[Programmers] 블록 이동하기
문제 2020 KAKAO BLIND RECRUITMENT > 블록 이동하기 코딩테스트 연습 - 블록 이동하기 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 programmers.co.kr 아이디어 이번 문제는 평범한 BFS로 길 찾는 문제들의 심화 버전이라고 생각합니다. 로봇이 차지하는 공간이 2칸이어도 사방탐색을 하는 데는 어려움이 없었지만 회전하는 경우를 구할 때 말썽을 많이 부렸습니다. 초기 코드가 구현되었을 때는 회전하는 부분이 복잡하고 길었지만 구현하고 나서 생각을 다시 정리해보니 회전하는 경우를 판단할 때 매우 간단한 코드로 변경할 수 있었습니다. 생각한 방법에 대해 간단하게 설명드리겠습니다..
2021. 3. 20.
[Programmers] 자물쇠와 열쇠
문제 2020 KAKAO BLIND RECRUITMENT > 자물쇠와 열쇠 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 아이디어 이번 문제는 처음 접했을 땐 풀지 못하고 시간이 흘러 다시 접했을 때 풀게 된 문제였습니다. 풀이 방법은 단순히 회전을 하며 자물쇠를 열 수 있는 모든 경우를 찾는 완전탐색을 하면 되었습니다. 자물쇠는 고정 시키고 열쇠를 좌측 상단부터 우측 하단까지 옮기며 자물쇠를 열 수 있는지를 확인해주면 됩니다. 마치 2차원 배열을 탐색하는 것처럼요. 그림으로 나타내면 이런 모습이 나오겠습니다. 구현 코드 (Java) class Soluti..
2021. 3. 19.
[Programmers] 보행자 천국
문제 2017 카카오코드 예선 > 보행자 천국 코딩테스트 연습 - 보행자 천국 3 3 [[0, 0, 0], [0, 0, 0], [0, 0, 0]] 6 3 6 [[0, 2, 0, 0, 0, 2], [0, 0, 2, 0, 1, 0], [1, 0, 0, 2, 2, 0]] 2 programmers.co.kr 아이디어 이번 문제는 DFS/BFS를 이용하여 풀어야 되는 것처럼 보이지만 DP를 이용하여 풀어야만 하는 문제입니다. DP를 활용하는 방법은 간단합니다. city_map배열을 순회하면서 현재 위치에서 다음 위치(오른쪽, 아래)를 이동하는 경우를 생각하거나 또는 이전 위치(왼쪽, 위)에서 현재 위치로 오게 하는 경우를 생각하면 됩니다. 저 같은 경우는 현재 위치에서 다음 위치로 이동하는 경우를 활용하여 풀었습..
2021. 3. 14.
[Programmers] 합승 택시 요금
문제 2021 KAKAO BLIND RECRUITMENT > 합승 택시 요금 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 아이디어 이 문제는 문제를 보자마자 플로이드-워셜을 이용해야겠다는 생각이 났던 문제입니다. 왜냐하면 무지와 ..
2021. 3. 10.
[Programmers] 카드 짝 맞추기
문제 2021 KAKAO BLIND RECRUITMENT > 카드 짝 맞추기 코딩테스트 연습 - 카드 짝 맞추기 [[1,0,0,3],[2,0,0,0],[0,0,0,2],[3,0,1,0]] 1 0 14 [[3,0,0,2],[0,0,1,0],[0,1,0,0],[2,0,0,3]] 0 1 16 programmers.co.kr 아이디어 해당 문제를 처음 접했을 때 어떻게 풀지 막막했었습니다. 여러 생각을 하던 도중 아이디어가 생각나지 않아 질문하기 메뉴를 통해 아이디어를 찾다가 순열을 이용하신 분이 있는 것을 보고 어떻게 풀어내야 할지 아이디어가 생각난 문제였습니다. 코드는 짧지 않지만 풀이법은 생각보다 간단했습니다. 탐색할 카드들을 순열을 통해 순서를 정하고 키 조작 횟수를 최소화하며 순서대로 카드를 찾아 가기..
2021. 3. 7.
