dev-hunmin

programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr - 접근법 사람 한명이 지날 때 마다 배열의 각 요소가 1씩 감소된다. 그렇게 여러명이 지나가게 되면 결국 언젠가 그 요소는 0이 되고 그 돌을 무시하고 지나갈 수 있는 최대 거리는 k로 주어진다. 즉 사람이 지나갈 때 마다 배열의 각 요소가 1씩 감소되고 결국 0이 되어버린 돌들을 다음 사람이 0이 된 돌들을 최대 k개 만큼 무시하고 지나갈 수 있는 최대 사람 수를 구하는 것이다. 가장 쉽게 생각할 수 있는 방법은 사람1명부터 +1하면서 못지나갈때까지 탐색하는 것인데 각 배열의 원소값이 ..

programmers.co.kr/learn/courses/30/lessons/68937 코딩테스트 연습 - 트리 트리오 중간값 5 [[1,5],[2,5],[3,5],[4,5]] 2 programmers.co.kr - 접근법 이 문제에서 가장 중요한 것은 중간값의 의미를 평균값으로 오해한다면 자칫 문제가 더 어려워진다.. 문제의 예시에서 나오는 세 값중의 중간값, 즉 정렬된 값 A,B,C가 있다면 중간값은 B이다. 따라서 각 A,B,C의 값은 정점(A,B,C)가 있다면 (A-B거리, A-C거리, C-B거리) 이다. 또 여기서 주어지는 값은 트리를 형성한다. (사이클이 없다, 간선의 수는 정점의 수-1) 그렇기 때문에 각 정점 사이의 경로는 '유일' 하다. 위 조건들을 가지고 다시 문제를 보면, 결국 답을 ..

programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[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 - 접근법 N(맵의 크기)이 25이므로 처음에 생각나는 풀이는 완전탐색 DFS 이다. 하지만 최단거리..

programmers.co.kr/learn/courses/30/lessons/12984 코딩테스트 연습 - 지형 편집 XX 게임에서는 지형 편집 기능을 이용하여 플레이어가 직접 게임 속 지형을 수정할 수 있습니다. 이 게임에서는 1 x 1 x 1 크기의 정육면체 블록을 쌓아 게임 속 지형을 표현합니다. 이때, 블록이 programmers.co.kr - 접근법 이 문제에서 만들 수 있는 테스트케이스(TC)에서 각 높이를 기준으로 블럭을 제거하고 새로 쌓아 얻은 추가비용들을 그래프화 시켜보면 유형은 크게 3가지로 나눌 수 있다.(x축이 높이, y축이 cost) 첫번째 경우처럼 최대높이에서 최소cost가 나오는 경우 (값이 계속 감소) 두번째 경우처럼 높이 0 에서 최소cost가 나오는 경우 (값이 계속 증가..

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 - 접근법 문제와 주어진TC를 통한 예시를 보면, 각 배열에 담긴 값(높이)이 동,서,남,북 인접한 배열에 담긴 값과의 차이가 주어진 height 이하이면 cost없이 통할 수 있다. 그러나 height 보다 큰 인접한 곳은 '사다리'를 설치해야만 지나갈 수 있다. 결국 cost가 소모되는 것은 사다리를 ..

programmers.co.kr/learn/courses/30/lessons/12927 코딩테스트 연습 - 야근 지수 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도 programmers.co.kr - 접근법 최종적으로 각 일 크기의 제곱들의 합이 가장이 작게 만들어야 하는 것이 이 문제의 목표이다.야근 1시간 마다 일 크기들중 하나를 -1 할 수 있다. 그렇다면 최종적인 목표의 답을 얻기 위해선 어떻게 해야할까?문제와 예시 데이터들을 보면, 결국 제곱들의 합을 작게 만들기 위해서는 일 크기들 중 큰 값들을 감소시켜야 한다.따라서 이 문제는 그리디를 적용시..

programmers.co.kr/learn/courses/30/lessons/17684 코딩테스트 연습 - [3차] 압축 TOBEORNOTTOBEORTOBEORNOT [20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34] programmers.co.kr - 접근법 단순한 구현 문제이다.문제에서 요구하는 조건과 데이터들을 처리할 로직 그리고 자료구조들을 생각하면서 구현하면 편할 것 같다.나의 경우엔 사전에 등록된 string과 색인번호들을 unordered_map에 저장하면서 처리했다. - 소스코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445#inc..

programmers.co.kr/learn/courses/30/lessons/1832 코딩테스트 연습 - 보행자 천국 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 - 접근법 이산수학에서도 단골로 나오고, 기본적인 DP문제로도 나오는 유형인 최단거리 수 찾기 문제이다. 이 문제는 기본적인 문제에서 조건 하나를 추가해서 살짝 꼰것 같은 문제지만 해결방법은 크게 다르지않다. 먼저 이 문제에서 도로의 유형은 0,1,2 로 주어지는데 0은 자유롭게 지나갈 수 있는 길, 1은 벽(못지나감), 2는 오는 방향으로부터 직진만 가능하다. (문제..