Algorithm/백준

[백준] 1012. 유기농 배추 - 파이썬

https://www.acmicpc.net/problem/1012 풀이 [백준 3197 - 백조의 호수], [백준 7569 - 토마토] 문제와 유사했던 문제. 마찬가지로, BFS를 이용해 풀이. 배추밭을 2차원 배열로 초기화, 이후 입력된 배추의 좌표를 가지고 2차원배열에 적용. 매 반복마다, 배추가 없는 지 확인. 배추가 있다면, 제일 먼저 발견된 배추를 Queue에 넣고, 먹어치워진 배추의 상하좌우를 탐색하며 BFS를 이용해 탐색을 진행. 인접한 모든 배추를 처리하고 나서, 다시 다음 반복을 진행~ 복잡한 건 없어서 주석 이외 부가 설명은 필요하지 않은 듯.. ^ㅁ^ from collections import deque test_case_cnt = int(input()) # 결과값 저장 worms =..

[백준] 7569. 토마토 - 파이썬

https://www.acmicpc.net/problem/7569 풀이 [백준 3197 - 백조의 호수] 문제와 상당히 유사했던 문제. BFS를 이용해 풀이함. 주의할 점은, 토마토를 익히는 과정에서 한 번 익혀지고, queue에 들어간 토마토는 값이 이미 1이 되었기 때문에, visited나 queue에 이미 존재하는 지 확인할 필요가 없음. in 이나 not in 연산자는 O(N) 의 time complexity를 가지므로, for나 while문 안에서 남발했다가는 그대로 시간초과가 되기 쉽다. [백준 3197 - 백조의 호수] 보다 쉬웠던 점은, 토마토가 다 익었는지 확인하는 과정을 Brute-Force로 처리해도 되었음. 그러나 3차원 배열을 써야 하므로 index의 순서가 바뀌지는 않았는지 항상..

[백준] 2281. 데스노트 - 파이썬

https://www.acmicpc.net/problem/2281 풀이 DP (Dynamic Programming) 문제. 나는 기본적으로 DP는 bottom-up 방식으로 푸는 것을 선호하고, 풀이도 bottom-up 방식으로 먼저 생각해내곤 하는데, 이 문제는 잘 생각이 나지 않아 시도하다 다시 top-down 방식으로 선회한 문제. top-down 방식으로 푸는 것이 훨씬 구현하기 수월했다. 먼저 기저 상태를 0으로 설정하고, memoization을 활용해 이미 계산된 dp[index]가 존재하면 (maxNum으로 초기화했으므로, maxNum보다 작으면 값이 담긴 것) 그 값을 return. dp[index]는 index+1번째의 이름을 '새로운 줄' 에 작성할 때, 남은 공간들의 제..

[백준] 1107. 리모컨 - 파이썬

https://www.acmicpc.net/problem/1107 풀이 이것저것 여러 방법을 생각해 봤으나, 마땅한 수가 생각나지 않았음. 문제 조건에서 채널이 500,000개 정도였기 때문에 Brute-Force로 시도해볼 만하다고 생각해서 Brute-Force로 실행. 다만 0~500,000 까지의 수를 모두 대입해 보기보다는, 고장난 버튼을 염두에 두고, 조합 가능한 모든 6자리까지의 경우의 수를 미리 만들어 두고, 그 이후 처리하는 것이 속도 면에서 이득이다. # 100에서 움직일 때와 버튼을 누르고 움직일 때, 둘 중 최솟값을 채택 channels[ch] = min(abs(goal - 100), len(str(ch)) + abs(goal - ch)) 0 ~ 500,000 까지의 모든 수를 대입한..

[백준] 1655. 가운데를 말해요

[백준] 1655. 가운데를 말해요 - 파이썬 https://www.acmicpc.net/problem/1655 풀이 1 일단 첫 시도는, 최소 힙을 사용. 입력받은 수들의 리스트를 저장 후, 반복문을 돌릴 때 마다 리스트를 알맞게 slicing하여 heapify, 그리고 매 반복마다 pop 후 heapify를 2/n회(가운데 값을 찾을 때 까지) 반복하여 중간값을 찾도록 코드를 짰다. 결과는 시간초과. python에서의 heapify() 는 O(N)의 time complexity를 가지고, heappop(), heappush() 는 각각 O(logN)의 time complexity를 가지므로, 간단히 계산해 봐도 최소 O(N^2) 이상의 complexity이고, 그냥 생각나는대로 대충 시도해봤기 때문에..

[백준] 2437. 저울

https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 풀이를 생각해내기 쉽지 않았던 문제. 풀이 입력된 숫자 배열을 오름차순으로 정렬한 후 검사. 만약 [이전의 숫자들을 더한 결과 + 1] < [다음 숫자] 라면, 더해서 만들 수 없는 수가 생기게 됨. EX 1 - [1, 2, 2, 7, 9, 13, 15] 1+2+2 + 1 < 7 이므로 &#39;6&#39; 을 만들 수 없음 EX 2 - [1, 1, 4, 9, 13] 1+1 + 1 < 4 이므로 &#39;3..

[백준] 1700. 멀티탭 스케줄링

[백준] 1700. 멀티탭 스케줄링 - 파이썬 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 풀이 플러그를 새로 꽂을 때마다 경우의 수가 나눠지는데 플러그 자리가 남아 있을 때 꽂혀 있는 기기를 그대로 사용 플러그 하나를 빼야 함. 1, 2번은 그냥 처리하면 되고, 3번을 처리하는 방법이 문제다. Greedy하게 처리하자면, 앞으로 쓸 일이 없거나, 가장 나중에 사용할 기기를 빼는 것이 최선이므로, 그렇게 처리함. from collection..

[백준] 11000. 강의실 배정

[백준] 11000. 강의실 배정 - 파이썬 https://www.acmicpc.net/problem/11000 풀이 Greedy를 생각하며.. 힙을 이용해 품. 강의를 모두 순회하며 강의의 종료시간을 최소 힙에 집어넣는데, 최소 힙의 root(제일 빠른 종료시간) > 처리할 강의의 시작시간 이면 그대로 최소 힙에 처리할 강의의 종료시간을 넣고(강의실을 +1) 아니라면, 그 강의실에서 계속 강의해도 되니까 최소 힙에서 pop하고 다시 새로운 종료시간을 넣음. import heapq import sys read = sys.stdin.readline N = int(read().strip("\n")) lec = [list(map(int, read().strip("\n").split())) for _ in ra..