코딩테스트
[백준] 스도쿠
https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net dfs를 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 하다 만 스도쿠가 input으로 들어오면, 마저 끝내서 return을 해야 하는 문제입니다. 처음에는 시간초과가 나왔습니다. 처음 풀이 아이디어와, 나중에 어떻게 고치는지 순서로 설명을 해보겠습니다. 우선 이 문제를 보면, dfs를 사용해야 하는 것을 알 수 있습니다. 간단한 예시를 통해 아이디어를 살펴봅시다. 다음 그림과 같이..
[백준] 팰린드롬 분할
https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 다이나믹 프로그래밍을 두번 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 주어진 문자열에 팰린드롬 분할을 한 갯수의 최솟값을 출력해야 합니다. 처음에 두개의 다이나믹 프로그래밍중 하나만 이용하여 시간초과가 났었고 이후에 해결을 하였는데 각각 과정들을 한번 설명해 보겠습니다. (큰 아이디어에서 출발해서 수정을 한 부분의 아..
[백준] ACM Craft
https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 위상정렬과 DP를 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 다음과 같이 건물들을 건설하는 게임을 하는데, 특정 건물을 건설하면 반드시 승리하게 됩니다. 이 때, 건물들 간에는 우선순위(규칙)이 정해져 있습니다. 특정 건물을 짓는데 걸리는 최소 시간을 return 해야 합니다. 위 그림을 통해 간단하게 설명하면, 만약 4번건물을 짓는 최소시간을 구해야 한다면, 1->3&2->4 ..
[백준] N과 M (8)
https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net python의 itertools 라이브러리를 사용하는 문제입니다. 우선 문제부터 간단하게 요약하면, N개의 자연수중 중복을 허용해서 M개를 뽑을 때, 이 뽑는 경우들을 사전의 순서에 맞게 출력하면 되는 문제입니다. 단순하게 그냥 sequence를 미리 sorting 해주고, python itertools의 combinations_with_replacement를 사용하여 갯수만큼 뽑아내면,..
[백준] 공항
https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 그리디 알고리즘과 분리집합을 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 1~G번 게이트가 있는 공항에 비행기 P대가 옵니다. 이 때, 각 비행기는 숫자 gi를 가지는데 이 1
[백준] 외판원 순회
https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 다이나믹 프로그래밍과, bit masking을 이용하는 문제입니다. 우선 문제의 핵심부터 간단하게 요약하면, N개의 도시를 임의의 도시에서 출발해서 한번씩 전부 방문하고 원래 있던 도시로 돌아오는 최소 비용을 구해야하는 문제입니다. https://en.wikipedia.org/wiki/Travelling_salesman_problem Travelling sal..
[백준] N과 M (5)
https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net Permutation(순열)을 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, N개의 자연수가 주어질 때, 길이 M인 수열을 만들어 사전순으로 출력해야 하는 것이 문제입니다. 크게 어려운 점 없이 python의 경우 itertools libraray를 사용하여 permutations를 활용하면 됩니다. 이 때, 사전순 정렬을 위해 list를 미리 sorting 해주면 자동적으로 p..