SilentWalk

문제 가장 작은 부분문제를 떠올리는 부분이 생각보다 무척 어려웠다. 문제의 조건을 정리하면 아래와 같이 표현할 수 있다. 앞으로 숫자를 더 지워야 할 때 어떤 숫자의 앞에 그 숫자보다 작은 숫자를 두지 않는 것 이를 전개하면, 아래와 같은 로직을 만들 수 있다. 앞에서부터 계속 두 개의 숫자를 비교하여 앞의 숫자가 작으면 버리고, 아니면 취한다 하지만 문제 풀이를 떠올리는 과정에서 특정 상황별 대처 방법을 같이 떠올리고 추가하려고 하다 보니 자연스럽게 가장 작은 부분문제에서 멀어지는 문제가 발생하였고, Greedy한 풀이에서 자꾸만 멀어지는 모습을 확인하였다. Greedy 알고리즘 문제풀이 연습이 좀 더 필요할 것 같다. 코드 제출 후 다른 풀이를 찾아보니 굉장히 깔끔한 풀이가 있어서 이를 참고하여 코드..

풀이 과정 프림 알고리즘을 떠올리면 풀이를 쉽게 진행할 수 있다. 섬의 갯수가 1 이상, 100 이하로 주어졌으며 절대로 연결될 수 없는 섬은 주어지지 않는다고 하였으므로 시작지점을 임의로 0번 섬으로 지정하여도 아무런 문제가 없다. 기본적인 풀이의 진행방식은 아래와 같다. Edge의 cost에 대해 오름차순 정렬하는 Priority Queue를 준비한다. 현재까지 방문한 각 섬에 대하여 이하의 과정을 수행한다. 전체 edge에서 현재 선택중인 섬과 연결된 edge를 찾는다. 해당 edge의 다른 한 쪽 끝이 아직까지 방문하지 않은 섬과 연결되어있는지를 확인한다. 방문하지 않은 섬과 연결되어 있는 edge는 다음번에 설치될 다리가 될 가능성이 있으므로 1에서 준비한 Priority Queue에 추가한다...

문제 : https://programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 풀이과정 주어진 자동차 정보(출입지점, 이탈지점)을 이탈지점을 기준으로 오름차순으로 정렬한다. (단, 여기서 모든 차량은 한 방향으로만 진행한다는 가정이 있어야 한다.) 맨 앞 차량(가장 먼저 이탈하는 차량)이 카메라에 잡히기 위해서는 반드시 이 차량의 [진입 지점, 이탈 지점]의 범위 내에 단속 카메라가 설치되어야 한다. 여기서 가장 다른 차량과 동선이 겹칠 가능성이 높은 지점은 이 차량의 이탈지점이다. 그 이유는 이미 1에서 이탈지점을 기준으로 오름차순 ..

문제 이 풀이 및 코드는 2022년 3월 14일 재검토 시점에 오답으로 처리되고 있습니다. 풀이과정 주어진 문자열의 현재 위치(시작시 0)에서 가장 가까운 ‘A’가 아닌 문자의 위치를 찾는다. 해당 위치까지 이동할 때, 좌우 방향 중 더 적은 이동횟수를 센다. 해당 문자를 ‘A’로 바꾸기 위해 상하 방향 조작 횟수를 센다. 2와 3의 결과를 더한다. 해당 문자를 ‘A’로 교체한다. 더이상 ‘A’ 문자가 없을 때 까지 1~4 과정을 반복한다. 위 과정처럼 문제를 풀이했을 때 테스트 케이스 11, 13, 23, 25, 26에서 실패가 발생한다. 이에, 위 과정 중 2번 과정에서 좌우 방향 이동횟수가 같을 때 어느 한 쪽 방향에 대한 우선도가 존재하는지 확인 해 보았으나 별도의 우선도가 존재하지는 않는 것으로..

문제 : programmers.co.kr/learn/courses/30/lessons/42862 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr 먼저, 각 학생별 체육복 도난 및 여분 보유 여부를 정리한다. 각 학생들의 체육복 보유 수량을 나타내는 정수 배열을 선언하고 그 값을 모두 1로 초기화한다. (시작시점에는 모든 학생이 체육복을 가지고 있다.) 도둑질 당한 학생들의 번호에 해당하는 원소들에서 1씩 뺀다. 여분 체육복을 가지고 온 학생들의 번호에 해당하는 원소들에 1씩 더한다. 이후, 맨 앞 학생부터 차례..