Algorithm (37) 썸네일형 리스트형 백준 1715번. 카드 정렬하기 해결방안가장 적은 두 값을 더하여 다시 넣는 행위를 반복하여 쉽게 해결할 수 있었다.시간 복잡도는 O(NlogN)이 나온다. 또 다른 방법으로는 2개의 큐를 이용하는 방법이 있다. 첫번째 큐: a는 cards 리스트를 정렬한 다음 만든 큐두번째 큐: b는 빈 큐 아래의 코드에서 보면 두 큐의 첫번째 원소끼리 비교하여 더 적은 숫자를 리턴하는데, a 큐에서는 이미 정렬된 상태이기 때문에 맨 앞이 가장 적은 숫자임을 보장한다.b 큐에서는 더한 값들을 순서대로 추가하는데, 이럴 경우 뒤에 더한 값들이 무조건 먼저 더한 값들보다 클 수 밖에 없다.따라서 b의 맨 앞이 가장 적은 숫자임을 보장한다. 이 경우도 힙과 마찬가지로 시간복잡도 O(NlogN)이 나온다. 정리일반적으로 가장 큰 원소를 뽑아내라? 이건 .. 우선 순위 큐(heap) 큐 : FIFO 구조로 들어온 순서대로(enqueue) 나가는(dequeue) 자료구조이다.우선 순위 큐 : 우선 순위가 높은 것이 먼저 나가는 자료구조이다. 우선 순위 큐를 구현하는 방법은 다양하지만 그 중 heap 이라는 자료구조에서 enqueue, dequeue하는 방법이 가장 시간이 적게 걸린다. heap완전 이진 트리 형태로 우선 순위 큐를 구현하기 위해 만들어진 자료구조이다. ✔ min heap(최소 힙)"부모 노드 ✔ max heap(최대 힙)"부모 노드 > 자식 노드" 인 완전 이진 트리 Enqueue와 Dequeuemin heap 자료구조를 바탕으로 설명하겠습니다. "우선 순위가 높다"는 것은 숫자가 더 작다는 의미 [Enqueue]1) 새로운 노드를 마지막 노드에 추가2) 부모 노드와 .. 백준 10971. 외판원 순회 2 문제모든 도시를 방문하고 다시 현재로 돌아오는 데 걸리는 최소 비용을 구해라[입력]첫 줄에는 방문해야할 도시의 수를 입력받는다.그 다음에 도시 사이를 이동하는 비용을 배열로 받는데, cities[i][j]란 i -> j 도시로 이동하는 데 드는 비용을 의미한다.[정리]모든 도시를 거쳐야 한다.한번 거쳤던 도시는 재방문할 수 없다.마지막 도시를 거친 후 처음 도시로 돌아가야하는 데, 걸리는 최소 비용을 구한다.문제 풀이도시의 수(N)가 10개 이하이다. 모든 도시를 방문했을 때도 10! 이기 때문에 1초안에 실행이 가능하다.따라서 백트래킹을 구현하였다. ⭐ key point!if value > ans 로 만약 모든 도시를 방문하지 않더라도 이미 결과 저장 값(ans) 보다 크다면 즉시 리턴을 통해 시간을 .. 백준 2178. 미로찾기 문제(1,1)부터 (N, M) 까지 가는 최소 칸의 수를 출력하는 문제이다.- 미로 바깥으로는 나갈 수 없다.- 0은 지뢰이므로 갈 수 없다. 문제 풀이기존 코드 - 미로를 탐색하기 위해 bfs를 사용했으며 visited라는 배열을 선언하여 visited[x][y] 까지 가는 데 지나친 칸 수를 저장했다.- 조건 1. 미로를 넘어간 경우 2. 지뢰인 경우 (map[x][y]가 0) - 여기서 방문 여부에 따라 다른 로직을 작성하였다. - 방문 안한 경우 : 작업 큐(q)에 추가하고, visited[next_x][next_y]에 이전의 칸 수 +1 저장 - 방문한 경우 : 새로운 길이 visited에 저장된 수보다 적은 경우, visited[next_x][next_y]에 이전의 칸 수 +1 로.. 하노이의 탑 목표시작(start) 기둥에 있던 정렬된 원판을 목표(end) 기둥에 정렬한다.문제 풀이종료 조건- n이 1일 때, start => end 기둥에 꽂는다. => answer 배열에 저장 기본 재귀 형식1. n -1 까지의 원판을 other 기둥에 꽂는다.2. n번 째의 원판을 start 기둥에서 end 기둥에 꽂는다. => answer 배열에 저장3. other 기둥에 있는 n -1 개의 원판을 end기둥에 꽂는다. https://school.programmers.co.kr/learn/courses/30/lessons/12946 이전 1 2 3 4 5 다음
