2021 KAKAO 채용연계형 인턴쉽 시험장 나누기
https://programmers.co.kr/learn/courses/30/lessons/81305# 코딩테스트 연습 - 시험장 나누기 3 [12, 30, 1, 8, 8, 6, 20, 7, 5, 10, 4, 1] [[-1, -1], [-1, -1], [-1, -1], [-1, -1], [8, 5], [2, 10], [3, 0], [6, 1], [11, -1], [7, 4], [-1, -1], [-1, -1]] 40 programmers.co.kr Naive한 방법에서 현재 풀이까지 생각하는데 많은 시간(2주)이 걸렸다. Naive한 방법은 간선을 끊어 모든 경우의 수를 탐색하는 방법이다. 이 방법은 정확성 Test에서는 합격을 받을 수 있겠지만, 효율성에서 받지 못할 것 같았다. 다음으로 생각한 방법은..
2020 KAKAO 인턴쉽 동굴 탐험
https://programmers.co.kr/learn/courses/30/lessons/67260 코딩테스트 연습 - 동굴 탐험 9 [[0,1],[0,3],[0,7],[8,1],[3,6],[1,2],[4,7],[7,5]] [[8,5],[6,7],[4,1]] true 9 [[8,1],[0,1],[1,2],[0,7],[4,7],[0,3],[7,5],[3,6]] [[4,1],[5,2]] true 9 [[0,1],[0,3],[0,7],[8,1],[3,6],[1,2],[4,7],[7,5]] [[4,1],[8,7],[6,5]] false programmers.co.kr 간선 정보로만 그래프 구성 이후, 선행 node -> 후행 node 간선도 추가한 뒤, 위상정렬을 시행한 뒤 node 가 남는지 확인하면 문제를..
2020 KAKAO 카카오 인턴쉽 경주로 건설
https://programmers.co.kr/learn/courses/30/lessons/67259?language=cpp 코딩테스트 연습 - 경주로 건설 [[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로만 접근하여 문제를 풀어서 맞췄다. 하지만, 현..
2021 KAKAO 채용연계형 인턴쉽 보석 쇼핑
https://programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 처음에는 naive한 방식을 생각하다가, 특정 영역 [a,b] 영역을 확인한 결과를 사용할 수 없을까라는 생각을 했다. 그래서 떠올린 방법이 2-pointer이다. end가 증가하면서 확인하는 것은, 보석 종류를 확인하고, 해당 보석 개수를 기록하는 것이다. 해당 보석 종류가 처음 등장하면 이를 기록한다. 처음 등장하지 않더라도 일단 해당 종류의 보석 개수를 기록한다. start가 2개이상 가지고 있는 보석을 ..
2021 KAKAO 채용연계형 인턴쉽 미로 탈출
https://programmers.co.kr/learn/courses/30/lessons/81304# 코딩테스트 연습 - 미로 탈출 4 1 4 [[1, 2, 1], [3, 2, 1], [2, 4, 1]] [2, 3] 4 programmers.co.kr 방문한 Trap을 bit로 관리한다는 생각을 떠올리니, 방탈출 문제가 생각났다. 그 문제풀이를 이 문제에 적용시켜보면 될 것 같았다. 대신 map 크기가 작아 완전탐색으로 풀었던 방탈출 문제 대신, 이 문제는 Vertex3 역뱡향 간선을 사용할 수 있게 설정하면된다. 나는 정방향 간선엔 0, 역방향 간선엔 1을 붙여 간선 방향을 구분했다. #include #include #include using namespace std; vector map; int c..
2021 KAKAO 채용연계형 인턴쉽 표 편집
https://programmers.co.kr/learn/courses/30/lessons/81303 코딩테스트 연습 - 표 편집 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO" programmers.co.kr 첫번째로 생각한 것은 Segment Tree + Binary Search이다. U X, D X 명령어는 현재 위치로 부터 임의의 위치 사이에 존재하는 살아있는 Node 개수를 알아야 구할 수 있다. 따라서 구간합을 Log n 만에 구할 수 있는 Segment Tree를 사용할 수 있다고 생각했다. 하지만, 문제는..
