[C++] 회장뽑기(플로이드 워샬) 🔥
·
algorithms (C++)
📄문제 월드컵축구의 응원을 위한 모임에서 회장을 선출하려고 한다. 이모임은 만들어진지 얼마 되지 않았기 때문에 회원사이에 서로 모르는 사람도 있지만, 몇 사람을 통하면 서로 모두 알 수 있다. 각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 된다. 예를 들어 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나, 친구의 친구임을 말한다. 또한, 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구이거나, 친구의 친구이거나, 친국의 친구의 친구임을 말한다.4점, 5점등은 같은 방법으로 정해진다. 각 회원의 점수를 정할 때 주의할 점은 어떤 두 회원이 친구 사이이면서 동시에 친구의 친구 사이이면, 이 두 사람은 친구사이라고 ..
[C++] 플로이드 워샬 알고리즘 ⭐
·
algorithms (C++)
플로이드-와샬(Floyd-Warshall) 알고리즘은 그래프 내의 모든 노드 쌍 간의 최단 경로를 찾는 알고리즘입니다. 특히 음수 가중치와 음수 가중치 사이클을 포함하는 그래프에서도 동작합니다. 플로이드-와샬 알고리즘은 동적 계획법(Dynamic Programming)을 기반으로 합니다. 플로이드-와샬 알고리즘은 음수 가중치와 음수 가중치 사이클을 다룰 수 있습니다. 물론 음수 가중치 사이클이 없는 경우에만 올바른 결과를 얻을 수 있습니다. 알고리즘의 시간 복잡도는 O(N^3)로, 노드의 수에 대해 세제곱 시간이 소요됩니다. 따라서 큰 그래프에서는 실행 시간이 길어질 수 있습니다. 결과 배열에는 모든 노드 쌍 간의 최단 경로가 저장되며, 노드 쌍 간의 최단 경로를 직접 액세스할 수 있습니다. 📄문제 N개..
[C++] 최대점수 구하기(냅색 알고리즘) 🔥
·
algorithms (C++)
📄문제 이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.) ⬇️ 입력 첫 번째 줄에 문제의 개수N(1 M; for (int i = 0; i > s >> t; // 각 문제당 한번씩만 푼다는 조건이 있기때문에 // for문을 M부터 t까지 역으로 돌아 현재 score에 대한 중복 적용이 없도록 구현 for (int j = M; j >= t; --j) { dp[j..
[C++] 동전교환 ⭐
·
algorithms (C++)
📄문제 다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다. ⬇️ 입력 첫 번째 줄에는 동전의 종류개수 N(1 coin[i]; cin >> m; // 적당히 큰 값으로 초기화 (INT_MAX)를 하면 오버플로우가 나옴 vector dy(m + 1, 1000); dy[0] = 0; for (int i = 0; i < n; i++) { int value = coin[i]; for (int j = value; j
[C++] 가방문제(냅색 알고리즘) ⭐
·
algorithms (C++)
📄문제 최고 17kg의 무게를 저장할 수 있는 가방이 있다. 그리고 각각 3kg, 4kg, 7kg, 8kg, 9kg의 무게를 가진 5종류의 보석이 있다. 이 보석들의 가치는 각각 4, 5, 10, 11, 13이다. 이 보석을 가방에 담는데 17kg를 넘지 않으면서 최대의 가치가 되도록 하려면 어떻게 담아야할까요? 각 종류별 보석의 개수는 무한이 많다. 한 종류의 보석을 여러 번 가방에 담을 수 있다는 뜻입니다. ⬇️ 입력 첫 번째 줄은 보석 종류의 개수와 가방에 담을 수 있는 무게의 한계값이 주어진다. 두 번째 줄부터 각 보석의 무게와 가치가 주어진다. 가방의 저장무게는 1000kg을 넘지 않는다. 보석의 개수는 30개 이내이다. 4 11 5 12 3 8 6 14 4 8 ⬆️ 출력 첫 번째 줄에 가방에 ..
[C++] 알리바바와 40인의 도둑
·
algorithms (C++)
📄문제 알리바바는 40인의 도둑으로부터 금화를 훔쳐 도망치고 있습니다. 알리바바는 도망치는 길에 평소에 잘 가지 않던 계곡의 돌다리로 도망가고자 한다. 계곡의 돌다리는 N×N개의 돌들로 구성되어 있다. 각 돌다리들은 높이가 서로 다릅니다. 해당 돌다리를 건널때 돌의 높이 만큼 에너지가 소비됩니다. 이동은 최단거리 이동을 합니다. 즉 현재 지점에서 오른쪽 또는 아래쪽으로만 이동해야 합니다. N*N의 계곡의 돌다리 격자정보가 주어지면 (1, 1)격자에서 (N, N)까지 가는데 드는 에너지의 최소량을 구하는 프로그램을 작성하세요. 만약 N=3이고, 계곡의 돌다리 격자 정보가 다음과 같다면 (1, 1)좌표에서 (3, 3)좌표까지 가는데 드는 최소 에너지는 3+2+3+4+2=14이다. ⬇️ 입력 첫 번째 줄에는 ..
[C++] 가장 높은 탑 쌓기 🔥
·
algorithms (C++)
📄문제 밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래에서 위로 쌓으면서 만들어 간다. 아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프로그램을 작성하시오. (조건1) 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다. (조건2) 밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다. (조건3) 벽돌들의 높이는 같을 수도 있다. (조건4) 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다. (조건5) 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다. ⬇️ 입력 입력 파일의 첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 개..
[C++] 최대 선 연결하기 🔥
·
algorithms (C++)
📄문제 왼쪽의 번호와 오른쪽의 번호가 있는 그림에서 같은 번호끼리 선으로 연결하려고 합니다. 왼쪽번호는 무조건 위에서부터 차례로 1부터 N까지 오름차순으로 나열되어 있습니다. 오른쪽의 번호 정보가 위부터 아래 순서로 주어지만 서로 선이 겹치지 않고 최대 몇 개의 선 을 연결할 수 있는 지 구하는 프로그램을 작성하세요. 위의 그림은 오른쪽 번호 정보가 4 1 2 3 9 7 5 6 10 8 로 입력되었을 때 선이 서로 겹치지 않고 연결할 수 있는 최대 선을 개수 6을 구한 경우입니다. ⬇️ 입력 첫 줄에 자연수 N(1 N; for (int i = 0; i > numbers[i]; dp[0] = 1; for (int i = 1; i < N; ++i) { int max = 0; for..
[C++] 최대 부분 증가수열 🔥
·
algorithms (C++)
📄문제 N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰수로) 원소들의 집합을 찾는 프로그램을 작성하라. 예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어 길이가 5인 최대 부분 증가수열을 만들 수 있다. ⬇️ 입력 첫째 줄은 입력되는 데이터의 수 N(1≤N≤1,000, 자연수)를 의미하고, 둘째 줄은 N개의 입력데이터들이 주어진다. 8 5 3 7 8 6 2 9 4 ⬆️ 출력 첫 번째 줄에 부분증가수열의 최대 길이를 출력한다. 4 📝 풀이 #include using namespace std; int dp[1001]; int numbers[1001]; in..
[C++] 돌다리 건너기(Bottom-Up)
·
algorithms (C++)
📄문제 철수는 학교에 가는데 개울을 만났습니다. 개울은 N개의 돌로 다리를 만들어 놓았습니다. 철 수는 돌 다리를 건널 때 한 번에 한 칸 또는 두 칸씩 건너뛰면서 돌다리를 건널 수 있습니다. 철수가 개울을 건너는 방법은 몇 가지일까요? ⬇️ 입력 첫째 줄은 돌의 개수인 자연수 N(3≤N≤45)이 주어집니다. 7 ⬆️ 출력 첫 번째 줄에 개울을 건너는 방법의 수를 출력합니다. 34 📝 풀이 #include using namespace std; int dp[46]; int main() { ios_base::sync_with_stdio(false); int N; cin >> N; dp[1] = 1; dp[2] = 2; for (int i = 3; i
[C++] 계단오르기(Top-Down : 메모이제이션)
·
algorithms (C++)
📄문제 철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면 그 방법의 수는 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 로 5가지이다. 그렇다면 총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인가? ⬇️ 입력 첫째 줄은 계단의 개수인 자연수 N(3≤N≤45)이 주어집니다. 7 ⬆️ 출력 첫 번째 줄에 올라가는 방법의 수를 출력합니다. 21 📝 풀이 #include using namespace std; int dp[46]; int DFS(int n) { if (dp[n] != 0) return dp[n]; return dp[n] = DFS(n - 1) + DFS(n - 2); } int main() { ios_base::sync_wit..
[C++] 네트워크 선 자르기(DP, Bottom-Up, Top-Down) ⭐
·
algorithms (C++)
📄문제 현수는 네트워크 선을 1m, 2m의 길이를 갖는 선으로 자르려고 합니다. 예를 들어 4m의 네트워크 선이 주어진다면 1) 1m+1m+1m+1m 2) 2m+1m+1m 3) 1m+2m+1m 4) 1m+1m+2m 5) 2m+2m 의 5가지 방법을 생각할 수 있습니다. (2)와 (3)과 (4)의 경우 왼쪽을 기준으로 자르는 위치가 다르면 다른 경우로 생각한다. 그렇다면 네트워크 선의 길이가 Nm라면 몇 가지의 자르는 방법이 있는지 구하시오. ⬇️ 입력 첫째 줄은 네트워크 선의 총 길이인 자연수 N(3≤N≤45)이 주어집니다. 7 ⬆️ 출력 첫 번째 줄에 부분증가수열의 최대 길이를 출력한다. 21 📝 풀이 #include using namespace std; static int dy[46]; int mai..
[C++] 토마토(BFS)
·
algorithms (C++)
📄문제 현수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 현수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다. 토마토를 창고에 보관하는 격자모양의 상자..
[C++] 섬나라 아일랜드(BFS)
·
algorithms (C++)
📄문제 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다. 각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다입니다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는프로그램을 작성하세요. ⬇️ 입력 첫 번째 줄에 자연수 N(1 N) continue; // 방문 가능한 모든 섬 위치를 삽입 if (island[xx][yy] == 1) { island[xx][yy] = 0; q.push({ xx, yy }); } } } } } } printf("%d", cnt); } BFS를 활용하여 계산합니다. 2중 for문을 통해 해당 구역이 섬이라면, 해당 구역을 시작으로 인접한 영역을 모두 검사합니다. 더 이상 인접한 영역이 없어 queue가 비었다면, 섬 영역은 끝이며, 2중 for문을 이어서..
[C++] 피자 배달 거리(DFS) 🔥
·
algorithms (C++)
📄문제 N×N 크기의 도시지도가 있습니다. 도시지도는 1×1크기의 격자칸으로 이루어져 있습니다. 각 격자칸에는 0은 빈칸, 1은 집, 2는 피자집으로 표현됩니다. 각 격자칸은 좌표(행번호, 열 번호)로 표현됩니다. 행번호는 1번부터 N번까지이고, 열 번호도 1부터 N까지입니다. 도시에는 각 집마다 “피자배달거리”가 았는데 각 집의 피자배달거리는 해당 집과 도시의 존재하는 피자집들과의 거리 중 최소값을 해당 집의 “피자배달거리”라고 한다. 집과 피자집의 피자배달거리는 |x1-x2|+|y1-y2| 이다. 예를 들어, 도시의 지도가 아래와 같다면 (1, 2)에 있는 집과 (2, 3)에 있는 피자집과의 피자 배달 거리는 |1-2| + |2-3| = 2가 된다. 최근 도시가 불경기에 접어들어 우후죽순 생겼던 피자..
[C++] 수식만들기
·
algorithms (C++)
📄문제 길이가 N인 자연수로 이루어진 수열이 주어집니다. 수열의 각 항 사이에 끼워넣을 N-1개의 연산자가 주어집니다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있습니다. 수열의 순서는 그대로 유지한 채 각 항사이에 N-1개의 연산자를 적절히 배치하면 다양한 수식이 나옵니다. 예를 들면, 수열이 1 2 3 4 5이고 덧셈(+) 1개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 일 때 만들 수 있는 수식은 많은 경우가 존재한다. 그 중 1+2*3-4/5와 같이 수식을 만들었다면 수식을 계산하는 결과는 연산자 우선순위를 따지지 않고 맨 앞쪽 연산자부터 차례로 계산한다. 수식을 계산한 결과는 1이다. N길이의 수열과 N-1개의 연산자가 주어지면 만들 수 있는 수식들..
[C++] 휴가(DFS) 🔥
·
algorithms (C++)
📄문제 카운슬러로 일하고 있는 현수는 오늘부터 N+1일째 되는 날 휴가를 가기 위해서, 남은 N일 동안 최대한 많은 상담을 해서 휴가비를 넉넉히 만들어 휴가를 떠나려 한다. 현수가 다니는 회사에 하루에 하나씩 서로 다른 사람의 상담이 예약되어 있다. 각각의 상담은 상담을 완료하는데 걸리는 날수 T와 상담을 했을 때 받을 수 있는 금액 P로 이루어져 있다. 만약 N = 7이고, 아래와 같이 예약이 잡혀있다면 1일에 잡혀있는 상담은 총 4일이 걸리며, 상담했을 때 받을 수 있는 금액은 20이다. 만약 1일에 예약된 상담을 하면 4일까지는 상담을 할 수가 없다. 하나의 상담이 하루를 넘어가는 경우가 많기 때문에 현수는 예약된 모든 상담을 혼자 할 수 없어 최대 이익이 나는 상담 스케줄을 짜기로 했다. 휴가를 ..
[C++] 복면산 SEND+MORE=MONEY 🔥
·
algorithms (C++)
📄문제 SEND+MORE=MONEY 라는 유명한 복면산이 있습니다. 이 복면산을 구하는 프로그램을 작성하세요. ⬇️ 입력 없음 ⬆️ 출력 9 5 6 7 + 1 0 8 5 ------------ 1 0 6 5 2 📝 풀이 #include // S E N D M O R Y // 각 인덱스 번호에는 위에 해당하는 문자로 간주되어 계산 int arr[8]; // 0부터 9까지를 사용했는지 체크 bool ch[10]; int SEND() { // arr의 각 인덱스 번호에 해당하는대로 네자리 숫자로 출력 return arr[0] * 1000 + arr[1] * 100 + arr[2] * 10 + arr[3] * 1; } int MORE() { return arr[4] * 1000 + arr[5] * 100 + a..
[C++] 순열구하기(DFS : Depth First Search) 🔥
·
algorithms (C++)
📄 문제 자연수 N과 R이 주어지면 서로 다른 N개의 자연수 중 R개를 뽑아 일렬로 나열하는 프로그램을 작성하세요. ⬇️ 입력 첫 번째 줄에 자연수 N(1
[C++] 벨만-포드 알고리즘 ⭐
·
algorithms (C++)
벨만-포드(Bellman-Ford) 알고리즘은 그래프 내에서 단일 출발 노드로부터 모든 다른 노드까지의 최단 경로를 찾는 알고리즘 중 하나입니다. 벨만-포드 알고리즘은 음수 가중치를 가진 간선도 처리할 수 있으며, 음수 가중치 간선이 사이클(음의 사이클)을 형성하지 않는 경우에 사용할 수 있습니다. 음수 가중치 처리 벨만-포드 알고리즘은 음수 가중치를 가진 간선을 처리할 수 있습니다. 단, 음수 가중치 사이클이 없어야 합니다. 음수 가중치 사이클이 있을 경우 알고리즘은 무한 반복됩니다. 시간 복잡도 벨만-포드 알고리즘의 시간 복잡도는 O(V * E)입니다. 여기서 V는 노드의 수, E는 간선의 수를 나타냅니다. 각 노드에 대해 모든 간선을 검사하기 때문에 모든 간선을 한 번씩 확인하는 과정이 V번 반복됩..
[C++] 다익스트라 알고리즘 ⭐
·
algorithms (C++)
다익스트라(Dijkstra) 알고리즘은 그래프 내에서 특정 출발 노드로부터 모든 다른 노드까지의 최단 경로를 찾는 알고리즘 중 하나입니다. 다익스트라 알고리즘은 가중치가 양수인 간선을 가지는 그래프에서 사용됩니다. 우선순위 큐를 사용하여 효율적으로 접근합니다. 그 이유는, Dijkstra 알고리즘에서 최소 가중치를 가진 간선을 선택하는 데 필요한 노드의 후보 집합을 효율적으로 관리하기 위함입니다. 최소 가중치 간선 선택 Dijkstra 알고리즘은 시작 노드에서부터 다른 노드로 가는 최단 경로를 찾는 것이 목적입니다. 이를 위해 각 단계에서 최소 가중치를 가진 간선을 선택해야 합니다. 우선순위 큐는 간선을 가중치 순으로 관리하므로 최소 가중치 간선을 빠르게 선택할 수 있습니다. 노드의 후보 집합 관리 Di..
[C++] 원더랜드(Prim MST 알고리즘 : priority_queue 활용) ⭐
·
algorithms (C++)
프림(Prim) 알고리즘은 그래프의 최소 신장 트리(Minimum Spanning Tree, MST)를 찾는 알고리즘 중 하나로, 시작 노드에서부터 출발하여 MST를 구성하는 과정을 설명합니다. 프림 알고리즘에서 priority_queue를 활용하는 것은 간선의 선택과 관련이 있습니다. 알고리즘 개요 1. 임의의 시작 노드를 선택하고, 해당 노드를 MST에 추가합니다. 2. MST에 속한 노드와 아직 MST에 포함되지 않은 노드 사이의 모든 간선 중에서 최소 가중치 간선을 선택합니다. 3. 선택한 간선의 도착 노드를 MST에 추가하고, 해당 노드를 MST의 일부로 만듭니다. 4. 위의 단계를 MST가 모든 노드를 포함할 때까지 반복합니다. priority_queue의 활용 프림 알고리즘에서 각 단계마다 ..
[C++] 원더랜드(Kruskal MST 알고리즘 : Union&Find 활용) ⭐
·
algorithms (C++)
크루스칼(Kruskal) 알고리즘을 사용하여 그래프의 최소 신장 트리(Minimum Spanning Tree)를 찾습니다. 최소 신장 트리는 그래프의 모든 노드를 포함하면서 모든 노드를 연결하는 데 필요한 간선 중에서 가중치의 합이 최소인 트리입니다. 📄문제 원더랜드에 문제가 생겼다. 원더랜드의 각 도로를 유지보수하는 재정이 바닥난 것이다. 원더랜드는 모든 도시를 서로 연결하면서 최소의 유지비용이 들도록 도로를 선택하고 나머지 도로는 폐쇄하려고 한다. 어떤 도로는 도로를 유지보수하면 재정에 도움이 되는 도로도 존재한다. 재정에 도움이 되는 도로는 비용을 음수로 표현했다. 아래의 그림은 그 한 예를 설명하는 그림이다. 위의 지도는 각 도시가 1부터 9로 표현되었고, 지도의 오른쪽은 최소비용 196으로 모든..
[C++] 친구인가?(Union&Find) ⭐
·
algorithms (C++)
Union-Find, 또는 Disjoint-Set,는 그래프 이론과 컴퓨터 과학에서 사용되는 자료 구조입니다. 이 자료 구조는 여러 원소 집합을 관리하고 원소 간의 관계를 효과적으로 조사할 수 있도록 도와줍니다. 주로 연결 요소를 관리하거나 등가성 판별을 위해 사용됩니다. Union(x, y): 두 집합을 하나로 합칩니다. 즉, 원소 x가 속한 집합과 원소 y가 속한 집합을 합쳐서 하나의 집합으로 만듭니다. Find(x): 원소 x가 속한 집합을 찾아서 대표 원소(또는 부모 원소)를 반환합니다. 이 연산을 통해 원소 간의 관계를 확인할 수 있으며, 두 원소가 동일한 집합에 속하는지 확인할 수 있습니다. 📄문제 오늘은 새 학기 새로운 반에서 처음 시작하는 날이다. 현수네 반 학생은 N명이다. 현수는 각 학..
[C++] 이항계수(메모이제이션) ⭐
·
algorithms (C++)
이항 계수(binomial coefficient)는 조합론(Combinatorics)에서 사용되는 수학적 개념으로, 주어진 크기의 집합에서 원하는 개수의 원소를 선택하는 방법의 수를 나타냅니다. 이항 계수는 주로 "n choose k"로 표기되며, "n choose k"는 n개의 원소 중에서 k개의 원소를 선택하는 경우의 수를 의미합니다. 이항 계수의 조합적 특성은 다음과 같습니다: C(n,k) = C(n−1,k−1) + C(n−1,k) ​ 📄문제 이항계수는 N개의 원소를 가지는 집합에서 R개의 원소를 뽑아 부분집합을 만드는 경우의 수 를 의미한다. 공식은 nCr 로 표현된다. N과 R이 주어지면 이항계수를 구하는 프로그램을 작성하세요. ⬇️ 입력 첫 번째 줄에 자연수 N(1
[C++] 최대 수입 스케쥴(priority_queue 응용문제)
·
algorithms (C++)
📄문제 현수는 유명한 강연자이다. N개이 기업에서 강연 요청을 해왔다. 각 기업은 D일 안에 와서 강연을 해 주면 M만큼의 강연료를 주기로 했다. 각 기업이 요청한 D와 M를 바탕으로 가장 많을 돈을 벌 수 있도록 강연 스케쥴을 짜야 한다. 단 강연의 특성상 현수는 하루에 하나의 기업에서만 강연을 할 수 있다. ⬇️ 입력 첫 번째 줄에 자연수 N(1
[C++] 최소힙(priority_queue : 우선순위 큐)
·
algorithms (C++)
C++에서 priority_queue는 STL의 일부로 제공되는 데이터 구조 중 하나입니다. 요소들을 우선순위에 따라 정렬하여 다루는 자료 구조입니다. priority_queue는 힙(Heap) 자료 구조를 기반으로 작동하며, 기본적으로 내림차순(큰 값이 우선순위가 높음)으로 요소를 정렬합니다. 요소를 삽입할 때 우선순위에 따라 자동으로 정렬하고, 우선순위가 가장 높은 요소를 빠르게 추출할 수 있습니다. 📄문제 최소힙은 완전이진트리로 구현된 자료구조입니다. 그 구성은 부모 노드값이 왼쪽자식과 오른쪽 자식노드의 값보다 작게 트리를 구성하는 것입니다. 그렇게 하면 트리의 루트(root)노드는 입력된 값들 중 가장 작은 값이 저장되어 있습니다. 예를 들어 5 3 2 1 4 6 7순으로 입력되면 최소힙 트리는 ..
[C++] 최대힙(priority_queue : 우선순위 큐)
·
algorithms (C++)
C++에서 priority_queue는 STL의 일부로 제공되는 데이터 구조 중 하나입니다. 요소들을 우선순위에 따라 정렬하여 다루는 자료 구조입니다. priority_queue는 힙(Heap) 자료 구조를 기반으로 작동하며, 기본적으로 내림차순(큰 값이 우선순위가 높음)으로 요소를 정렬합니다. 요소를 삽입할 때 우선순위에 따라 자동으로 정렬하고, 우선순위가 가장 높은 요소를 빠르게 추출할 수 있습니다. 📄문제 최대힙은 완전이진트리로 구현된 자료구조입니다. 그 구성은 부모 노드값이 왼쪽자식과 오른쪽 자식노드의 값보다 크게 트리를 구성하는 것입니다. 그렇게 하면 트리의 루트(root)노드는 입력된 값들 중 가장 큰 값이 저장되어 있습니다. 예를 들어 5 3 2 1 4 6 7순으로 입력되면 최대힙 트리는 아..
[C++] 공주 구하기(Queue 자료구조)
·
algorithms (C++)
📄문제 정보 왕국의 이웃 나라 외동딸 공주가 숲속의 괴물에게 잡혀갔습니다. 정보 왕국에는 왕자가 N명이 있는데 서로 공주를 구하러 가겠다고 합니다. 정보왕국의 왕은 다음과 같은 방법으로 공주를 구하러 갈 왕자를 결정하기로 했습니다. 왕은 왕자들을 나이 순으로 1번부터 N번까지 차례로 번호를 매긴다. 그리고 1번 왕자부터 N번 왕자까지 순서대로 시계 방향으로 돌아가며 동그랗게 앉게 한다. 그리고 1번 왕자부터 시계방향으로 돌아가며 1부터 시작하여 번호를 외치게 한다. 한 왕자가 K(특정숫자)를 외치면 그 왕자는 공주를 구하러 가는데서 제외되고 원 밖으로 나오게 된다. 그리고 다음 왕자부터 다시 1부터 시작하여 번호를 외친다. 이렇게 해서 마지막까지 남은 왕자가 공주를 구하러 갈 수 있다. 예를 들어 총 8..
[C++] 송아지 찾기(BFS : 상태트리탐색)
·
algorithms (C++)
📄문제 현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아지의 위치가 직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다. 현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요. ⬇️ 입력 첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000까지이다. ⬆️ 출력 점프의 최소횟수를 구한다. 📝 풀이 #include #include using namespace std; bool visited[10001]; int dist[10001]; /..
bonnate

티스토리툴바