코딩기록

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이 문제는 전형적인 LCS 문제입니다. LCS 개념과 푸는 방법만 알면 쉽게 풀 수 있습니다. 먼저 두 문자열을 담은 2차원 리스트를 만듭니다. 그리고 문자 하나씩 비교해가면서 최장 수열의 개수를 세면 됩니다. 최장 수열의 개수를 세는 방법은, 문자가 같은 경우 -> dp[i][j] = dp[i-1][j-1] + 1 (글자가 추가 되기 전 최대 길이 +..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 이 문제를 풀기에 앞서 이분 그래프의 개념을 알고 가야 한다. 이런 식으로 정점의 색깔을 바꾸어 칠하면서 같은 색끼리 간선이 없는 경우 이분 그래프이다. 간선이 있다면 이분 그래프가 될 수 없다. 이것을 코드에 적용하면 문제를 풀 수 있다. 코드에서는 색상을 숫자로 표시하였다. (예 - 파랑은 1로, 빨강은 -1로) from collections import deque import sys inpu..

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net import copy N, M = map(int, input().split()) graph = [list(map(int, input().split())) for _ in range(N)] dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] direction = { 1: [[0], [1], [2], [3]], 2: [[0, 2], [1, 3]], 3: [[0, 1], [1..

https://www.acmicpc.net/problem/21314 21314번: 민겸 수 민겸 수 하나가 주어진다. 민겸 수는 대문자 M과 K로만 이루어진 문자열이며, 길이는 3,000을 넘지 않는다. www.acmicpc.net MK일 경우 최소값은 15, 최대값은 50이 된다. MMK일 경우 최소값은 105, 최대값은 500이 된다. MKMM일 경우 최소값은 1510, 최대값은 5011이 된다. 이제 규칙을 알 수 있다. ▶ 최소값의 규칙 = K로 끝날 때마다 10 ** (K가 나오기 전 M의 개수) + 5 를 추가한다. M으로 끝날 때 10 ** (M의 개수 - 1) 를 추가한다. ▶ 최대값의 규칙 = K로 끝날 때마다 5 * (10 ** (K가 나오기 전 M의 개수)) 를 추가한다. M으로 끝날..

https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net N, K = map(int, input().split()) nums = list(input()) k, stack = K, [] for i in range(N): while k > 0 and stack and stack[-1] < nums[i]: # 앞에 숫자가 해당 숫자보다 작을 경우 지운다 stack.pop() k -= 1 stack.append(nums[i]) print(''.join(stack[:N-K])) # K개를 지우지 못하는 경우를 위해 인덱스 슬라이싱을 해준다..

https://www.acmicpc.net/problem/1783 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제는 그리디 문제이다. 해결방법은 다음과 같다. [ 이동 방법 ] 2칸 위로, 1칸 오른쪽 1칸 위로, 2칸 오른쪽 1칸 아래로, 2칸 오른쪽 2칸 아래로, 1칸 오른쪽 1. N == 1 인 경우 - 위 아래로 움직일 수 없으므로 시작칸만 방문할 수 있다. 따라서 방문할 수 있는 칸의 수는 1이다. 2. N == 2 인 경우 - 위 아래로 1칸만 움직일 수 있으므로 2, 3번 방법만으로 움직일 수 있다. 가로가 아무리 길더라도 최대 3번 이상 움직일 수 없..

https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net N, C = map(int, input().split()) house = [int(input()) for _ in range(N)] house.sort() # 오름차순 정렬 low, high = 1, house[-1] - house[0] while low = cur + mid: cur = house[i] count += 1 if count >= ..

https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net import sys, heapq # 동서남북 dx = [0, 0, -1, 1] dy = [1, -1, 0, 0] count = 1 # 순서 def dijkstra(): queue = [] heapq.heappush(queue, (graph[0][0], 0, 0)) # 시작 노드 큐에 삽입 dist[0][0] = graph[0][0] while queue: cur_dist, x, ..

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 이 문제를 처음 보면 그래프 문제일 것이라고 쉽게 생각나지 않는다. 문제의 예시를 자세히 살펴보면 왜 이 문제가 그래프 문제인지 알 수 있다. 그 이유는 다음 그림을 참고하면 된다. from collections import deque F, S, G, U, D = map(int, input().split()) dist = [0] * (F+1) # 방문 확인 리스트 def bfs(start): queue = d..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net from collections import defaultdict import sys, heapq input = sys.stdin.readline V, E = map(int, input().split()) # 정점, 간선 개수 start = int(input()) # 시작 노드 graph = defaultdict(list) # 방향 그래프 dist = [sys...