문제3x3 퍼즐판이 주어졌을 때, 퍼즐판의 알파벳을 사용하여 만들 수 있는 단어의 수를 알파벳별로 계산하고, 단어 수의 최솟값과 최댓값에 해당하는 알파벳을 출력하는 문제이다.풀이퍼즐의 알파벳들과 각 단어의 알파벳들의 비교하여 만들 수 있는 단어인지 파악하고, 퍼즐의 각 알파벳이 총 몇 개의 단어를 만드는데 사용될 수 있는지 세면 최솟값과 최댓값을 구할 수 있다.먼저 단어 사전의 단어들의 알파벳 빈도 딕셔너리로 변환하여 저장한다. (중복 값이 있을 수 있음을 고려) 퍼즐 정보를 하나씩 받으면서 퍼즐의 알파벳 빈도 딕셔너리를 생성한다.단어 사전의 단어들과 퍼즐을 비교하여 퍼즐을 통해 만들 수 있는 단어인지 확인한다.퍼즐 알파벳의 빈도가 단어 알파벳의 빈도보다 작으면 만들 수 없는 단어이다.만들 수 있는 단어..
문제1부터 N까지의 정수로 이루어진 순열을 오름차순으로 정렬할 때, 최소 몇 번의 뒤집기를 해야 하는지 구하는 문제이다.정렬은 특정 위치 iii에서 시작하여 오른쪽으로 K개의 숫자를 뒤집는 연산을 반복하는 방식으로 이루어진다. 예를 들어 N이 5, K가 3일 때, (5, 4, 3, 2, 1) 순열이 주어진 경우i=0에서 뒤집으면 (3, 4, 5, 2, 1) 이 된다.i=1에서 뒤집으면 (3, 2, 5, 4, 1) 이 된다.i=2에서 뒤집으면 (3, 2, 1, 4, 5) 이 된다.i=0에서 뒤집으면 (1, 2, 3, 4, 5) 이 되면서 정렬이 완료된다.최소 4번의 뒤집기로 오름차순 순열을 만들 수 있다.풀이이 문제는 각 순열 상태를 노드로 보고, 한 번의 뒤집기로 다른 상태로 이동하는 최단 경로 탐색 문..
문제정수를 십진수로 표현할 때, 각 자리수가 왼쪽에서 오른쪽으로 감소하는 줄어드는 수 중 n번째로 작은 줄어드는 수를 구하는 문제이다.예를 들어 54321나 654는 줄어드는 수이며, 544나 324은 줄어드는 수가 아니다. 풀이BFS로 n번째 작은 수까지의 모든 경우의 수를 찾아 정답을 도출 할 수 있다.BFS를 사용하는 이유는 작은 수부터 순차적으로 줄어드는 수를 생성하므로, 추가적인 정렬 없이도 오름차순으로 n번째 줄어드는 수를 찾을 수 있기 때문이다.먼저 한 자리수 (0~9)를 큐에 넣는다.큐에서 줄어드는 수를 꺼내어 해당 숫자가 n번째 줄어드는 수라면 탐색을 멈추고 결과를 반환한다.아니라면, 1의 자리보다 작은 숫자를 뒤에 추가해 새로운 줄어드는 수를 생성한다.만약 n번째 줄어드는 수가 없다면 ..
[프로그래머스 / Python] 거스름돈
문제주어진 금액을 만들기 위해 동전 종류에 따라 거스름돈을 주는 방법의 수를 구하는 문제이다.풀이동적 프로그래밍(DP)을 사용해 풀 수 있다. 특정 금액 n을 만들기 위한 방법의 수를 누적해서 계산한다. 이때 작은 동전(금액)부터 시작해 큰 동전에 대해 가능한 경우의 수를 차례로 계산한다. dp[0]은 항상 아무 동전도 쓰이지 않는 방법 한 가지만 존재함으로 dp[0]=1로 지정한다. 현재 금액 x를 만들기 위한 방법의 수는 x - coin을 만들 수 있는 방법의 수에 현재 동전 coin을 추가한 것이다. 이를 토대로 점화식을 구성하면 dp[x] = dp[x] + dp[x-coin] 이 된다. 마지막 정답을 도출할 때는 숫자가 매우 커질 것을 방지해 1000000007로 나눈 나머지를 반환한다.Pytho..
문제게임 보드 위의 숫자에 따라 동전을 이동시킬 때, 동전을 움직이는 횟수가 최대가 되도록 하는 문제이다.보드 위의 숫자는 1부터 9까지 있으며, 해당 칸에서 다음 칸으로 이동할 때 표기된 숫자만큼 한 번에 이동해야 한다.동전은 상하좌우로 이동할 수 있고, H(구멍) 칸이나 보드 바깥으로 이동되면 게임이 종료된다.풀이이 문제에서는 깊이 우선 탐색(DFS)과 메모이제이션, 백트래킹을 사용해 풀 수 있다.재귀적으로 DFS를 사용해서 동전이 이동할 수 있는 모든 경로를 탐색한다.메모이제이션 DFS 탐색을 하면서 특정 칸에 대한 경로 탐색이 끝나면, 그 칸에서 최대 이동 횟수를 계산한 상태이다.따라서 중복 탐색을 방지하기 위해, 계산된 값을 메모이제이션을 통해 저장한다.탐색 도중 이미 계산된 값( dp[x][y..
문제주어진 2차원 배열에서 각 칸에 고일 수 있는 물의 양을 계산하는 문제이다. 각 칸의 물 높이는 주변에 있는 벽(높이가 더 큰 칸들)에 의해 제한되며, 물은 낮은 칸을 채워 나가면서 주위 벽에 의해 막히는 곳에만 고일 수 있다.풀이이 코드의 핵심은 외곽부터 낮은 높이의 칸을 우선 탐색하면서 물을 채워나가는 것이다.먼저, 외곽에 있는 칸들을 힙에 추가하고 높이가 낮은 칸부터 탐색을 시작한다.탐색하면서 주변에 더 낮은 높이의 칸이 있다면, 현재 칸의 높이만큼 물을 채우고 채운 물의 양을 답에 더한다.물 높이와 상관없이 방문하지 않은 칸이라면 방문 처리 후, 현재 높이와 좌표를 힙에 추가하여 계속해서 주변을 탐색한다.이 과정을 통해 최종적으로 고일 수 있는 물의 양을 계산한다.Python 코드import ..
[백준 BOJ / Python] 22352번 항체 인식
문제주어진 격자 데이터의 전후를 비교하여 주입된 백신이 CPCU-1202 백신인지 판단하는 문제이다.CPCU-1202 백신을 놓으면, 백신이 주입된 조직에서 항체를 생성하고 같은 영역의 조직에 항체가 퍼진다.항체는 조직을 변형시켜 동일한 색상이거나 다른 색상이 될 수 있다. 풀이전체 조직의 영역들 중 색상이 바뀐 영역이 1개이하여야 한다.따라서 조직을 탐색하면서 동일한 영역이 변경된 것인지를 판단하고, 색상이 변경된 영역의 개수를 세어야 한다.BFS나 DFS를 통해 동일한 색상으로 이루어진 인접 영역을 탐색하며 해당 영역이 일관된 색상으로 변경되었는지 확인한다.탐색 중 영역이 다르다면 CPCU-1202 백신이 아님으로 NO를 출력하고,색상이 변경된 영역의 개수가 2개이상이어도 NO를 출력하며,그 외의 경..