안녕

0. 문제 링크 https://www.acmicpc.net/problem/20366 20366번: 같이 눈사람 만들래? 높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1 다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1 www.acmicpc.net 1. 풀이 방법 투 포인터로 풀었음 (투 포인터로 안 풀어도 됨) 이를 위하여 눈덩이를 크기 순서대로 정렬하였음 우선 엘사의 범위는 for문을 이용하여 구하였음 엘사의 눈사람의 길이가 정해지면, 투포인터를 이용하여 안나의 눈사람의 길이를 구함 만약 엘사 > 안나라면 안나의 눈사람이 커져야 하므로 left += 1 하였음 만약 엘사 < 안나라면 안나의 ..

0. 문제 링크 https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 1. 풀이 방법 파이썬에는 우선순위 큐를 위한 모듈이 있음. 해당 모듈을 사용하면 최솟값 힙, 최댓값 힙을 구현할 수 있음 최솟값 힙, 최댓값 힙을 만들었음 여기서 생기는 문제점은 최솟값 힙에서 삭제한 숫자가 최댓값 힙에는 적용되지 않는다는 문제점임 따라서 최솟값 힙에서 삭제한 숫자를 따로 저장하는 딕셔너리를 만들었음. 최댓값 힙에도 마찬가지로 생성함 만약 최솟값 힙에서 숫자 ..

0. 문제 링크 https://www.acmicpc.net/problem/1045 1045번: 도로 0부터 N-1까지의 번호가 매겨져 있는 N개의 도시와 두 도시를 연결하는 도로가 있다. 도로에는 우선순위가 있는데, A와 B가 (A < B) 도로 x로 연결되어 있고, C와 D가 (C < D) 도로 y로 연결되어 있을 때, www.acmicpc.net 1. 풀이 방법 edge가 (a, b)가 있다면, a < b가 되도록 모든 간선을 우선순위 큐에 넣음 이때 모든 간선의 개수가 m보다 작다면 -1을 출력 크루스칼 알고리즘을 사용하여 mst를 만들었음 만약 mst가 만들어지지 않으면, 모두 연결되지 않는 것이므로 -1을 출력 크루스칼 알고리즘을 진행하는 도중에 쓸모없는 간선은 따로 관리함 이때 우선순위 큐로 ..

0. 문제 링크 https://www.acmicpc.net/problem/20442 20442번: ㅋㅋ루ㅋㅋ 어떤 문자열에서 몇 개의 문자를 지워서 부분 수열을 만들 수 있다. 예를 들어, ABC의 부분 수열은 ABC, AB, BC, AC, A, B, C와 빈 문자열이다. www.acmicpc.net 1. 풀이 방법 https://chanu-ps.tistory.com/24 우선 위의 블로그를 참고하였습니다. 맨 처음에 원포인터로 각 R의 위치에서 양 옆의 K의 개수를 세서 구하는 식으로 했는데, 예제랑 질문 게시판의 반례도 다 맞았는데도 1% 펑하길래 좀 힘들었습니다. 혼자 막 도전하다가 결국 구글링을 했는데, 위의 블로그가 매우 잘 정리해놓았습니다. 그래도 혹시 문제가 이해 안 간다던가 풀이가 이해가 ..

0. 문제 링크 https://www.acmicpc.net/problem/1414 1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선 www.acmicpc.net 1. 풀이 방법 일단 문제를 보고 나서 MST를 구하는 문제라는 것은 쉽게 알아차렸음. 아무 생각 없이 크루스칼 알고리즘을 짜고 예제를 돌리는데, 틀렸음 왜 틀렸는지 곰곰히 생각을 해봤음 생각해 보니까 이게 무방향 그래프인데, 두 개의 노드에 최대 두 개의 무방향 엣지가 연결되는 것이 가능함 그래서 무방향 엣지 중에 작은 애를 고르고, 걔를 우선순위 큐에 넣었음 그러고 나서 ..

0. 문제 링크 https://www.acmicpc.net/problem/6068 6068번: 시간 관리하기 성실한 농부 존은 시간을 효율적으로 관리해야 한다는 걸 깨달았다. 그는 N개의 해야할 일에 (1

0. 문제 링크 https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 1. 풀이 방법 일단 내가 푼 방식을 먼저 얘기하고 Two Pointer로 풀 수 있는 방법에 대해 얘기해 보자. 나는 일단 정렬 이런 거 안 했다. a, b, c, d가 있으니 a와 b를 합쳐서 ab, c와 d를 합쳐서 cd로 만들었다. 이때 cd를 Counter 객체로 만들었다. Counter 객체는 파이썬 내장 모듈이므로 한 번 찾아보면 될 것 같다. 아무튼..

0. 문제 링크 https://www.acmicpc.net/problem/2141 2141번: 우체국 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 1 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 1. 풀이 방법 해당 방법은 그리디여서 어떻게 풀지 생각이 좀 많았다. 인구가 가장 많은 곳을 기준 잡고, 그 다음 많은 곳을 향해 우체국 위치를 조정할까 이런 생각을 하다가 이건 최적을 보장하지 못한다는 생각이 들어서 그만뒀다. 음..이런 문제를 풀 때, 이게 최적이라는 보장이 있을까요? 그리디는 ..

0. 문제 링크 https://www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 1. 풀이 방법 첫 번째로 동전의 위치를 찾았다. 만약 동전이 둘 다 범위 안에 있다면, 무난하게 동전을 움직이게 했고, 만약 벽이라면 움직이지 않고 다시 현재 위치에 있게 했다. 그리고 다시 deque에 넣었다. 만약 동전이 둘 다 범위 바깥이라면, 둘 다 떨어졌다는 의미이므로, continue를 했다. 만약 한 개만 떨어졌다면 그대로 반환을 했음 하지만 해당 경우에 동전이 겹..

0. 문제 링크 https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 1. 풀이 방법 우선 0이 있다는 것은 +도 되고, -도 되므로 그냥 0이 n개 있으면, 0을 빼고 결과값에 2^n 만큼 곱해주며 된다. 아무튼 다른 숫자들은 2차원 배열을 만들어서 dp에 넣으면 된다. dp[가능한 숫자][현재까지 수행 횟수] 이런 식으로 하면, 최종적으로 원하는 숫자까지 가는데 만들 수 있는 등식의 수가 나온다. 항상 마지막에는 0의 개수만큼 2의 거듭제..