WOONY's 인사이트

1. 점프(#2253) 처음에 떠올렸던 아이디어는 출발지점에서 중간 도착지점을 저장하는 방식으로 DP 테이블을 짜는 방식이었다. 예를 들어 1번 돌에서 10번 돌까지 간다고 하면 1번 (+1)=> 2번 (+2)=> 4번 => 7번 => 10번이니까 D[1][2] = 1, D[2][4] = 2, D[4][7] = 3, D[7][10] = 3 이렇게 해서 최종적으로 D[1][10] = D[1][2] + D[2][4] + D[4][7] + D[7][10] 이런 식으로. 그런데 점화식을 짜려니 뭔가 꼬이기 시작하더라..가장 관건은 속도였는데, 나는 속도를 dp 테이블에 value로 저장했으나 이를 어떻게 점화식으로 풀어내야 할지 감이 잘 오지 않았다. 결국 풀지 못하고 풀이를 검색해서 찾아봤다. 풀이에서는 속도..

오늘은 어제에 이어서 계속해서 이분 탐색 문제를 풀었다. 진도가 생각만큼 빠르게 나가지 않아 답답한 감이 없잖아 있다. 내일부터는 한 문제당 푸는 시간 30분 / 답지 보고 확인하는 시간 30분으로 시간 제한을 좀더 엄격하게 지킬 예정. 빠르게 후루룩 넘기고 다시 보는 게 낫지 하나하나 공들여서 공부하기에는 시간이 너무 부족하다. 1. 두 용액 두 용액 문제는 투포인터 알고리즘을 이용해 푸는 방식이다. 이진 탐색 카테고리에 두 용액 문제가 속해있어서 이진 탐색으로 풀어야 한다는 전제에서 문제를 접근하려니 어디에 mid를 잡아야 할지 도통 감을 잡지 못했다. 하지만 이 문제는 투포인터 알고리즘을 이용해 풀어야 한다는 점과 투포인터 알고리즘은 이분 탐색과 약간 다르다는 점을 알고 있어야 문제에 보다 수월하게..

0. 목차 1. Dynamic Programming (DP) 2. 외판원 순회 문제(TSP) 어제는 일요일이었기에 TIL을 생략하고 8일차 TIL을 업로드한다. 그렇다고 어제도 공부를 하지 않은 것은 아니었는데, 어제부터 시작해 오늘까지 하루종일 괴롭혔던 건 외판원 순회 문제(TSP)였다. 먼저 외판원 순회 문제에 대한 설명을 읽어보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지..