상상쓰

https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 정렬을 이용하여 테이프를 붙이는 위치를 계속 변경하면서 최소 횟수를 구하는 문제로 쉽다. import sys N, L = map(int, sys.stdin.readline().split()) pipe = list(map(int, sys.stdin.readline().split())) pipe.sort() answer = 1 value = pipe[0] for i in range(1..

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 이 문제의 알고리즘 분류가 정렬 또는 우선순위 큐가 있어서 heapq 와 sort() 로 오름차순으로 정렬하였다. 작은 가방에 들어갈 수 있는 보석은 큰 가방에 당연히 들어가기 때문이다. 오름차순으로 가방에 넣을 수 있는 보석의 가격을 price 에 놓고 heapq 와 '-' 부호를 이용하여 절댓값이 가장 큰 가격을 answer 에 더한..

https://programmers.co.kr/learn/courses/30/lessons/70130 코딩테스트 연습 - 스타 수열 programmers.co.kr 교집합이 될 수 있는 원소의 index 를 가지고 스타 수열의 길이를 구한다. 스타 수열의 최대 길이를 구하려고 한다면 우선 교집합의 원소가 오른쪽에 오는 것을 우선으로 한다. 또한, 스타 수열의 항에서 교집합의 원소랑 아닌 원소랑은 가장 근접한 것을 우선으로 한다. 조건에 맞는 항을 구한 후, 항의 각 원소가 다르면 스타 수열의 길이가 2씩 늘어난다. from collections import defaultdict def solution(a): answer = 0 dic = defaultdict(list) N = len(a) for i in..

https://programmers.co.kr/learn/courses/30/lessons/42897 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 programmers.co.kr 프로그래머스 4단계 문제치고는 쉬운 문제였다. 원형이라 처음과 끝은 인접하므로 경우를 나눠서 생각했다. 1. 끝을 생각하지 않는 경우 : 1 번 부터 차례대로 인접하지 않고 N-1 번으로 갈 때 훔칠 수 있는 돈의 최댓값 2. 처음을 생각하지 않는 경우 : 2 번 부터 차례대로 인접하지 않고 N 번으로 갈 때 훔칠 수 있는 돈의 최댓값 동적 계획법으로 구현하여 1..

https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 재밌는 문제였다. 예를 들어 a1

https://programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 저번에 풀었던 '배달' 문제랑 비슷하다. 다익스트라 알고리즘을 이용하여 (s, 도작..

https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net '0' 또는 '1' 이 연속되는 집단의 개수 중 작은 것을 반환하면 된다. 얼마 전에 정규식을 배웠기에 한 번 써봤다. import sys, re S = sys.stdin.readline() answer = min(len(re.findall(r'1+', S)), len(re.findall(r'0+', S))) print(answer)

https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net (0, 0) 부터 시작하여 (N-3, M-3) 까지 비교하면서 더는 바꿀 수 없는 구간에 대해서 A[][] 와 B[][] 가 다르면 -1 을 반환한다. 예를 들면 0 열부터 M-3 까지 비교하여 다음 행 차례가 오면 비교했던 행에 M-2 열과 M-1 이 바꿀 수 없는 구간이다. N 이나 M 이 3보다 작으면 3*3 크기의 부분 행렬이 없으므로 같으면 0 다르면 -1 을 반환한다. 이 예외 때문에 계속 틀렸었다...

https://programmers.co.kr/learn/courses/30/lessons/60063 코딩테스트 연습 - 블록 이동하기 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 programmers.co.kr BFS 알고리즘으로 일어날 수 있는 조건을 주어 구현하였다. 각 조건마다 코딩하여서 조금 길다. 한 칸 이동이 예를 들면 가로로 긴 블록일 때 좌우로 한 칸의 움직임만 허용되는 건 줄 알았는데 문제를 자세히 읽어보니 위아래로 가능하여서 틀리는 이유를 찾는데 조금 애먹었던 문제였다. from collections import defaultdict, deque def solution(board)..

https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 간단하게 생각해보면 같은 부호끼리는 절댓값이 큰 순서대로 묶어서 계산해야 최댓값이 된다. 양수하고 음수를 묶어야 할 상황에는 묶지 말고 더하는 것이 최댓값이 된다. 주의해야 할 점은 1과 0이다. 1은 무조건 더하는 것이 최댓값이 된다. 그리고 0은 양수랑 남으면 더하는 것이 최대지만, 음수랑 남으면 묶어서 계산하는 것이 최댓값이 된다. 그래서 우선순위 큐를 이용하여 부호에 따라 담을 큐를 두 ..