기록

문제 https://www.acmicpc.net/problem/2208 2208번: 보석 줍기 화영이는 고대 유적을 탐사하던 도중 보석을 발견했다. 유적 속에는 N(1 ≤ N ≤ 100,000)개의 보석들이 일렬로 놓여 있었다. 각각의 보석의 가치는 다를 수 있기 때문에, 화영이는 가급적 많은 이득 www.acmicpc.net 풀이 1) 연속 누적합 dp 우선, 보석의 개수를 신경쓰지 않고, 연속해서 얻을 수 있는 보석의 누적 가치합을 구한다. 이를 위해 세가지 경우를 고려한다. 이전 보석과 연속해서 줍는다. 이전 보석을 버리고, 현재 보석만을 줍는다. 아무 보석도 줍지 않는다. 2) M개 이상의 보석을 줍는다. prefix_sum 2-1. 현재 위치를 포함해서, 왼쪽으로 이동하면서 M개의 보석을 줍는다..

문제 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 풀이 분리집합 이미 같은 집합에 있는 원소(부모가 같은 원소)들이 언급되었다면, 사이클이 생긴 것이다. 코드 def find(n) : if parent[n]==n : return n parent[n] = find(parent[n]) return parent[n] def union(x, y) : x = find(x) y = find(y) if x

문제 https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 풀이 1) DFS def dfs(board, w) : if w>=5 : return max(max(board, key = max)) return max(solve(up(board), w+1), solve(down(board), w+1), solve(right(board), w+1), solve(left(board), w+1)) 2) 블록 오른쪽으로 밀기 각 행을 ..

문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net h..

문제 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 풀이 1) DFS 원점을 옮겨가면서 깊이 우선 탐색을 진행한다. 단순하게 dfs만으로 구현하면, 시간초과를 만나게 된다. 시간을 줄이기 위해 DP를 이용해야 한다. 2) DP 2차원 배열을 선언해 한번 방문한 노드는 다시 방문하지 않도록 처리하면, 시간을 줄일 수 있다. 3) 기타 매번 dfs를 while문을 쓰다보니, 재귀범위를 넓히는 것을 잘 잊어버린다. 자주 써봐서 익숙해지기..

문제 https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 풀이 DP 위치를 위, 오른쪽, 왼쪽으로 움직이면서 가장 큰 경우를 board에 저장한다. 1. 0번째 행의 경우, 오른쪽으로만 이동이 가능하다. 2. 1번째 ~ N-1번째 행까지, 오른쪽/왼쪽으로 이동이 모두 가능하다. 2-1. 왼쪽과 위쪽을 비교하여 구한 배열과 2-2. 오른쪽과 위쪽을 비교하여 구한 배열을 비교해 해당 위치에서 가질 수 있는 최대값을 board에 저장한다. 코드..

문제 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 풀이 최소 스패닝 트리 https://en.wikipedia.org/wiki/Minimum_spanning_tree Minimum spanning tree - Wikipedia From Wikipedia, the free encyclopedia Jump to navigation Jump to search Tree of smallest total weight through all vertices..

문제 https://www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 풀이 1) CCW 세 점의 방향성을 판별할 수 있다. 2) 두 선분이 교차 3) 두 선분이 일직선 코드 import sys input = sys.stdin.readline x1, y1, x2, y2 = map(int, input().strip().split()) x3, y3, x4, y4 = map(int, input().strip().split()) A, B, C, D = (x1, y1), (x2, y2), (x3, y3), (x4, y4) A, B..