빠르고 꾸준하게

자료구조 & 알고리즘/백준(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 문제인데,,, 많이 본 문제 유형이긴 한데 제가 한 번에 떠오르는 방식으로는 구현할 수 없었습니다. 처음에 접근할 때 주어진 물건들..

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

[백준]2206(파이썬) - 벽 부수고 이동하기

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 이 문제는 푸는데 정말 오래 걸린 문제입니다. 푸는 방법까지는 생각했는데 구현이 정답률 33프로 이상으로는 넘어가지 못했던 문제죠. 이 문제의 핵심은 벽을 한 번 부수고 이동할 때 어떻게 체크를 할 것인가? 입니다. 처음에 풀 때는 flag를 0,1 로 나눠서 1이 처음 나왔을 때 flag를 1로 바꿔주고 bfs로 구현을 했는데요, 이렇게 됐을 경우 아래와 같은 테스트 케..

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

[백준]21610(파이썬) - 마법사 상어와 비바라기

www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 이 문제는 2021 삼성 하반기 코딩테스트 문제입니다. 삼성 코딩테스트의 특징대로, 하나하나씩 주어진 조건에 따라서 구현을 해봤습니다. 이 문제에서 가장 오래 걸렸던 부분은 구름위치인 4칸을 각각 대각선 방향으로 옮길 때 어떻게 연결할 것인가 였습니다. 주어진 5 * 5 격자에서 여러 번 손으로 써보니까 규칙이 나왔고, 식을 구해서 대입했습니다. 아마도 다른 분들도 이 부분이 가장 까다롭지 않았나 싶습니..