서론

코딩테스트 공부에 손놓은지 너무 오래됐다. 예전에는 다익스트라 관련 문제를 정말 좋아했고 잘 풀었는데 이제는 골드5문제 하나 풀기 힘들어졌다. 그래서 지금부터 잃어버린 다익스트라 감을 찾아보려고 한다.

전략수립

태그 검색으로 나열하고, 푼 사람수가 많은 것을 기준으로 풀어나가려고 한다.
너무 비슷한 유형을 제외하면서 골드5부터 골드1까지 5개씩 총 25개 풀 계획을 세웠다. 다익스트라 유형만 하루 1개 이상씩 풀어서 9월 15일까지 감을 찾아보겠다!

골드5

골드5는 활용이 전혀 없을거라고 생각해 다른 풀이를 찾아보기보단, 감찾기 용으로만 풀어보려고 한다.

(8/18) 1584 게임

2차원 배열을 사용하는 간단한 다익스트라 문제다. 예전이면 빠르게 풀었겠지만 거의 2달만이라 시간이 오래걸렸다.

(8/19) 1916 최소비용 구하기

정말 다익스트라의 정석이다. 처음 다익스트라를 공부하는 친구가 있다면 이 문제를 추천하고싶다.

(8/20) 5972 택배 배송

이것도 근본 다익스트라였다. 조금의 활용도 없는 그냥 다익스트라였당

(8/20) 11909 배열 탈출

배열을 돌아다니는 다익스트라 유형이었다. 문제를 잘못읽으면 실수할 수도 있었겠지만 그렇게 어렵진 않았다.

(8/21) 13549 숨바꼭질 3

그리디인가 했지만 너무 다양한 경우가 있다고 생각해 다익스트라로 풀었다. 풀이 자체는 어렵지 않음

골드4

골드4도 골드5와 큰 차이가 없고 별로 어렵지 않으니 한 2개정도만 풀고 넘어가면 될듯하다.

(8/21) 1261 알고스팟

(8/22) 1504 특정한 최단 경로

골드4는 활용도 없고 너무 재미가 없어서 골드3으로 바로 넘어가야겠다.

골드3

이번에도 재미가 없으면 바로 골드2로 넘어가려고 한다.

(8/22) 파티

풀어보니 활용도 없고 너무 재미가 없어서 바로 골드2로 넘어가겠다!

골드2

골드2부터는 dp도 같이 나오니 제대로 5문제정도 풀어보겠다!

(8/23) 네트워크 복구

최소 간선수를 가지면서 최단거리가 되도록 해야한다. 그냥 끝까지 다익스트라 돌리면 나올 것 같아서 해봤더니 됐다.

(8/27) 미확인 도착지

해당 간선을 지나왔는지를 체크하다가 실수를 했는지 계속 16%에서 안됐다. 반례도 못찾아서 2시간정도 풀이를 고집하다가 다른 풀이를 보고 외웠다. 짝수홀수 개념을 도입하니 참신했다.

(8/28) 인간 대포

아이디어 자체는 어렵지 않았다. 그냥 다익스트라 잘 하면 되는데... 실수해서 계속 삽질했다. 종이에 잘 적는 연습이 필요하다고 느꼈다.

(9/1) 집 구하기

아이디어는 어렵지 않았는데 잔실수때문에 많이 틀렸다. 제대로 설계했다면 실수하지 않았을 것 같아서 아쉽다.

골드1

시간도 잘 고려하면서 풀되, 너무 오랫동안 못풀면 다른 사람들 풀이도 참고하면서 풀어보려고 한다.

(9/2) 인터넷 설치

결정문제로 바꿔야한다는 걸 눈치채지 못하고 dp로 풀려다가 시간을 엄청 날려먹었다.
결정문제로 바꾸고, x값은 이진탐색을 통해 찾아내는 방법을 써야한다.

(9/14) 도로 검문

전부 다 돌리는 건 좀 아니라는 생각 + 아이디어 하나만 잘 찾으면 어렵지 않게 풀린다. 그냥 다익스트라 잘 돌리면 되는 것 같다.

(9/17) 전구를 켜라

구현느낌만 들어갔을 뿐 다익스트라를 돌리는 건 똑같다. 골드1이라기엔 좀 쉬운 것 같다.

(9/19) 달빛여우

dp가 필요한 다익스트라 문제인데, 그렇게 어렵진 않다

(9/25) 횡단보도

종이에 적으면서 어떤 값을 계산해야하는지 명확하게 정의하면 어렵지 않은 문제다! 범위값이 Int를 넘어가는지 여부는 항상 확인해야하는데 자주 까먹는다..

마치며..

프로젝트와 스터디 때문에 일정이 늦이졌지만 어느정도 감은 잡은 것 같다. 항상 꾸준하게 해야겠다!!