plzrun 2632 - 피자판매 반복문을 통해 풀면 되는 문제이다. (1) 두 피자에서 한쪽 피자로만 줄 수 있는 경우의 수가 존재할 수 있으므로 distA[0] = distB[0] = 1로 주었다. (2) 피자 한 판에서 나올 수 있는 모든 경우의 수를 구하다 t보다 클 경우 종료 에서 그림을 보면 알 수 있는데 i, j를 m까지 돌리면서 피자 한판 자체가 m 크기이니 (i + j)를 m으로 나눈 결과의 인덱스 값을 tm... Binary SearchplzrunbaekjoonBinary Search 2143 - 두 배열의 합 이해 문제에서는 두 배열의 합을 더해서, T가 되는 모든 부 배열의 쌍의 개수를 구하는 프로그램을 작성하려고 하였다. 이는 순차적으로 탐색을 하며, 완전 탐색을 해야하는 상황이다. 배열의 합 : A[i] + ... + A[j] 그 사이의 합을 구하는 문제이다. 순차적으로 탐색을 하며, 사이 구간의 합을 구할 때는 딕셔너리를 사용하면 된다. 이와 같은 문제를 풀 때는, 현재 A의 합들을 딕셔너... Binary SearchplzrunbaekjoonBinary Search 2447 - 별 찍기 - 10 이해 재귀적인 패턴으로 별을 찍는다. 평소에는 반복문 위주로 사용하여, 이번 문제는 재귀를 이용하여 풀었다. 현재 n = 3^i일 때, 가운데를 제외한 나머지는 n = 3^(i-1)이다. n이 3^i일 때 ➡️ * : 3^(i - 1)이다. 위를 이용하여 재귀함수를 구현하였다. 재귀말고, 배열로만 결과를 낼 수도 있다. (위 블로그 참고하면 된다.) 소스 채점 결과... Divide and conquerbaekjoonplzrunDivide and conquer 2448 - 별 찍기 - 11 이해 위 별의 모양이 반복해서 출력된 것을 확인할 수 있다. 문제에 나와있는 공식에 따르면 (N = 3 x 2^k)라고 한다. k가 1일 때는 위 별의 모양이 2개가 추가 되는 것이고 k가 2일 때는 k가 1일 때 모양을 2개 추가한 것을 알 수 있다. 이와 같이 반복된다. 띄어쓰기는 k가 1일 때는 위 별의 모양에서 왼쪽으로 3칸 띄워쓰기가, 위 별의 모양에서 오른쪽 끝은 3칸 띄워지면 된... Divide and conquerbaekjoonplzrunDivide and conquer 2875 - 대화 or 인턴 이해 브론즈 문제이지만, 약간 생각을 해야한다고 생각한다. 조건처리하는데, 생각을 많이 한 것 같다. 소스 채점 결과... plzrungreedybaekjoonbaekjoon 1744 - 수 묶기 이해 나 같은 경우, 모든 경우의 수를 조건식으로 처리했으나 이는 좋지 않은 방법이라는 것을 알게 되었다. ✔️ 좋은 해결책으로 음수는 오름차순 정렬, 양수는 내림차순 정렬, 1은 곱하기 대신 더하는 방식 (0은 음수에 속하게 된다.) 0과 음수의 개수 합이 홀수라면 제일 작은 값을 정답에 더한다. 0과 음수의 개수 합이 짝수라면 두 수를 곱하고 정답에 더한다. 소스 첫 나의 소스 좋은 해결... plzrungreedybaekjoonbaekjoon 1783 - 병든 나이트 이해 규칙이 있는데 세로가 1일 때는 1 세로가 2일 때는 2번째(1칸 위로, 2칸 오른쪽), 3번째(1칸 아래로, 2칸 오른쪽) 밖에 사용하지 못한다. 그러므로, 이동 횟수가 최대 4이다. 오른쪽으로 2만큼이므로 min(4, m+1)이 된다. (예를 들어, m이 3이면 이동할 수 있는 칸은 2번이다.) 세로가 3이상일 때는 가로의 길이 6보다 크다면 시작을 2, 3으로 하고 7번부터는 1번... plzrungreedybaekjoonbaekjoon ATM - 11399 이해 정렬 후 현재 합, 전체 총합을 각각 구하여 계산한다. 정렬 후 1번째 수는 n번 더해지고, 2번째 수는 n-1번 더해지고 ~ n번째 수는 1번 더해진다. 소스 채점 결과 결과를 보면 위에 (2), 밑에 (1) 채점 결과... plzrungreedybaekjoonbaekjoon 1451 - 직사각형으로 나누기 ✔️ (1, 1)부터 (n, m)까지 각 자리의 총합 → 왜 (1, 1)을 빼는가? (1, 2)와 (2, 1)에 (1, 1)이 2번 더해진다. → 왜 (2, 2)를 빼는가? (2, 3)와 (3, 2)에 (2, 2)가 2번 더해진다. (1, 1) 행열 부터 (n, m) 행렬까지 총합이다. ✔️ 각 자리수 총합을 이용해 (a, b)부터 (n, m)까지 합 만약 (2, 2) 부터 (3, 3)까지 ... plzrunbaekjoonbrute forcebaekjoon 2186 - 문자판 이해 n, m 크기의 문자판이 주어지며, 경로의 개수를 구하는 문제이다. 직사각형과 경로가 등장했다. 이는 깊이 우선 탐색, 너비 우선 탐색으로 풀 수 있는 문제라는 것이다. 보통 우선 탐색 문제들은 좌표안에서 지나갈 수 있는 경로를 구할 때 많이 사용된다. 📌 주의점 출력 값이 2^31 - 1 보다 작거나 같기 때문에, 메모이제이션을 사용하여 계산들을 메모리에 저장함으로써 동일한 계산의 반... plzrunbaekjoonbrute forcebaekjoon 3108 - 로고 이해 내가 푼 완전 탐색 중에서 가장 어려웠다고 생각한다. 1시간 정도 보다가 이해가 안되서 바로 검색했다! ↑ 여기 설명 진짜 잘되어 있다. 어떤 경우의 수에 체크해야할지 잘 나와있다. 근데 위와 똑같이 python으로 제출 할 경우 런타임 에러가 발생한다. 그래서 방문했는지 안했는지 체크하는 소스가 필요하다. 소스 채점 결과... plzrunbaekjoonbrute forcebaekjoon 5014 - 스타트링크 이해 이번 문제는 전형적인 너비 우선 탐색 문제이다. 이와 같이 총 길이가 나와 있고, 시작점과 도착점 그리고 증가와 감소가 나와있을 경우 너비 우선 탐색을 사용하면 된다. 다만, 나도 이것 때문에 틀렸었는데 무조건 경우의 수가 존재하지 않는다고 use the stairs를 출력하면 틀린다! 위와 같은 경우의 수도 체크해야 한다. 소스 채점 결과... plzrunbaekjoonbrute forcebaekjoon 9019 - DSLR 이해 너비 우선 탐색으로 모든 노드를 방문하다가 b를 찾았다면, 종료하면 된다. (1) D : n은 2배로 나눈다. (10,000보다 큰 경우, 10000으로 나눈 나머지) → 현재숫자 * 2 % 10000 (2) S : n에서 1을 뺀다. (0인 경우, 9999로) → (현재숫자-1) % 10000 (3) L : n의 각 자릿수를 왼편으로 회전 (d1d2d3d4 -> d2d3d4d1) → ... plzrunbaekjoonbrute forcebaekjoon 가장 긴 증가하는 부분 수열 dp[i]의 값을 1로 초기화 현재 위치보다 이전에 있는 원소의 값이 작은지 확인한다. (크거나 같으면 가장 긴 증가하는 부분 수열이 될 수 없다.) 작다면, 현재 위치의 이전 숫자 중, dp값에 + 1을 하여 현재 위치 dp 값과 비교한다. 그 중 최대값을 구한다. 예시를 보면 이와 같다. arr dp 실행 결과 참고 내용 :... baekjoonDPplzrunDP 11057 - 오르막 수 기존 나의 코드 상위권 효율적인 코드 참고 결과 규칙을 잡아 DP를 이용하니 for문 2개로 해결되었다. 시간이 대략 12ms 차이난다.... baekjoonDPplzrunDP 2004 - 조합 0의 개수 풀이 조합식 : nCr = n! / (n-m)!r! 끝자리 0의 개수를 출력한다. 조합식을 보면 분모에는 : n! 분자에는 : (n-m)!, r! 가 있다. ➡ 그러므로 0의 개수는 분자에 있는 0의 개수에서 분모에 있는 0의 개수를 빼주면 된다. 또한, 10의 배수는 2와 5의 배수이다. (두 수 개수가 같다면 10의 배수가 된다.) ➡️ 분자에 있는 0의 개수에서 분모에 있는 0의 개수를... baekjoonplzrunmathbaekjoon 1991 - 트리 순회 풀이 문제는 전형적인 트리 순회 알고리즘 문제이다. 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal) 만약, 전위, 중위, 후위에 대해 모른다면 이를 참고하면 될 것 같다. Pre-order(전위순회) 1) 루트노드 방문 2) 왼쪽 자식 노드를 루트로 하는 서브 트리를 프리오더(재귀) 3) 오른쪽 자... GraphbaekjoonplzrunGraph
2632 - 피자판매 반복문을 통해 풀면 되는 문제이다. (1) 두 피자에서 한쪽 피자로만 줄 수 있는 경우의 수가 존재할 수 있으므로 distA[0] = distB[0] = 1로 주었다. (2) 피자 한 판에서 나올 수 있는 모든 경우의 수를 구하다 t보다 클 경우 종료 에서 그림을 보면 알 수 있는데 i, j를 m까지 돌리면서 피자 한판 자체가 m 크기이니 (i + j)를 m으로 나눈 결과의 인덱스 값을 tm... Binary SearchplzrunbaekjoonBinary Search 2143 - 두 배열의 합 이해 문제에서는 두 배열의 합을 더해서, T가 되는 모든 부 배열의 쌍의 개수를 구하는 프로그램을 작성하려고 하였다. 이는 순차적으로 탐색을 하며, 완전 탐색을 해야하는 상황이다. 배열의 합 : A[i] + ... + A[j] 그 사이의 합을 구하는 문제이다. 순차적으로 탐색을 하며, 사이 구간의 합을 구할 때는 딕셔너리를 사용하면 된다. 이와 같은 문제를 풀 때는, 현재 A의 합들을 딕셔너... Binary SearchplzrunbaekjoonBinary Search 2447 - 별 찍기 - 10 이해 재귀적인 패턴으로 별을 찍는다. 평소에는 반복문 위주로 사용하여, 이번 문제는 재귀를 이용하여 풀었다. 현재 n = 3^i일 때, 가운데를 제외한 나머지는 n = 3^(i-1)이다. n이 3^i일 때 ➡️ * : 3^(i - 1)이다. 위를 이용하여 재귀함수를 구현하였다. 재귀말고, 배열로만 결과를 낼 수도 있다. (위 블로그 참고하면 된다.) 소스 채점 결과... Divide and conquerbaekjoonplzrunDivide and conquer 2448 - 별 찍기 - 11 이해 위 별의 모양이 반복해서 출력된 것을 확인할 수 있다. 문제에 나와있는 공식에 따르면 (N = 3 x 2^k)라고 한다. k가 1일 때는 위 별의 모양이 2개가 추가 되는 것이고 k가 2일 때는 k가 1일 때 모양을 2개 추가한 것을 알 수 있다. 이와 같이 반복된다. 띄어쓰기는 k가 1일 때는 위 별의 모양에서 왼쪽으로 3칸 띄워쓰기가, 위 별의 모양에서 오른쪽 끝은 3칸 띄워지면 된... Divide and conquerbaekjoonplzrunDivide and conquer 2875 - 대화 or 인턴 이해 브론즈 문제이지만, 약간 생각을 해야한다고 생각한다. 조건처리하는데, 생각을 많이 한 것 같다. 소스 채점 결과... plzrungreedybaekjoonbaekjoon 1744 - 수 묶기 이해 나 같은 경우, 모든 경우의 수를 조건식으로 처리했으나 이는 좋지 않은 방법이라는 것을 알게 되었다. ✔️ 좋은 해결책으로 음수는 오름차순 정렬, 양수는 내림차순 정렬, 1은 곱하기 대신 더하는 방식 (0은 음수에 속하게 된다.) 0과 음수의 개수 합이 홀수라면 제일 작은 값을 정답에 더한다. 0과 음수의 개수 합이 짝수라면 두 수를 곱하고 정답에 더한다. 소스 첫 나의 소스 좋은 해결... plzrungreedybaekjoonbaekjoon 1783 - 병든 나이트 이해 규칙이 있는데 세로가 1일 때는 1 세로가 2일 때는 2번째(1칸 위로, 2칸 오른쪽), 3번째(1칸 아래로, 2칸 오른쪽) 밖에 사용하지 못한다. 그러므로, 이동 횟수가 최대 4이다. 오른쪽으로 2만큼이므로 min(4, m+1)이 된다. (예를 들어, m이 3이면 이동할 수 있는 칸은 2번이다.) 세로가 3이상일 때는 가로의 길이 6보다 크다면 시작을 2, 3으로 하고 7번부터는 1번... plzrungreedybaekjoonbaekjoon ATM - 11399 이해 정렬 후 현재 합, 전체 총합을 각각 구하여 계산한다. 정렬 후 1번째 수는 n번 더해지고, 2번째 수는 n-1번 더해지고 ~ n번째 수는 1번 더해진다. 소스 채점 결과 결과를 보면 위에 (2), 밑에 (1) 채점 결과... plzrungreedybaekjoonbaekjoon 1451 - 직사각형으로 나누기 ✔️ (1, 1)부터 (n, m)까지 각 자리의 총합 → 왜 (1, 1)을 빼는가? (1, 2)와 (2, 1)에 (1, 1)이 2번 더해진다. → 왜 (2, 2)를 빼는가? (2, 3)와 (3, 2)에 (2, 2)가 2번 더해진다. (1, 1) 행열 부터 (n, m) 행렬까지 총합이다. ✔️ 각 자리수 총합을 이용해 (a, b)부터 (n, m)까지 합 만약 (2, 2) 부터 (3, 3)까지 ... plzrunbaekjoonbrute forcebaekjoon 2186 - 문자판 이해 n, m 크기의 문자판이 주어지며, 경로의 개수를 구하는 문제이다. 직사각형과 경로가 등장했다. 이는 깊이 우선 탐색, 너비 우선 탐색으로 풀 수 있는 문제라는 것이다. 보통 우선 탐색 문제들은 좌표안에서 지나갈 수 있는 경로를 구할 때 많이 사용된다. 📌 주의점 출력 값이 2^31 - 1 보다 작거나 같기 때문에, 메모이제이션을 사용하여 계산들을 메모리에 저장함으로써 동일한 계산의 반... plzrunbaekjoonbrute forcebaekjoon 3108 - 로고 이해 내가 푼 완전 탐색 중에서 가장 어려웠다고 생각한다. 1시간 정도 보다가 이해가 안되서 바로 검색했다! ↑ 여기 설명 진짜 잘되어 있다. 어떤 경우의 수에 체크해야할지 잘 나와있다. 근데 위와 똑같이 python으로 제출 할 경우 런타임 에러가 발생한다. 그래서 방문했는지 안했는지 체크하는 소스가 필요하다. 소스 채점 결과... plzrunbaekjoonbrute forcebaekjoon 5014 - 스타트링크 이해 이번 문제는 전형적인 너비 우선 탐색 문제이다. 이와 같이 총 길이가 나와 있고, 시작점과 도착점 그리고 증가와 감소가 나와있을 경우 너비 우선 탐색을 사용하면 된다. 다만, 나도 이것 때문에 틀렸었는데 무조건 경우의 수가 존재하지 않는다고 use the stairs를 출력하면 틀린다! 위와 같은 경우의 수도 체크해야 한다. 소스 채점 결과... plzrunbaekjoonbrute forcebaekjoon 9019 - DSLR 이해 너비 우선 탐색으로 모든 노드를 방문하다가 b를 찾았다면, 종료하면 된다. (1) D : n은 2배로 나눈다. (10,000보다 큰 경우, 10000으로 나눈 나머지) → 현재숫자 * 2 % 10000 (2) S : n에서 1을 뺀다. (0인 경우, 9999로) → (현재숫자-1) % 10000 (3) L : n의 각 자릿수를 왼편으로 회전 (d1d2d3d4 -> d2d3d4d1) → ... plzrunbaekjoonbrute forcebaekjoon 가장 긴 증가하는 부분 수열 dp[i]의 값을 1로 초기화 현재 위치보다 이전에 있는 원소의 값이 작은지 확인한다. (크거나 같으면 가장 긴 증가하는 부분 수열이 될 수 없다.) 작다면, 현재 위치의 이전 숫자 중, dp값에 + 1을 하여 현재 위치 dp 값과 비교한다. 그 중 최대값을 구한다. 예시를 보면 이와 같다. arr dp 실행 결과 참고 내용 :... baekjoonDPplzrunDP 11057 - 오르막 수 기존 나의 코드 상위권 효율적인 코드 참고 결과 규칙을 잡아 DP를 이용하니 for문 2개로 해결되었다. 시간이 대략 12ms 차이난다.... baekjoonDPplzrunDP 2004 - 조합 0의 개수 풀이 조합식 : nCr = n! / (n-m)!r! 끝자리 0의 개수를 출력한다. 조합식을 보면 분모에는 : n! 분자에는 : (n-m)!, r! 가 있다. ➡ 그러므로 0의 개수는 분자에 있는 0의 개수에서 분모에 있는 0의 개수를 빼주면 된다. 또한, 10의 배수는 2와 5의 배수이다. (두 수 개수가 같다면 10의 배수가 된다.) ➡️ 분자에 있는 0의 개수에서 분모에 있는 0의 개수를... baekjoonplzrunmathbaekjoon 1991 - 트리 순회 풀이 문제는 전형적인 트리 순회 알고리즘 문제이다. 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal) 만약, 전위, 중위, 후위에 대해 모른다면 이를 참고하면 될 것 같다. Pre-order(전위순회) 1) 루트노드 방문 2) 왼쪽 자식 노드를 루트로 하는 서브 트리를 프리오더(재귀) 3) 오른쪽 자... GraphbaekjoonplzrunGraph