KMF

요세푸스 순열을 구하는 문제이다. 요세푸스 순열을 구할때 유의해야할 점은 배열이 순환한다는 것이다. 이는 배열의 인덱스를 구할때 인덱스가 배열의 크기보다 큰 경우 인덱스는 K-1만큼 커진다. from sys import stdin readline = stdin.readline def get_ys_seq(): idx = K - 1 stack = [i+1 for i in range(N)] result = [] for _ in range(N): if len(stack)

DFS를 사용한다는 것 말고는 제대로된 접근도 하지 못한 문제이다. 임의의 한 노드를 얼리어답터로 할 것인지 하지 않을 것인지 기준을 잡는 것이 중요하다. 1. 현재 노드가 얼리어답터일 경우: 자식 노드는 얼리어답터일 수도 아닐 수도 있다. 2. 현재 노드가 얼리어답터가 아닐 경우: 자식노드는 반드시 얼리어답터이어야 한다. 다음으로는 점화식을 만들어야 한다. 얼리어답터인 경우를 0, 그렇지 않을 경우를 1로 하고 2차원 배열을 선언한다. DP 노드는 현재 노드가 얼리어답터일 경우 최소 얼리어답터 수와 현재 노드가 얼리어답터가 아닐 경우 얼리어답터의 최소 수를 담고 있다. DP[node][0] = 0 : node는 얼리어답터가 아니다 DP[node][1] = 1 : node는 얼리어답터 이다. 점화식 DP..

외판원 순환 문제( TSP: Traveling Salesperson Problem)이다. TSP는 하나의 시작점에서 모든 도시를 단 한번씩만 방문하여 원래 도시로 돌아오는 문제를 말한다. TSP를 해결하기 위한 방법은 두 가지가 존재한다. 1. 완전탐색 O(N!) 2. 다이나믹 프로그래밍 O(N^2 * 2^N) 만약 도시의 개수가 10개 이하라면 완전탐색도 사용이 가능하다. 하지만 일반적으로 다이나믹 프로그래밍을 사용한다. 그리고 방문한 도시를 구분하는 방법이 이전에 풀었던 문제와 다른데 비트 마스크를 사용한다. 만약 1, 2, 3, 4의 도시가 존재한다면, 1과 2 도시를 방문할 경우 1100과 같이 나타낸다. 비트 마스크로 나타내어 만약 방문한 도시가 동일하다면 비용도 동일하기 때문에 굳이 모두 직정..

주어진 대나무 숲에서 가장 오래 살 수 있는 기간을 구하는 문제이다. n*n 크기의 대나무 숲이 주어지고, 대나무가 더 많은 방향으로만 이동이 가능하다. 한 Cell당 하루를 살 수 있고 최대한 살 수 있는 기간을 구하기 때문에 DFS를 사용해야 한다는 것을 알 수 있다. 그리고 매 지점마다의 최대 값을 구하는 것 보다 이미 지나간 지점의 값을 저장해 놓는 것이 효율적이기 때문에 DP를 활용한다. 소스 코드 from sys import stdin, setrecursionlimit setrecursionlimit(10 ** 6) readline = stdin.readline N = int(readline()) dp = [[0] * N for _ in range(N)] _map = [[0] * N for _..

45656과 같이 모든 자릿수가 1씩 차이나는 수를 계단 수라 정의하고, 주어진 N자리 수의 총 계단의 수를 파악하는 문제이다. N의 수는 N-1의 1의 자리 수 +- 1을 1의 자리 수에 추가하는 규칙을 가지고 있다는 것을 발견하고 나열 하면 아래와 같이 나타난다. N=1 1, 2, 3, 4, 5, 6, 7, 8, 9 N=2 10, 21, 32, 43, 54, 65, 76, 87, 98 12, 23, 34, 45, 56, 67, 78, 89 .... 위와 같이 나열하다 보니 아래와 같은 점화식을 도출해 낼 수 있었다. N = 짝수 2 * D[i-1] - (i-1) N = 홀수 2 * (D[i-1] - (i-2)) 하지만 적절한 점화식이 아니었고 다른 분의 풀이를 참고하였다. 1의 자리수 N 0 1 2 ..

n개의 동전이 주어지고 최소한의 동전을 합하여 k원을 만드는 문제이다. 그리디, 동적 프로그래밍 두 가지 접근 방법이 가능하나, 나는 그리디 알고리즘 밖에 떠올리지 못하였다. 그리디 우선순위 큐를 가지고 그리디 알고리즘을 사용하면 메모리초과가 발생할 수 있다. 우선순위 큐에 들어갈 수를 직접 작성해보면 중복된 수 가 상당히 많이 삽입되기 때문에 이미 만들어진 합을 제외하면 메모리 초과를 해결 할 수 있다. 동적 프로그래밍 사실 이 문제는 동적 프로그래밍으로 분류되는 문제이기 때문에 그리디 풀이법이 출제자가 의도한 것은 아닐 것이다. 동적 프로그래밍으로 해결하기 위해서는 점화식을 만들 수 있어야한다. 어떤 n 원을 만들기 위해서는 임의의 m원에서 주어진 동전 중 하나를 더해야 한다. n원을 만들기 위해 사..

일렬로 놓여 있는 포도주를 마실 수 있는 최대의 양을 구하는 문제 DP로 풀이가 가능하다. 규칙은 아래와 같다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 위 규칙에 따르면 포도주를 마실 수 없는 경우가 나타나는데 이를 3가지로 나눌 수 있다. 1. 현재 포도주를 마시지 않는다. 2. 이전의 포도주를 마시지 않는다. 3. 2번째 이전의 포도주를 마시지 않는다. 이 세 가지 경우를 각각 적어도 하나만 만족한다면 위 2가지 규칙을 만족한다. 소스 코드 파이썬 from sys import stdin readline = stdin.readline N = int(readline()) wines ..

카드를 조건에 맞게 제거하여 최대 점수를 구하는 문제이다. 문제 해결에 가장 중요한 규칙은 아래와 같다. 언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다. 오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에는 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다. (1)과 (2)의 규칙에 따라 게임을 진행하다가 어느 쪽 더미든 남은 카드가 없다면 게임이 끝나며 그때까지 얻은 점수의 합이 최종 점수가 된다. 처음 문제를 접할 때는 최대 점수를 구하기 때문에 그리디 방식으로 접근했다. 하지만 카드 뭉치가 소멸하는 순서가 점수와 관련이 없기 때문에 반복문을 전부 다 돌아..

최소한의 횟수로 빨간 구슬을 구멍으로 빼내는 문제이다. '최소한'이라는 단어에서 BFS를 사용해야 한다고 생각 해냈다. 하지만 구슬이 움직이는 방법에 대해서 고민하다 시도 조차 하지 못하고 포기했다. 다른 분들이 작성한 문제 해결 방법 참고하였다. 각각의 공은 동시에 움직이지만 겹쳐질 수 없다. 파란공이 구멍에 빠지면 반드시 실패한 것이다. 동시에 빠져도 그러하다. 다음 움직임은 공이 더이상 이동할 수 없을 때 가능하다. 움직임이 10회가 초과하면 실패한 것으로 간주한다. 알고리즘 진행 중 빨간공과 파란공의 위치가 겹쳐지게 되는 경우 각 공의 이동 횟수를 구해서 더 큰 쪽이 늦게 도착했기 때문에 이전 상태로 되돌린다. 파란공이 먼저 혹은 동시에 구멍에 빠질 경우 무시한다 공을 이동시킬 경우 벽에 부딪혀 ..

문제 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B의 인덱스는 1부터 시작한다. 입력 첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, N2)보다 작거나 같은 자연수이다. 출력 B[k]를 출력한다. 접근 방법 해결하지 못해 다른 분이 작성하신 접근 방법을 참고하였다. 문제를 보고 가장 먼저 N*N 배열을 만들고 오름 차순 정렬하는 것을 생각할 수 있다. 하지만 이러한 방법을 사용할 경우 O(N^2) 시간이 걸리기 때문에 매우 비효율 적이고 메모리도 많..