개구리의 개발 블로그 개구리의 개발 블로그

문제 링크 - https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 석순과 종유석의 길이가 주어지면 석순과 종유석이 가장 적게 등장하는 구간을 찾는다. 1. 풀이 누적합 문제다. 석순과 종유석이 번갈아가며 주어진다는 점에서 힌트를 얻어서 석순과 종유석을 분리했다. 가장 처음 등장하는 원소는 석순이므로 down 배열에 0번째 원소부터 1개씩 건너 뛰며 저장한다. up 배열에는 1번째 원소부터 1개씩 건너 뛰며 저장한다. prefix배열에서 각 인덱스의 크..

백준 1092번 파이썬 문제 링크 - https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 그리디 알고리즘은 간단하다고 생각하고 최근에 많이 풀지 않았는데 까다로운 문제가 많았다. 처음에는 배와 크레인의 무게를 오름차순으로 정렬하여 그리디하게 할당했는데 반례가 있었다. 내림차순으로 정렬해야겠다는 구상을 했지만 코드로 구현하는 것도 쉽지는 않았다. 1-1. 풀이 박스 1개를 배치할 때 count를 1 늘려준다. count가 박스의 개수..

백준 10775번 공항 파이썬 문제 링크 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 한 번에 푼 문제는 아니지만 단계적으로 잘 풀어서 기분이 좋았다. 유니온 파인드를 이용해서 풀어야 하는 문제다. 처음에는 그리디하게 가능한 가장 번호가 큰 공항에 비행기를 배치했다. 새로운 비행기에 할당된 공항이 중복되면 기존에 있던 비행기는 왼쪽으로 한 칸씩 밀어서 배치가 가능하다. 이를 이중 반복문을 통해 구현했다. 1. 코드 (greedy, 시간 초과) # 공항 G, P = int(i..

백준 1765번 닭싸움 팀 정하기 파이썬 문제 링크 - https://www.acmicpc.net/problem/1765 1765번: 닭싸움 팀 정하기 1번 학생 혼자 팀, 2, 4, 6번 학생 셋이서 팀, 3, 5번 학생 둘이서 팀일 때, 팀의 개수가 최대이다. www.acmicpc.net union-find 문제는 해당 카테고리의 문제라는 것을 알고 있다면 쉽게 풀 수 있다. 하지만 문제를 보고 union-find로 풀어야겠다는 아이디어를 떠올리는 것은 어려울 수 있다. 팀을 만들어야 되는 문제이고 팀의 개수를 물어보았기 때문에 union-find로 풀면 될 것 같았다. 1. 풀이 팀을 만들기 위해 친구는 입력값을 받을 때 모두 union 한다. 원수인 경우 인접 리스트를 통해 서로 원수 관계인 것을..

백준 6987번 월드컵 파이썬 문제 출처 - https://www.acmicpc.net/problem/6987 6987번: 월드컵 월드컵 조별 최종 예선에서는 6개국으로 구성된 각 조별로 동일한 조에 소속된 국가들과 한 번씩, 각 국가별로 총 5번의 경기를 치른다. 조별리그가 끝난 후, 기자가 보내온 각 나라의 승, 무승부 www.acmicpc.net 제발 시간 복잡도 계산했는데 안되면 다른 방법을 생각하자. 처음에는 결과 배열 마다 따로 함수를 수행하지 않고 마지막 15 라운드에서 4개의 배열과 각각 비교하는 방식으로 풀었다. 결과 배열에서 -1을 하며 재귀를 수행하는 것이 아니라 0에서 부터 모든 경우를 구하기 때문에 가지치기를 할 수 있는 방법이 없다. 즉 시간 복잡도가 O(3**15)가 된다. (..

백준 2412번 암벽 등반 파이썬 문제 출처 - https://www.acmicpc.net/problem/2412 2412번: 암벽 등반 어떤 암벽에 n(1 ≤ n ≤ 50,000)개의 홈이 파져 있다. 각각의 홈의 좌표는 (x, y)와 같이 표현되는데, |a - x| ≤ 2이고 |b - y| ≤ 2이면 (x, y)에서 (a, b)로 이동할 수 있다. 이와 같이 홈들을 이용하여 이동 www.acmicpc.net 그래프 문제 하나 가볍게 푼다고 생각했는데 예상치 못하게 시간을 많이 소비했다. 알고리즘분석 수업에서 2차원 그래프에서 가장 가까운 두 점의 거리 문제를 다루었던 기억이 났다. 비둘기 집 원리로 접근했는데 이번 문제에서도 한 점에서 최대 25개까지만 방문할 수 있다는 점을 고려해서 문제를 접근했다..

2982번 국왕의 방문 파이썬 출처 - https://www.acmicpc.net/problem/2982 2982번: 국왕의 방문 지난주에 상그니 아라비아의 국왕 고둘라 창지즈 영사우드가 한국에 도착했다. 고둘라는 매우 중요한 사람이다. 따라서, 경찰은 그가 타고 있는 차량이 길에 진입했을 때, 그가 길에 있는 동안 www.acmicpc.net 로직은 쉽게 생각할 수 있는 다익스트라 문제였다. 다만 국왕이 도로를 점유하고 있는 상황을 표현하는 방법이 조금 까다로웠다. 메모리를 비효율적으로 사용하더라도 우선 풀어야겠다고 생각했다. 인접 행렬과 인접 리스트를 모두 사용하여 국왕의 위치를 표시했다. 1. 풀이 path[u][v]에 u에서 v로 국왕이 이동을 시작한 시간, 도착한 시간을 저장한다. 양방향 그래프..

2263번 트리의 순회 파이썬 문제 출처 - https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 문제를 처음봤을 때 접근 방법이 도저히 떠오르지 않아서 다른 문제를 풀다가 다시 시도했다. 트리의 노드를 여러 개 그려서 inorder과 postorder을 각각 써보면 규칙을 발견할 수 있다. 각각의 순회는 재귀적으로 표현할 수 있다. inorder - 왼쪽 서브 트리 / 루트 / 오른쪽 서브 트리 → 여기서 각각의 서브 트리도 다시 inorder이다. 즉 다음과 같이 표현할 ..