전체 글
-
[백준 9081] 단어 맞추기 (Python)Algorithm & Problem Solving/구현(Implementation) 2021. 1. 22. 19:51
www.acmicpc.net/problem/9081 9081번: 단어 맞추기 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 하나의 단어가 한 줄로 주어진다. 단어는 알파벳 A~Z 대문자로만 이루어지며 항상 공백이 없는 연속된 알 www.acmicpc.net 문제풀이 단순 구현문제로, next_permutation 함수를 이용하여 쉽게 해결할 수 있다. 코드 import sys def next_permutation(a): i = len(a) - 1 while i > 0 and a[i - 1] >= a[i]: i -= 1 if i = a[j]: j -= 1 a[i - 1], a[j] = a[j], a[i - 1] j = len(a) - 1 while i <..
-
[백준 5002] 도어맨 (Python)Algorithm & Problem Solving/그리디 알고리즘(Greedy) 2021. 1. 22. 19:12
www.acmicpc.net/problem/5002 5002번: 도어맨 첫째 줄에 정인이가 기억할 수 있는 가장 큰 차이 X 현재 차례 사람 입장 - 그렇지 않을 경우, 다음 사람을 먼저 입장 시켜보기 => 남여 차이가 N보다 작아진다면 다음 사람 먼저 입장, 그렇지 않으면 종료 3. 1-2 과정을 반복한다. 코드 import sys if __name__ == '__main__': N = int(input()) arr = list(map(str, sys.stdin.readline().rstrip())) m_cnt, w_cnt = 0, 0 ans = 0 for i in range(len(arr)): # 남자 여자 차이가 N보다 작을 경우에는 바로 증가 if abs(m_cnt - w_cnt) < N: if ..
-
[백준 1202] 보석 도둑 (Python)Algorithm & Problem Solving/그리디 알고리즘(Greedy) 2021. 1. 22. 11:34
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 문제풀이 N, K : 입력값 arr, bag : 보석 정보, 가방 무게 idx : arr 리스트 인덱스 백준 2109 순회강연 문제풀이와 유사한 문제이다. 우선순위 큐를 이용해서 현재 가방 무게에서 가능한 가장 큰 값어치의 보석을 더하는 그리디 알고리즘 방식으로 해결할 수 있다. 1. 보석 정보 및 가방 무게 정렬하기 2. 각 가방에 대해서, 현재 가..
-
[백준 2109] 순회강연 (Python)Algorithm & Problem Solving/그리디 알고리즘(Greedy) 2021. 1. 22. 11:24
www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 문제풀이 N, arr : 입력값 hq : 우선순위 큐 idx : arr 리스트의 인덱스 우선순위큐를 이용한 그리디 알고리즘 문제이다. 가능한 가장 큰 시간인 10000일 부터 하나씩 내려오면서 해당 날에 가능한 가장 큰 돈을 더하는 방식으로 해결할 수 있다. 1. arr 리스트에서 d를 기준으로 역순으로 정렬하기 2. 가능한 가장 큰 시간인 10000일부터 1일까지 하나씩 줄..
-
[백준 11559] Puyo Puyo (Python)Algorithm & Problem Solving/그래프 이론(DFS & BFS) 2021. 1. 22. 01:27
www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 문제풀이 BFS를 이용한 구현문제이다. 주어진 조건만 잘 구현하면 쉽게 해결할 수 있다. 1. 뿌요 탐색 및 뿌요 부수기 - 현재 위치에서 동일한 색상의 뿌요가 4개 이상일 경우 뿌요를 부신다. 2. 1의 과정에서 없앤 뿌요가 있으면 뿌요를 내려준다. - 없앤 뿌요가 없으면 더 이상 진행할 것이 없으므로 결과를 바로 출력한다. 코드 보면 쉽게(?) 이해할 수 있다. 코드 import s..
-
[백준 1360] 되돌리기 (Python)Algorithm & Problem Solving/구현(Implementation) 2021. 1. 21. 01:55
www.acmicpc.net/problem/1360 1360번: 되돌리기 첫째 줄에 명령의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 명령과 수행한 시간이 주어진다. 항상 시간이 오름차순으로 주어지고, type c에서 c는 알파벳 소문자, undo t에서 t는 1보다 크거나 같 www.acmicpc.net 문제풀이 N : 입력값 cmd, ch, t : 입력값 q : 현재까지의 시간과 타이핑한 텍스트 저장 리스트 [(시간, 텍스트)] now : 현재 텍스트 따로 알고리즘이 필요없는, 그냥 문제에서 요구한대로 구현만 하면 해결할 수 있는 문제이다. 몇몇 예외 테스트케이스만 조심하면 쉽게 해결할 수 있다. 1. cmd가 type일 경우 - 현재 텍스트(now)에 ch 추가 - q에 시간(t)과 텍스트(no..
-
[백준 16947] 서울 지하철 2호선 (Python)Algorithm & Problem Solving/그래프 이론(DFS & BFS) 2021. 1. 20. 17:07
www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 문제풀이 N : 입력값 adj_list : 양뱡향 인접리스트 check : 노드 방문 여부 체크 dist : 최소 방문 거리 DFS를 통해 사이클을 찾고, BFS를 통해 특정 노드에서 사이클 까지의 거리를 계산하는 방식으로 해결할 수 있다. check를 통해 방문한 노드(check[x] = 1), 방문하지 않은 노드(check[x] = 0), 사이클에 속한 노드(check[x] = 2..
-
[백준 17615] 볼 모으기 (Python)Algorithm & Problem Solving/그리디 알고리즘(Greedy) 2021. 1. 19. 20:41
www.acmicpc.net/problem/17615 17615번: 볼 모으기 첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주 www.acmicpc.net 문제풀이 N, arr : 입력값 red, blue : N에서 'R', 'B' 의 개수 ans : 최소 이동 횟수 cnt : 좌측, 우측의 연속된 색상의 개수 생각보다 까다로운(?) 문제였다. 그리디(Greedy) 알고리즘 문제로, 가장 좌측에서 연속된 색상의 개수, 가장 우측에서 연속된 색상의 개수, 더 적은 색상의 개수를 구하고 이 중 최소값을 출력해야 한다. 1. 각 색상의 개수..