알고리즘 썸네일형 리스트형 프로그래머스 - 퍼즐 게임 챌린지 0. 개요파라메트릭 서치(이분탐색) 문제입니다.파라메트릭 서치의 경우 아래의 문제풀이 글에서 자세히 설명했으니 참고하시길 바랍니다.https://ksb-dev.tistory.com/257 프로그래머스 - 디펜스 게임(Java)[수정 알림] 파라메트릭 서치 및 우선순위 큐로 문제를 해결했는데, 테케 10번에서 시간초과가 발생하신다는 분이 계셨습니다. 저의 경우 제 방법이 아슬아슬하게 통과를 했던것 같고, 서버 상태ksb-dev.tistory.com 1. 파라메트릭서치인 이유파라메트릭서치는 최적의 문제 찾기를 결정 문제로 바꿀 수 있는 알고리즘입니다.문제에서 "퍼즐을 모두 해결하기 위한 숙련도의 최솟값"을 구하라고 나왔습니다.이는 최적의 숙련도를 찾으라는 문제입니다. 1씩 증가시키며 숙련도를 찾아야할까요?l.. 더보기 소프티어 - 효도 여행 (Java) 0. 개요DFS 및 LCS 문제입니다.이 문제는 DFS 특징을 활용한 LCS 재활용입니다. 1. DFS 특징을 활용한 LCS 재활용문제의 예시 트리는 아래와 같습니다. DFS를 통한 좌측 두 개의 리프 노드 탐색 순서는 아래와 같습니다. 7번 : 1 -> 2 -> 4 -> 78번 : 1 -> 2 -> 5 -> 8 각 경로마다 문자가 주어지니 7, 8번 리프 노드까지 도달했을 때 문자는 아래와 같습니다.7번 : ACF8번 : AZQ 감이 오시나요? 리프 노드까지 탐색 경로에는 중첩된 부분이 있을 수 있습니다.또, 중첩된 경로 만큼 중복되는 문자가 있습니다. 7번과 8번의 노드는 2번 까지의 중첩되는 경로가 존재하고,A 문자가 공통적으로 존재합니다. 그렇다면,DFS 레벨에 맞게 해당 계층의 LCS만 구하면 .. 더보기 소프티어 - 나무 섭지 (Java) 0. 개요BFS 문제입니다.두 번의 BFS를 통해 이 문제를 해결할 수 있습니다.유령이 시간 내에 갈 수 있는 위치남우 탈출 https://softeer.ai/practice/7726 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai 1. 유령이 시간 내에 갈 수 있는 위치각 유령의 초기 위치를 큐에 저장해서, 각 위치에 얼마만에 유령이 도달할 수 있는지 저장해야 합니다. 문제의 1번 테스트 케이스를 그림으로 표현하면 아래와 같습니다. 유령의 거리 배열을 저장하게 된다면 아래 그림처럼 나타낼 수 있습니다. 유령은 벽을 통과할 수 있다는 점을 조심해야 합니다. 2. 남우 탈출유령의 거리 배열을 구했으니, 남우를 탈출시키면 됩니다.남우를 탈출 할 때 벽인지, 유령보다 빠르게 특정 위치에.. 더보기 코드 트리 - 마법의 숲 탐색(Java) 0. 개요구현 문제입니다. 이 문제를 해결하기 위해서 두 가지의 주의 사항이 있을거 같습니다.1. 골렘의 시작점은 숲 밖이다.2. 골렘 몸의 일부와 출구를 분리해야 한다. 1. 골렘의 시작점은 숲 밖이다.아래와 같은 그림일 때, 어떻게 동작될까요? 정답은, 왼쪽으로 회전한다는 것입니다.왼쪽으로 2회전이 가능하기 때문에 아래와 같은 그림으로 골렘의 이동이 종료됩니다. 이렇게 골렘은 숲 밖에서 부터 회전을 할 수 있습니다. 저는 이를 위해서 숲 바깥, 숲 위, 숲 안쪽을 각 -2, -1, 0 으로 표현했습니다.이를 그림으로 표현하면 아래와 같습니다. 행과 열의 입력의 범위가 70 이하입니다.저의 경우 편의상 80*80 배열을 만들어 (3,3) 부터 숲 내부가 되도록 고정시켰습니다. 좌측열에 패딩을 준 이유.. 더보기 백준 - 3197 백조의 호수(Java) 구현 문제입니다. 물과 인접한 얼음이 1초마다 없어지는데, 몇 초 후에 두 마리의 백조가 만나는지 구하는 문제입니다. 얼음을 녹이고 백조를 움직이면 입력 범위가 매우 커 시간 초과가 발생했습니다. 때문에 저는 두 가지 방법을 통해 이 문제를 해결했습니다.얼음 두께 구하기한 마리의 백조만 이동 1. 얼음 두께 구하기얼음 두께는 물과의 최대 거리가 됩니다.즉, 얼음 두께만큼 시간이 지나야 해당 얼음이 녹아 물이 됩니다. 이는 네 방향으로 알 수 있습니다.다음과 같은 얼음이 있다고 하겠습니다. 우선 오른쪽 방향으로 얼음의 두께를 확인합니다.물을 0로 두고, 얼음을 1로 둔 상태의 누적 최솟값을 구하는 것과 같습니다. 왼쪽으로 최솟값을 갱신합니다. 아래로 최솟값을 갱신합니다. 위로 최솟값을 갱신합니다. 즉, .. 더보기 프로그래머스 - 상담원 인원 (Java) 구현, 그리디 문제입니다. 상담원 인원과 참가자의 상담 요청 정보가 주어졌을 때, 대기시간을 최소로 하는 시간을 구하는 문제입니다. 우리가 해야하는 것은 대기시간을 최소로 하도록 상담원 배치를 하고 나서, 최소 대기 시간을 구해야 합니다. 어떻게 하면 최소 대기 시간을 만들도록 상담원을 배치할 수 있을까요? 문제 조건에 의해 모든 유형에는 상담원이 한 명씩은 배치되어야 합니다. 우선 한 명씩 상담원을 배치하고, 상담원이 추가되었을 때 가장 많이 대기 시간이 줄어드는 타입에 우선적으로 배치하면 됩니다. 가장 많이 대기시간이 줄어들게 되면 전체에서도 최소로 만들어지는 경우이로 만들어지기 때문에 그리디로 접근할 수 있습니다. 문제 접근 순서는 다음과 같습니다. 유형마다 상담 요청 시간 분리 각 유형마다 1~(.. 더보기 백준 - 17825 주사위 윷놀이 (Java) 구현 문제입니다. 문제 조건 자체는 이해하기 어려운 부분은 딱히 없는거 같습니다. 하지만, 이것을 코드로 구현하려니 마땅한 아이디어가 떠오르지 않았습니다. 3~4일간 이 문제만 붙잡고 백준 질문게시판에서 얻은 테스트 케이스를 직접 써보면서 경우의 수를 확인하고, 수많은 디버깅을 한 끝에 맞출 수 있었습니다. 제가 문제를 해결한 방법을 아래 글을 통해 공유하겠습니다. 1. 그래프로 윷놀이 판 구현하기 문제에서 주어지는 주사위 윷놀이 판의 모습은 아래 그림과 같습니다. 이 모습을 보자마자 그래프를 떠올렸고, 그림을 그래프로 표현하고자 했습니다. 우선 파란색으로 갈 수 있는 곳을 지름길(Shortcut)이라 가정했습니다. 💡 [10, 20, 30에서 출발해 40까지의 길이 모두 지름길입니다.] 💡 [편의상 빨.. 더보기 백준 - 17822 원판 돌리기 구현 문제입니다. 1. 문제 설명 원판과 조건이 주어지고, 조건처럼 행동했을 때 원판에 남아있는 수의 총합을 구하는 문제입니다. 원판과 그에 인접한 위치를 이차원 배열 그림으로 나타내면 아래와 같습니다. 기본적으로 4방 탐색을 하면서 세로는 위아래 끝이 연결되지 않습니다. 가로는 양옆 끝이 연결되어 있습니다. 또, 원판이 회전하게 되면 가로의 방향으로 만 움직입니다. D가 0일때는 아래와 같이 오른쪽(시계 방향)으로 움직입니다. D가 1일때는 아래와 같이 왼쪽(반시계 방향)으로 움직입니다. X는 회전할 세로 위치를 의미하며, K는 회전의 양을 의미합니다. 2. 접근 방법 접근 방법은 문제 자체에서 주어진 그 순서와 크게 다르지 않습니다. x의 배수의 위치의 배열들을 회전한다. d가 0일경우 오른쪽(시계 .. 더보기 이전 1 2 3 4 ··· 17 다음
