https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net dp문제는 왜인지 항상 블로그에 글을 쓰고 싶게 만든다. 처음 이 문제를 보면, 점화식을 만드는 규칙이 한 눈에 보이지 않아 무척 당황스러울 것이다. 하지만 연습장 하나 꺼내서 차근차근 손으로 계산하다보면 어떤 규칙이 눈에 띌 것이다 ! 그 규칙은 바로 삼각형이 정삼각형, 역삼각형 꼴을 반복하는 것이고, n번째 삼각형의 변의 길이 = 바로 직전의 삼각형의 변의 길이 + 직전 삼각형을 만드는데 쓰였던 삼..
https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 간단한 dfs문제이다. bfs로도 풀 수 있지만 dfs 연습중이라 그냥 dfs로 풀었다 무방향이므로 양쪽으로 모두 다 입력받아주고, 방문하지 않은 노드에 대해서만 dfs 탐색을 진행해준다. dfs 탐색이 끝난다면, 하나의 '연결요소'에 대한 탐색이 끝난 것과 동일한 것이므로 정답 개수를 +1 해주면 된다! import sys sys.s..
https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 기본적인 백트래킹 + 브루트포스 문제이다. 가능한 모든 경우의 수를 해보면서 최댓값을 찾으면 된다. 순열 구하는 문제와 동일하다. 만일 아직 백트래킹이 잘 이해가 되지 않는다면, 아주 작은 테스트 케이스를 하나 만들어서 직접 손으로 코드를 따라가보면 된다. 물론 당연히, 시스템 스택을 알고있어야 한다. import sys #sys.setrecursionlimit(10**6) input = sys.stdin.re..
https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 생각보다 까다로웠던 dp 문제이다. (사실 dp문제는 다 까다롭지만,,) dp[1], dp[2], dp[3]까지는 손쉽게 생각할 수 있다. dp[i]가 의미하는 바는 i번째 와인까지 마셨을 때 최대로 마실 수 있는 와인의 양이다. 1. 전전 와인 먹지 않고 전 와인과, 현재 와인 마시기 + 전전전 와인까지의 최댓값 2. 전 와인 먹지 않고 현재 와인 마시기 + 전전 와인까지의 최댓값 3. 전 와인까..
https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 백트래킹을 이용한 브루트 포싱이다. 단어의 앞뒤가 항상 anti, tica로 이루어져 있으므로 최소 5개의 글자 (a,c,i,n,t) 는 알고 있어야 한다. 그리고 이제 남은 알파벳 21개 중에서 추가로 학습을 진행한다. 이 때 알고 있는 글자의 수가 k개가 될 때 까지만 진행한다. 만약 depth가 k에 도달한다면, 입력으로 주어진 단어를 탐색하면서 모르는 글자가 나올 경우 탐색을 종료하..
https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net dfs 연습하기 좋은 문제이다. 우선 양방향 그래프이므로 입력을 양쪽에 모두 넣어주어야 한다는 것을 잊지말자! 그리고 숫자 하나씩 dfs를 돌려보며, 재귀의 depth가 4 (=> A-B, B-C, C-D, D-E 의 친구 관계) 에 도달할 경우 True 값을 주고 반환하면 된다. 단 한번이라도 도달하면 1을 출력해주면 된다. 주의할 점은, dfs에 들어가기 전 해당 숫자에 대해 방문 체크를 해주고 시작해야한다! import sys sys.setrecursionlimit(10**6) input = sy..
