빠르고 꾸준하게

자료구조 & 알고리즘/백준(Baekjoon)

[백준]2343(파이썬) - 기타레슨

https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 이 문제는 정말 어이없는 실수로 꽤나 시간을 쏟았던 문제입니다.. 해설을 하면서 말씀드리도록 하죠. 처음 봤을 때 생각은 '뭔가 기준점이 있어야 하고 그 기준점은 조건에 따라 달라질 수 있다.... 그렇다면 이분 탐색이겠구나'였습니다. 이분 탐색에서 가장 핵심은 이분탐색풀이에서의 mid 값을 뭐로 설정하느냐? 라고 저번 이분탐색 포스팅에서 언급한적이 있는데요, 이번에도 무엇을 mid로 둘 것이냐를 생각하..

자료구조 & 알고리즘/백준(Baekjoon)

[백준]18405(파이썬) - 경쟁적 전염

https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 이 문제는 94퍼센트 정답률 까지는 10분 안에 풀었지만 나머지 반례를 찾지 못해서 꽤 시간이 걸린 문제입니다.. 나머지 6퍼센트가 어느 부분에서 잘못 되었는지는 파악이 되었습니다. 바로 1초가 지난 후 시험관의 상태를 체크할 때, 어떻게 체크할 것이냐의 문제였던 것 같은데요, 제가 처음 풀었던 풀이에서 어디가 잘못되었는지 아시는 분은 댓글 부탁드립니다ㅠㅠ 결국에는 ..

자료구조 & 알고리즘/백준(Baekjoon)

[백준]11000(파이썬) - 강의실 배정

https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 이 문제는 맨 처음 dictionary를 이용해서 구현해서 몇 개의 테스트 케이스는 통과했지만, 도저히 시간 초과를 해결할 수 없어서 결국 어떤 유형의 문제인지 봤습니다. 최소 힙 이라니... 생각지도 못했네요. 하지만 곰곰이 생각해보니까 이거 여기서 시간 초과 났을 게 분명한데... 했던 부분을 최소 힙으로 풀어낼 수 있었던 것 같습니다. 이 문제의 핵심은 빨리 시작하는 수업 부터 순서대로 비교하고, 그 수업의 끝나는 시간과 다음으로 빨리 시..

자료구조 & 알고리즘/백준(Baekjoon)

[백준]12685(파이썬) - 평범한 배낭

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 이제는 문제를 읽었을 때, 어떻게 풀어야 하는지 방향성에 대한 확신이 약 80프로 정도 생긴 것 같습니다. 100프로 확신이 될 때까지 문제를 많이 풀어봐야겠군요. 이 문제를 읽고 나서는, 무조건 DP 문제인데,,, 많이 본 문제 유형이긴 한데 제가 한 번에 떠오르는 방식으로는 구현할 수 없었습니다. 처음에 접근할 때 주어진 물건들..