CODING/BAEKJOON72 [BAEKJOON] 2579번 계단 오르기 이 문제는 첫 번째 계단을 밟는 것을 시작으로 한 칸 혹은 두 칸씩 계단을 오를 수 있다. 단, 첫 번째 계단을 꼭 밟아야 하고, 연속으로 한 칸씩 세 번 반복할 수는 없다. 즉, 한 칸을 오른 다음 한 칸, 그 다음 두 칸 오르기만 가능하다. 따라서 첫 번째 계단을 오르는 최대 점수는 첫 번째 계단의 가중치인 10점이고, 두 번째 계단을 오르는 최대 점수는 첫 번째 계단을 오른 후에 (첫 번째 계단 10 + 두 번째 계단 20으로 총 30점)이과 바로 두 번째 계단으로 오르는 20점 중 더 높은 점수인 30점 방식으로 계단을 오른다. 세 번째 계단을 오를 때는 1. 첫 번째 계단 → 세 번째 계단 ▶ 10 + 20 + 15 = 25 2. 두 번째 계단 → 세 번째 계단 ▶ 20 + 15 = 35 위 두.. 2022. 4. 24. [BAEKJOON] 2805번 나무 자르기 상근이가 필요한 나무의 길이 m을 구할 때까지 절단기의 길이를 늘리거나 줄이는 과정을 반복하여 최대 절단기의 길이를 구하는 문제이다. 절단기의 최소 길이는 0, 최대 길이는 주어진 나무의 최대 길이와 같을 것이다. (필요한 나무 길이가 주어진 나무의 최대 길이라면 굳이 자를 필요없이 절단기의 길이는 0일 것이고, 필요한 나무 길이가 0일 경우 절단기의 길이는 곧 주어진 나무의 최대 길이가 될 것이기 때문!) 따라서 절단기의 최소 길이 0부터 최대 길이까지 가능한 최대의 절단기 길이를 구한다. 절단기의 길이를 0, 1, 2, ... 최대길이까지 반복하기엔 시간과 메모리 초과에 발이 묶일 것이다. 정렬된 상태에서 특정 값을 빠르게 찾기 위해서는 이분 탐색 방법을 사용한다. 위의 그림을 보면 임의로 절단기의 .. 2022. 4. 2. [BAEKJOON] 1920번 수 찾기 주어진 A 배열과 입력되는 수간의 비교 연산으로 포함 여부를 판단하는 문제이다. 물론, 반복문으로 배열 전체와 입력되는 수를 하나씩 비교하며 포함되는지 여부를 알 수 있다. 하지만 반복문을 사용할 경우 메모리 초과를 경험할 수 있을 것이다. 결론부터 말하자면 A 배열을 오름차순 정렬하여 이진 탐색 방법으로 타켓 수와의 비교 연산을 줄여 효율을 높인다. 위의 그림과 같이 시작과 끝 인덱스를 기준으로 mid에 해당하는 중간 지점 인덱스를 구한다. '시작~중간' 과 '중간~끝' 중에 target이 되는 수가 어디 지점에 있는지만 알면 된다. target이 배열의 중간을 기준으로 오른쪽과 왼쪽 부분으로 나누었을 때 어느 지점에 있는지 찾아가는 과정을 반복하면 결국 중간지점은 언제나 마지막 하나가 남을 때까지 반.. 2022. 3. 30. [BAEKJOON] 2775번 부녀회장이 될테야 아래 표를 보면 규칙이 보이면 문제 해결 끝이다. 0층의 경우 i호에 i명이 산다고 했으니 1호에 1명, 2호에 2명 , ... , 가장 끝 방(∵ n≤14)인 14호에 14명이 거주 중일 것이다. 0층의 바로 윗 층인 1층을 보자. 1층의 1호는 0층의 1호부터 1호까지 합 즉, 1명 거주 1층의 2호는 0층의 1호부터 2호까지 합 즉, 3명 거주 1층의 3호는 0층의 1호부터 3호까지 합 즉, 6명 거주 중이다. 규칙이 보이지 않는가? 모든 층의 1호는 모두 1명이 거주할 것이고, arr[1층][2호] = arr[0층][2호] + arr[1층][1호] arr[1층][3호] = arr[0층][3호] + arr[1층][2호], ... 아래와 같은 규칙이 나타난다. arr[층][호수] = arr[층-1][.. 2022. 3. 28. [BAEKJOON] 1018번 체스판 다시 칠하기 아래 그림들은 위의 입력 예제에서 N : 10, M : 13일 때의 경우이다. 문제를 풀어보기 전에 완벽한 체스판의 8*8 윈도우가 있다고 가정하자. 물론 맨 왼쪽 시작이 B인지 W인지 두 가지 모두 고려해야 한다. 이 아래 하늘색의 윈도우를 한 칸씩 이동하며 주어진 체스판의 범위를 넘어가지 않는 한 탐색할 수 있도록 조정한다. 만약 주어진 체스판과 윈도우와 일치하지 않는 칸이 많다면 최소 개수를 만족하지 못 하므로 윈도우를 다음 칸으로 옮겨 탐색을 시작한다. 윈도우를 이동할 수 있는만큼 이동할 때까지 반복하며 주어진 체스판과 윈도우의 일치하지 않는 칸의 최소 개수를 구하면 된다. ※ 여기서 고려해야 할 점! 위에서 언급했듯이 윈도우의 맨 왼쪽 윗 칸이 B로 시작할 때와 W로 시작할 때 두 경우를 모두 .. 2022. 3. 25. [BAEKJOON] 1914번 하노이탑 ※ 3개의 원판을 A(초기)에서 C(목적) 기둥으로 옮기는 과정 ※ N개의 원판을 A(초기)에서 C(목적) 기둥으로 옮기는 과정 가장 큰 원판 위에 쌓여있는 N-1개의 원판들을 하나의 덩어리로 가정하고 생각해보자. 먼저 덩어리 N-1개의 원판을 B(임시)기둥으로 옮겨놓은 상태에서 가장 큰 원판을 C(목적)기둥으로 이동시키자. 이후, B(임시) 기둥에 있는 N-1개의 덩어리들을 C(목적) 기둥으로 옮기기만 하면 끝이다. 더 세세하게 과정을 나누어서 바로 위의 세 번째 그림을 보자. 위와 같이 가장 큰 원판(빨강색)을 C(목적) 기둥으로 옮겼다면 현실적으로 덩어리를 한 번에 C(목적) 기둥으로 옮길 수는 없다. 따라서 그 다음으로 큰 원판(주황색) 역시 C(목적) 기둥으로 옮기는 과정이 필수이다. 그 전에 .. 2022. 3. 24. 이전 1 2 3 4 5 6 7 ··· 12 다음
