왜 필요할까? C#에서 우선순위큐(Prirority_Queue)는 NET 7에 새로 생겼다. 이게 문제가 되는 이유는 대표적인 알고리즘 풀이 사이트(백준, 프로그래머스)가. NET 7 하위 버전이다. 즉, C#으로 알고리즘을 풀 때 우선순위 큐를 사용할 수 없다는 소리다. SortedSet SortedSet에 대해 자세히 다루는 포스팅은 아니기 때문에 우선순위 큐 구현에 필요한 핵심만 말하겠다. SortedSet은 내부의 요소가 자동적으로 정렬된다. 이때 중복 요소는 허용되지 않는다. 원시타입(string, int) 같은 경우, 정렬 기준을 만들지 않으면 자동으로 오름차순으로 정렬되지만 컬렉션, 배열 등은 무조건 IComparable 혹은 IComparer를 통해 정렬 기준을 만들어야 한다. Sorted..

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/118669? 여러 출입구, 쉼터, 산봉우리로 왕복하는 코스 중에서 intensity가 최소인 것을 찾는 문제. 문제 핵심 및 풀이 왕복? 같은 출입구에서 시작하여 산봉우리를 찍고 다시 돌아오는 것이다 .그리고 갔던 길을 다시 가도 된다. 그래서 말이 출입구 - 산봉우리의 왕복이지, 사실상 편도로 계산해도 된다. 왜냐하면 최소의 intensity를 찾았다면, 그 경로 그대로 다시 내려오면 되니까.. 예를 들어, 출입구가 1이고, 4번이 산봉우리라고 하자.1번 출입구에서 4번 산봉우리까지 도착하는데 줄일 수 있는 intensity가 3이라고 하면 어떤 경로 (1 - a - b - 4) 이런 식..

문제 이해 단계 https://school.programmers.co.kr/learn/courses/30/lessons/136797 입력으로 눌러야 하는 숫자가 순서대로 주어지고, 왼손과 오른손 엄지를 가지고 숫자를 눌러야 한다. 각 숫자를 누를 때마다 가중치라는 비용이 드는데 이는 위치에 숫자의 위치에 따라 달라진다. 조건은 아래와 같다. - 이동하지 않고 제자리에서 다시 누르는 것 → 가중치 1 - 상하좌우 인접한 숫자로 이동 → 가중치 1 - 대각선으로 인접한 숫자로 이동 → 가중치 1 - 같지 않고 인접하지 않은 숫자를 누를 때 → 위 규칙을 따라 가중치 합이 최소가 되는 경로 처음에 왼손은 4번, 오른손은 6번에서 시작한다. 이때, 나올 수 있는 가중치의 최소합을 구하는 문제 입력으로는 숫자만 ..

문제 이해 단계 https://school.programmers.co.kr/learn/courses/30/lessons/68646 인접한 풍선 2개를 선택해서 둘 중 하나를 터트리는 행동을 풍선이 최종적으로 1개 남을 때까지 반복한다. 두 풍선 중 번호가 더 작은 것을 터트리는 행동은 최대 1번밖에 할 수 없다. 즉, 횟수 제한이 없는 것은 두 풍선 중 번호가 더 큰 풍선을 터트리는 행동이다. 그리고 최후까지 남을 수 있는 풍선의 개수를 구한다. 문제 접근 단계 제한 사항에서 얻을 수 있는 정보 제한 사항부터 살펴보자. 일단 배열의 길이, 그러니까 풍선의 개수는 최대 1,000,000개까지 가능하다. 이게 뜻하는 바는, 시간복잡도가 O(N^2)까지 가면 10^12이므로 10초가 훌쩍 넘어버린다. 그러니까..

문제 이해 단계 https://school.programmers.co.kr/learn/courses/30/lessons/92343? 이진트리가 있는데, 각 노드에는 양(0) 또는 늑대(1)가 있다. 무조건 루트노드에서 출발하여 양을 획득해야 한다. 루트 노드는 항상 양이다. 획득하는 과정에서 양의 수가 항상 늑대 수보다 많음을 유지해야 한다. 최대한 많은 수의 양을 모아서 다시 루트 노드로 돌아올 때 모을 수 있는 최대 양의 수를 구하는 문제 문제 접근 단계 제한 사항 파악 제한 사항부터 보면 노드(info)는 최대 17개까지이다. 이에 따라, 항상 이진트리를 유지하기 때문에 간선(edges) 또한 100개가 넘어가지 않는다 즉, 완전 탐색이 가능할 만큼 탐색할 범위가 작음을 알 수가 있다. 움직이는 경..

하노이의 탑(Tower of Hanoi) 문제란? 유례나 역사 같은 것은 다 생략하고, 문제의 조건 같은 본론부터 바로 말하겠다. 3개의 기둥과 이 기둥에 꽂을 수 있는 다양한 크기에 원판들이 존재한다. 맨 처음 시작할 때, 원판의 크기가 큰 것부터 1번 기둥에 모두 쌓는다. 맨 왼쪽 기둥부터 순서대로 1번, 2번, 3번 기둥이라고 한다. 문제에서 요구하는 것은 아래의 조건을 만족하면서, 1번 기둥에 쌓여있는 모든 원판들을 3번 기둥으로 옮기는 것이다. 조건 1. 한 번에 하나의 원판만 옮길 수 있다. 2. 큰 원판이 작은 원판 위에 있어서는 안 된다. N개의 원판이 최소 경로로 이동할 때의 경로를 출력하라는 것이 문제에서 요구하는 것이다. 이 문제를 왜 알아야 할까? 중요한 것은 학습의 목적이다. 프로..

문제 이해 단계 https://school.programmers.co.kr/learn/courses/30/lessons/12904? 팰린드롬이란 앞뒤를 뒤집어도 똑같은 문자열을 뜻한다. 입력으로 문자열 s가 주어질 때, s의 부분 문자열 중에 가장 긴 팰린드롬의 길이를 구하는 문제 문제 접근 단계 제한사항부터 살펴보자. 문자열의 길이 s는 2,500 이하의 자연수이고, 알파벳 소문자로만 구성되어 있다. 팰린드롬이라는 좌우대칭 규칙성을 판단할 때는 보통 스택을 사용한다. 이 문제에서 사용하려고 했는데, 각 자리마다 스택을 사용하여 넣었다 뺐다 하는 것은 굉장히 비효율적이다. 그리고 예전에 백준 포스팅에서 이런 유사한 문제를 다룬 적이 있다. https://howudong.tistory.com/319 [C+..

문제 이해 단계 https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS는 두 수열이 주어졌을 때, 두 수열의 공통이 되는 부분 수열 중 가장 긴 것을 찾는 문제이다. 가장 긴 수열의 길이를 출력하고, 둘째 줄에 LCS를 출력한다. LCS가 여러 가지일 경우엔 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄은 출력하지 않는다. 문제 접근 단계 LCS 길이 구하기 [C++] 백준 9251 ..