[프로그래머스] 지형이동 (C++)
1.문제 programmers.co.kr/learn/courses/30/lessons/62050 코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr 2.풀이 1. 사다리가 없이 이동이 가능한 지형끼리 묶기 2. 같은 땅덩어리로 묶이지 않은 지형들 간의 거리 구하기 3. 사다리의 설치 최소 비용 구하기 나는 1번을 dfs 알고리즘으로 구현하였다. (bfs 도 상관없음) 2번은 벡터를 구조체로 선언하여 (from , to, dist)로 저장을한 ..
2021. 4. 12.
[프로그래머스] 징검다리 건너기 (Python)
1. 문제 programmers.co.kr/learn/courses/30/lessons/64062#qna 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 2. 풀이 이분탐색을 적용해서 풀어야했던 문제. stones 배열 각 원소들의 값은 1 이상 200,000,000 이므로 최대 2억명의 친구들이 건널 수도 있으므로 2중 포문을 돌리면 시간초과가 난다. 따라서, 우선 M번째 친구가 건넜는지 확인하기 위해 M-1번째까지 건넌 상황을 살펴본다. 모두 잘 건넜으면 (cnt = k) last = mid-1 해서 범위를 좁힌다. 모든 탐색을 마쳤으면 first를 반환 3..
2021. 4. 10.
[프로그래머스] 키패드 누르기 (C++)
1. 문제 programmers.co.kr/learn/courses/30/lessons/67256 코딩테스트 연습 - 키패드 누르기 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] "right" "LLRLLRLLRL" programmers.co.kr 2. 풀이 왼/오른손에서 가운데 숫자와의 거리를 구하는 방법이 관건이었던 문제! 공식(수식)을 세워서 풀었어야했다.. 이 부분을 어떻게해야할지 몰라서 검색해서 다른 사람들의 방법을 참고하였다. 초기 left, right의 값은 각각 10, 12로 설정해주어..
2021. 4. 10.
[프로그래머스] 쿼드압축 후 개수 세기 (C++)
1. 문제 programmers.co.kr/learn/courses/30/lessons/68936?language=cpp 코딩테스트 연습 - 쿼드압축 후 개수 세기 [[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]] [4,9] [[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]] [10,15] programmers.co.kr 2. 풀이 먼저 재귀로 풀어야겠다는 생각이 들었다. 하지만 어디서부터 어디까지 반복을 해야하지? 라는 생각이 들었고 결과적으로 각 좌표의 시작점마다 재귀함..
2021. 3. 30.
[프로그래머스] 게임 맵 최단거리 (C++)
🍒문제 programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr 🍒풀이 1. Queue를 사용하여 BFS로 구현 -> 최단거리 조건 2. dist 배열을 사용하여 지나온 거리 중 최단거리 갱신 3. 마지막 좌표 (n,m)에 도달하였다면 dist[n][m] 값 리턴 4. 마지막 좌표에 도달하지 못 하면 -1 리턴 🍒코드 #include #include #include #includ..
2021. 3. 23.
