알고리즘 풀이(Problem Solving) 검색 결과

해당 글 150건

알고리즘 풀이 - 백준 14500(테트로미노, 완전 탐색)

관련글 완전 탐색 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 NxM 크기의 종이에 숫자가 써져 있을 때, 정사각형 4개가 이어 붙혀진 폴리오미노(테트로미노)를 놓을 때, 그 합이 가장 큰 경우의 숫자를 구하는 문제 ※ 폴리오미노 크기가 1x1인 정사각형을 여러 개 이어 붙힌 도형 ※ 테트로미노 정사각형 4개를 이어 붙인 폴리오미노 2. 풀이 테트로미노의 경우의 수는 다음의 19가지 이다. 이 문제는 각 경우의 테트로미노에서 상단 좌측을 기준으로 종이에 놓는 19가지의 경우를 모두 체크하기만 하면 된다. 문제 자체는 크게 어려울 것 없지만 코드를 작성하는데 약간의 귀찮음이 따를 수 있다. 각 테트로미노를 놓을 때, 공간이 범위를 넘어..
알고리즘 풀이(Problem Solving)/완전 탐색(Brute Force) 2021. 1. 30. 23:52

알고리즘 풀이 - 백준 1107(리모컨, 완전 탐색)

관련글 완전 탐색 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 현재 채널(100)에서 다른 채널로 이동 시 최소로 버튼을 눌러 이동하는 경우를 구하는 문제 2. 풀이 현재 100번에 위치한 상태에서 N번 채널로 리모컨을 눌러 이동하는데, +/- 버튼 또는 숫자 버튼만 누를 수 있다. 알아둬야 할 사항은 다음과 같다. ① + / - 버튼을 누르면 1 채널씩 이동하며 -는 0번까지, +는 무한대로 이동할 수 있다. ② 숫자버튼은 누르면 바로 그 채널로 이동되니 +/-를 누른 후 숫자를 누르는 것은 의미가 없다.(숫자가 먼저!) ③ 고장난 버튼은 누를 수 없다. 여기서 N번 채널이라고 할 때, N은 최대 50만이므로 모든 0~9버튼이 고장..
알고리즘 풀이(Problem Solving)/완전 탐색(Brute Force) 2021. 1. 30. 11:59

알고리즘 풀이 - 백준 1476(날짜 계산, 완전 탐색)

관련글 완전 탐색 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 지구(E), 태양(S), 달(M)의 3가지 수를 이용해 연도를 나타낼 때, 우리 날짜로는 몇 년도인지 환산하는 문제 2. 풀이 이 문제를 푸는 간단한 방법은 1부터 시작하여 1씩 더해가며 비교하는 방법이다. 주어지는 E, S, M을 미리 저장하고, 다른 변수를 만들어 1씩 더해가면서 E, S, M의 값과 모두 일치해지는 값을 찾은 경우 그 경우의 결과값을 반환하면 정답이 된다. 이 문제는 E는 최대 15, S는 28, M은 19이므로 3개의 값을 모두 합하면 7980이 되어 경우의 수가 매우 적어 완전 탐색으로 간단하게 풀 수 있다. 별도의 추가 설명 없이 아래의 코드를 ..
알고리즘 풀이(Problem Solving)/완전 탐색(Brute Force) 2021. 1. 26. 22:28

알고리즘 풀이 - 백준 3085(사탕 게임, 완전 탐색)

관련글 완전 탐색 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 NxN크기의 칸에 사탕이 각각 나열되어 있을 때, 인접한 사탕을 상호 교환 후 모두 같은 색으로 이루어진 연속된 사탕을 먹을 때, 최대값을 구하는 문제 2. 풀이 NxN의 크기로 각 칸에 사탕이 하나씩 놓여져 있으며 인접한 사탕을 상호 교환 후 하나의 행 또는 열에서 가장 긴 연속된 사탕의 개수를 구하는 문제이다. 여기서, 우리는 2가지의 작업이 수행된다는 것을 알 수 있다. ① 인접한 사탕을 상호 교환한다. ② 행 또는 열에서 가장 긴 연속된 동일 사탕의 개수를 찾는다. 여기서 ①의 인접한 사탕을 교환하는 경우의 모든 경우의 수를 알아보자. 파란 사탕이 인접한 사탕은 붉..
알고리즘 풀이(Problem Solving)/완전 탐색(Brute Force) 2021. 1. 26. 19:59

알고리즘 풀이 - 백준 2309(일곱 난쟁이, 완전 탐색)

관련글 완전 탐색 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 9명의 난쟁이의 키가 주어졌을 때, 합이 100이 되는 7명의 난쟁이의 키를 오름차순으로 출력하는 문제 2. 풀이 우선 간단히 경우의 수를 생각해보자. 9명의 난쟁이 중 7명의 경우 키가 합이 100이 되므로 우리는 7명을 찾는 것이 아니라 2명을 걸러내는 것이 더 효율적이다. 즉, 전체 경우의 수는 아홉 중 둘을 골라내므로 ${}_{9}C_{2}$의 경우가 되어 총 36가지의 경우의 수가 있다. 따라서, 이 문제는 완전탐색으로 풀어도 큰 문제가 없다. 풀이는 다음과 같다. ① 우선 전체 난쟁이의 키를 더하고 배열을 정렬한다. ② 전체 키를 더한 값에서 100을 뺀 값과 ..
알고리즘 풀이(Problem Solving)/완전 탐색(Brute Force) 2021. 1. 19. 22:41

알고리즘 풀이 - 백준 17404(RGB거리 2, DP)

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 관련 문제인 1149(RGB 거리) 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 이 문제는 1~N번째 집이 놓여있을 때, 인접한 집이 색이 다르게 색칠하는 경우 가장 최소의 비용으로 칠할 때의 비용을 구하는 문제다. 주목할 점은 1번째와 N번째 또한 같은 색이어서는 안된다는 것이다. 2. 풀이 이 문제는 간단하게 DP로 해결이 가능하다. 인접한 위치의 집과 색상이 다르면 되기 때문에 이전 위치와 동일한 색상으로 칠하지 않는 색 중 가장 최소 비용인 것을 구해나가면 되기 때문이다. 이 문제에서 State는 N개의 집 중 몇 번째에 위치했느냐, 어떤 색으로 칠해졌느냐의 2가..
알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 17. 01:31

알고리즘 풀이 - 백준 2133(타일 채우기, DP)

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 관련 문제인 11726번(2xN 타일링) 포스팅은 여기를 참조 관련 문제인 11727번(2xN 타일링2) 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 더보기 이 문제는 3xN 크기의 타일을 2x1, 1x2 크기의 타일로 채우는 경우의 수를 구하는 문제이다. 2. 풀이 상단의 관련 문제 포스팅과 달리 이 문제는 3xN이라는 부분이 좀 어려운 부분이다. 3xN 타일을 기본적으로 채우는 방법은 아래와 같이 생각할 것이다. 3x2의 경우를 채우는 경우를 생각해보자. 위와 같은 3가지의 경우는 길이가 무조건 2이다. 이 문제는 타일을 옆으로 계속 채워나가는 방식이고 그 전체 경우의 수를 구하는 문제이기 때문에 이전에 채워진 상태인..
알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 16. 21:36

알고리즘 풀이 - 백준 13398(연속합2, DP)

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 관련 문제인 1912번(연속합) 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 더보기 이 문제는 배열의 연속합을 구하되 특정 값을 제거하거나 제거하지 않을 수 있는 옵션이 붙은 문제이다. 2. 풀이 우선 문제를 이해하자. 배열 내에서 단순히 값을 몇 개 뽑아서 더하는 것이 아니라 연속합 중 최대의 경우를 구해야 한다. 연속합은 1개만 있어도 연속합이 될 수 있다. 아래와 같은 배열이 있을 때를 예시로 조금만 알아보자. arr[i]는 원 배열이고, sum[i]는 연속합이 최대가 되는 경우의 배열이다. 인덱스 i 0 1 2 3 arr[i] 10 -12 30 -8 sum[i] 10 -2 30 22 sum[i]을 보며 왜 저..
알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 16. 13:32