[알고리즘] 캐시 (2018 카카오)
코딩테스트 연습 - [1차] 캐시 3 [Jeju, Pangyo, Seoul, NewYork, LA, Jeju, Pangyo, Seoul, NewYork, LA] 50 3 [Jeju, Pangyo, Seoul, Jeju, Pangyo, Seoul, Jeju, Pangyo, Seoul] 21 2 [Jeju, Pangyo, Seoul, NewYork, LA, SanFrancisco, Seoul, Rome, Paris, Jeju, NewYork, Rome] 60 5 [Jeju, Pangyo, S programmers.co.kr 예전에 카카오 연습문제를 찾아보다가 한 번 풀었봤던 기억이 있는데 그 당시엔 프로그래머스를 몰라서 프로그래머스에서 푼게 아니라 그냥 이클립스에다가 돌리고 나와있는 테스트 케이스만 돌려봤었..
2020. 9. 11.
[알고리즘] 징검다리 건너기 (프로그래머스 Level3)
코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 우선 stones 배열의 최대 크기가 20만이기 때문에 O(N) 시간 만에 처리를 해야 한다. Solution 친구들이 뛰어넘을 수 있는 길이는 K만큼이라고 했으니 어느 구간이라도 연속 K개의 돌이 0이 되는 순간 친구들은 더 이상 다리를 건널 수 없다. 즉 배열에 존재하는 K 길이만큼의 구간들 중, 각 구간마다 포함하고 있는 돌의 최댓값이 모든 구간들 중 최솟값이 되는 경우를 찾아야 한다. 이게 무슨 말이냐면 위의 예시 문에서의 K는 3이다. 해당 배열에서 길이가 3인 구간은 총 8개가 나온다. Start Index Finish Index Max Value 0 2 5 1 3..
2020. 9. 9.
[알고리즘] 경주로 건설 (2020 카카오 인턴십)
코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 일단 최소비용 + 최단거리 경로 탐색 문제이다. 여러가지 방법들로 풀던데 난 처음엔 dfs를 이용해서 브루트포스 방식으로 했다. 하지만 이 방식의 문제점은 depth가 깊어질수록 4방향으로..
2020. 8. 30.
