티스토리

기억보다 기록
검색하기

블로그 홈

기억보다 기록

uiop5809.tistory.com/m

2025년에도 갓생살기

구독자
21
방명록 방문하기

주요 글 목록

  • [백준] 10844 쉬운 계단 수 java https://www.acmicpc.net/problem/10844 풀이 과정dp 파트가 약해서 정리해보고자 한다.문제를 요약해 보자면 ' N자리 수가 있을 때, 인접한 모든 자릿수가 1씩 차이씩 나는 수가 몇 개인지 구하는 것'이다. 여기서 유의해야 할 점은 다음 두 가지를 조심해야 한다. 1) N번째 자릿수의 자릿값이 0인 경우: 다음 자릿수의 자릿값은 1밖에 올 수가 없다.2) N번째 자릿수의 자릿값이 9인 경우: 다음 자릿수의 자릿값은 8밖에 올 수가 없다. 즉 10 다음에 붙을 수 있는 값은 1밖에 없으므로 101이 되는 것이고,만약 19가 온다면 8밖에 올 수 없으므로 198이 되는 것이다.그 외의 값 (2~8)은 각 값보다 -1 또는 +1 인 값을 가질 수 있다. 그럼 자릿값은 0~9를 가질.. 공감수 1 댓글수 0 2025. 1. 23.
  • [백준] 17471 게리맨더링 java https://www.acmicpc.net/problem/17471 풀이과정먼저 문제에 대해서 간단히 설명해보자면 다음과 같이 그래프가 주어졌을 때2가지 구역으로 나눠서, 두 구역의 인구수 차이의 최솟값을 구하는 문제이다. 여기서 유니온 파인드 알고리즘을 생각할 수 있었다. 문제의 조건으로는각 구역은 1개 이상의 지역으로 이루어져야된다고 한다. (1) (2, 3, 4, 5, 6)(2) (1, 3, 4, 5, 6)....(1, 2) (3, 4, 5, 6)(1, 3) (2, 4, 5, 6)(1, 4) (2, 3, 5, 6)...(1, 2, 3) (4, 5, 6)(1, 2, 4) (3, 5, 6) 이런 식으로 2가지 구역이 나눠질 수 있어서지역의 개수 N개에서최소 지역의 개수인 1부터 최대 N / 2개까지 뽑.. 공감수 1 댓글수 1 2025. 1. 22.
  • [백준] 1937 욕심쟁이 판다 c++ https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에www.acmicpc.net풀이과정처음에는 단순하게 DFS 재귀 백트래킹을 이용하여 구현했다.하지만, DP를 사용하지 않으면 시간초과가 났다. 괜히 골드3 문제가 아니다.DP와 DFS를 같이 사용해야 하는 새로운 문제 유형이었다.만약 이 그림 (0, 0)에 판다를 냅둔다면, (0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (1, 1) 을 통해서 총 5일을 살게 될 것이다. 그럼 dp[0][0] .. 공감수 0 댓글수 0 2024. 6. 24.
  • [백준] 1507 궁금한 민호 c++ https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 각각의 도시 사이에 이동하는데 필요한 시간이 주어진다. A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. 또, A와 B www.acmicpc.net 풀이과정 예제 입력으로 플로이드 와샬 알고리즘을 수행한 시간이 입력된다. 그럼에도 불구하고, 플로이드 와샬을 할 때 어느 도시를 거치는 게 더 짧다면 최소 이동시간이 아니므로 이는 불가능한 경우에 해당되며 -1을 출력한다. i에서 j로 가는 경로가 k로 거쳐가는 경우와 같다면 모든 경로를 최소의 도로로 커버해야 하므로 k를 거쳐가는 도로를 선택한다. #include #inclu.. 공감수 0 댓글수 0 2022. 9. 14.
  • [백준] 21940 가운데에서 만나기 c++ https://www.acmicpc.net/problem/21940 21940번: 가운데에서 만나기 위 조건을 만족하는 도시 $X$의 번호를 출력한다. 만약 가능한 도시 $X$가 여러 개인 경우는 도시의 번호를 오름차순으로 출력한다. www.acmicpc.net 풀이과정 #include #include #include using namespace std; int N, M, a, b, t, K, city[201]; int num[201][201]; const int INF = 1e9; void floyd() { for (int k = 1; k N >> M; for (int i = 1; i a >> b >> t; num[a][b] = t; } cin >> K; for (int i = 1; i > city[i.. 공감수 0 댓글수 0 2022. 9. 14.
  • [백준] 14938 서강그라운드 c++ https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 풀이과정 자신에서 자신으로 갈 수 없으니, i == j 일 때를 제외한 나머지 부분들은 무한대로 초기 설정한다. 그리고 num 배열에 각 정점에서 얻을 수 있는 아이템이 몇 개인지 입력받는다. 플로이드 와샬을 시행했을 때, 결과는 아래 사진처럼 나오게 되는데, 여기서의 숫자들은 각 노드에서 다른 노드를 갈 때 길의 길이가 얼마인지 알려주는 숫자들이다. 수색범위가 m이니까 각 노드에서 갈 때를 비교하여 .. 공감수 0 댓글수 0 2022. 9. 14.
  • [백준] 2458 키 순서 c++ https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 풀이과정 일단 각 간선의 가중치를 1로 잡았다. 자신의 키가 몇 번째인지 알 수 있으려면, 자신을 제외한 무한대가 아닌 노드들이 N - 1개여야 한다. num[i][j] = 1이라는 것은 i보다 j가 크다는 뜻이고, num[j][i] = 1이라는 것은 i보다 j가 작다는 뜻이다. 이 두 가지 경우 다 i학생의 기준에서 키의 기준을 알 수 있다. 그러므로 num[i][j] != INF 또는 num[j.. 공감수 0 댓글수 0 2022. 9. 14.
  • [백준] 2910 빈도 정렬 c++ https://www.acmicpc.net/problem/2910 2910번: 빈도 정렬 첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다. www.acmicpc.net 풀이 과정 #include #include #include #include #include using namespace std; map m; map m1; vector v; bool cmp(pair a, pair b) { if (a.first == b.first) return m1[a.second] b.first; } int main() { ios::sync_with_stdio(f.. 공감수 0 댓글수 0 2022. 9. 14.
  • [백준] 17219 비밀번호 찾기 c++ https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 풀이과정 map의 find 함수를 알게 해 준 문제이다. res를 입력받고 res의 key값을 찾으면 그에 맞는 value를 출력해주면 된다. #include #include #include #include #include using namespace std; int N, M; string adress, passwd, res; int main() { ios::sync.. 공감수 0 댓글수 0 2022. 9. 14.
  • [백준] 5568 카드 놓기 c++ https://www.acmicpc.net/problem/5568 5568번: 카드 놓기 예제 1의 경우 상근이는 11, 12, 21, 112, 121, 122, 212를 만들 수 있다. www.acmicpc.net 풀이과정 처음으로 set을 사용해봤다. map을 사용하지 않고, set을 사용한 이유는 중복되는 값을 삭제해야 되기 때문이다. 이것이 set의 가장 큰 메리트라고 생각한다. 좋은 문제인 것 같다! next_permutation - 현재 나와있는 수열에서 인자로 넘어간 범위에 해당하는 다음 순열을 구한다. - 사전식으로 정렬한다. - 사용 전에 꼭 sort하고 시작해야 한다. #include #include #include #include #include using namespace std; .. 공감수 0 댓글수 0 2022. 9. 13.
  • [백준] 14425 문자열 집합 c++ https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 풀이과정 처음에는 단순히 배열에 값을 넣어서 있으면 cnt하는 반복문을 돌렸었다. 그러나 실버3은 역시 간단할리 없었다. map에 string 값을 key로 넣고 bool 값을 value로 넣어서 bool이 true라면 값이 있었다는 뜻이므로 cnt를 해줬다. #include #include #include #include using namespace std; in.. 공감수 0 댓글수 0 2022. 9. 13.
  • [백준] 1620 나는야 포켓몬 마스터 이다솜 c++ https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 풀이과정 처음 풀어본 map 문제라 조금 헤맸던 문제이다. mp1은 string-key 값을 넣으면 int-value값이 나오는 맵이며, mp2는 int index 값을 넣으면 string이 나오는 기본적인 배열이다. #include #include #include #include using namespace std; int N, M; string str, quest;.. 공감수 0 댓글수 0 2022. 9. 13.
  • [백준] 1302 베스트셀러 c++ https://www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net 풀이과정 string을 key로 하고, int를 value로 한다. 팔린 책의 개수인 second 개수가 가장 큰 값을 res에 넣는다. 가장 많이 팔린 책이 여러 개일 경우에는 사전 순으로 가장 앞서는 제목을 출력해야 되니 팔린 책의 개수인 second 개수가 res일 경우에 first인 key를 출력해주고 함수를 끝낸다. (map은 삽입이 되면서 오름차순으로 자동 정렬된다.) 반복문 데.. 공감수 0 댓글수 0 2022. 9. 13.
  • [백준] 4803 트리 c++ https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 풀이과정 기본 문제인 것 같았지만, 생각해야 될 것이 많았던 문제이다. 입력을 받고 나서, 두 노드의 부모가 다른 집합일 때와 같은 집합일 때로 나눈다. 다른 집합일 때는 부모의 노드를 통일시켜주고, 만약에 두 부모 중 한 집합이라도 사이클이 존재한다면 두 집합 모두 사이클로 변경해준다. 같은 집합일 때는 시작 노드를 사이클로 변경해준다. 만약 사이클이 존재한다면 넘어가주고, 사.. 공감수 0 댓글수 0 2022. 9. 5.
  • [백준] 15809 전국시대 c++ https://www.acmicpc.net/problem/15809 15809번: 전국시대 첫 번째 줄에 국가의 수를 나타내는 N과 기록의 수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 두 번째 줄 부터 N개의 줄에 걸쳐 i번째 국가의 병력 Ai (1 ≤ i ≤ N)가 자연수로 주어진다. (1 ≤ Ai ≤ 10,000) 다 www.acmicpc.net 풀이과정 #include #include #include using namespace std; int N, M, op, P, Q; int parent[100001], res[100001]; int getParent(int x) { if (parent[x] == x) return x; return parent[x] = getParent(parent.. 공감수 0 댓글수 0 2022. 9. 5.
  • [백준] 1939 중량제한 c++ https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 풀이과정 이 문제는 이분 탐색, BFS, 유니온 파인드 3개의 알고리즘이 섞인 문제여서 매우 어려웠던 문제이다. #include #include #include #include #include using namespace std; int n, m, A, B, cost, s, e; bool c[10001]; vector v[10001]; b.. 공감수 0 댓글수 0 2022. 9. 5.
  • [백준] 4195 친구 네트워크 c++ https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 풀이과정 이 문제는 유니온 파인드와 map 알고리즘이 섞인 문제이다. 유니온 파인드 알고리즘을 하려면, 처음에 parent 배열에 각자 자신의 번호로 초기화시켜준다. 한 줄에 2명씩 입력되므로 최대 노드 개수는 2 * F 개가 된다. 입력을 받을 때, 만약 map.count가 0이라면 idx를 넣어주고 1씩 플러스 해준다. 그다음 unionParent 함수를 실행하고, 다른 집합일 경우.. 공감수 0 댓글수 0 2022. 9. 5.
  • [백준] 20040 사이클 게임 c++ https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 풀이과정 bool 함수의 장점을 느꼈던 문제이다. #include #include #include using namespace std; int n, m, x, y; int parent[500001]; // 부모 노드를 찾는 함수 int getParent(int x) { if (parent[x] == x) return x; return parent[x] = getParent(parent[x]).. 공감수 0 댓글수 0 2022. 9. 5.
  • [백준] 16562 친구비 c++ https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net 풀이과정 연결되어 있는 노드들 중에 친구비가 작은 친구가 있다면 부모 노드를 바꿔준다. #include #include #include using namespace std; int N, M, k, v, w; int f[10001], parent[10001]; // 부모 노드를 찾는 함수 int getParent(int x) { i.. 공감수 0 댓글수 0 2022. 9. 5.
  • [백준] 1976 여행 가자 c++ https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 풀이과정 1이면 도시들이 연결된 것을 의미하므로 unionParent(i, j) 함수를 실행시켜준다. 그럼 연결된 도시들은 가장 작은 부모 노드를 가지고 있을 것이다. 여행 계획에 있는 도시들을 두 개씩 findParent에 넣어보고 만약에 다른 것이 있다면 연결되지 않은 도시라는 뜻이므로 res를 false로 변경한다. #include #include #include using namespace.. 공감수 0 댓글수 0 2022. 9. 5.
  • [백준] 1717 집합의 표현 c++ https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 풀이과정 유니온 파인드 알고리즘의 가장 대표적인 기본 문제이다. 1. 부모 노드를 찾는 함수 2. 두 부모 노드를 작은 것으로 합치는 함수 3. 부모 노드가 같은지 확인하는 함수 #include #include #include using namespace std; int n, m; int parent[1000001]; // 부모 노드를 찾는 함수 int g.. 공감수 0 댓글수 0 2022. 9. 5.
  • [백준] 11657 타임머신 c++ https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 풀이과정 이 문제는 벨만 포드의 대표적인 기본 문제이다. 그 이유는 타임머신으로 시간을 되돌아가는 경우가 있으므로 가중치가 음수가 될 수 있기 때문이다. 가중치에 음수가 있다면 다익스트라가 아닌, 벨만 포드 알고리즘을 생각해야 한다. 문제에 있는 '시간을 무한히 오래전으로 되돌릴 수 있다면'이라는 말은 '음의 사이클이 존재한다면' 뜻이다.. 공감수 0 댓글수 0 2022. 9. 5.
  • [백준] 1956 운동 c++ https://www.acmicpc.net/problem/1956  1956번: 운동첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의www.acmicpc.net 풀이과정사이클이 생기는 부분의 최소합을 구하면 되는 문제이다.   i == j일 때는 continue 해주고, arr[i][j] + arr[j][i]일 때의 최솟값을 구하면 된다.   만약 res가 INF일 경우는, 사이클이 되는 곳이 한 곳도 없으므로 -1을 출력해준다. #include #include #include using namespace std;int V.. 공감수 0 댓글수 0 2022. 9. 5.
  • [백준] 1719 택배 c++ https://www.acmicpc.net/problem/1719 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net 풀이과정 예전에 다익스트라 + 플로이드 와샬 문제를 푼 적이 있어서 비슷할 거라고 생각했다. 그러나 생각해야될 것이 많아서 시간이 오래 걸린 문제였다..! 처음에 풀었던 방식은 경유지를 지나면 res배열에 담아주는 방식이다. (2번째 코드) 그러나 이렇게 되면 1행 6열은 1 -> 2 -> 5 -> 6 두개의 경유지를 거치게 되어 첫번째 경유지 2가 아닌, 두번째 경유지인 5를 출력하게 되었다. 최초로 거.. 공감수 0 댓글수 0 2022. 9. 5.
  • [백준] 1613 역사 c++ https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 풀이과정 예전에 풀었던 플로이드 와샬의 백준 키 순서와 비슷한 문제였다. 키 순서 문제 참고하기 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 처음에 입력을 받자마자 num[x][y] = 1, .. 공감수 0 댓글수 0 2022. 9. 5.
  • [백준] 3665 최종 순위 c++ https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 풀이과정 문제에서 작년 순위를 주고, 순위가 바뀐 모든 팀의 정보를 주었으므로, 확실한 순위를 모르는 경우인 "?"인 경우는 없다. adj[a][b] = true : a팀 다음에 b팀 indegree[x] : x 앞에 와야 하는 팀 개수 #include #include #include #include #include #include using namespace std; int T, n, m.. 공감수 0 댓글수 0 2022. 9. 2.
  • [백준] 14676 영우는 사기꾼? c++ https://www.acmicpc.net/problem/14676 14676번: 영우는 사기꾼? 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 건물 종류의 개수 N, 건물 사이 관계의 개수 M, 영우의 게임 정보의 개수 K가 주어진다.(1 ≤ N, M, K ≤ 100,000) 다음 줄부터 M줄에 걸쳐 www.acmicpc.net 풀이과정 이때까지 풀었던 문제 유형들과는 다른 느낌이었다. 위상 정렬 함수를 만들지 않고 main함수 안에서 하려고 하니 더 어렵게 느껴졌다. 일단 입력을 M번 받아놓고 화살표 간선끼리 연결해주며 진입 차수도 플러스해준다. 그다음, K번 반복하는 부분이 중요한데 option이 1이면 건물을 1개 건설하는 것이고 2이면 파괴하는 것이라고 한다. 건설 부분을 보면 진입.. 공감수 0 댓글수 0 2022. 9. 2.
  • [백준] 9470 Strahler 순서 c++ https://www.acmicpc.net/problem/9470 9470번: Strahler 순서 지질학에서 하천계는 유향그래프로 나타낼 수 있다. 강은 간선으로 나타내며, 물이 흐르는 방향이 간선의 방향이 된다. 노드는 호수나 샘처럼 강이 시작하는 곳, 강이 합쳐지거나 나누어지는 곳 www.acmicpc.net 풀이과정 문제를 잘 읽지 않고 풀어서 고생했던 문제이다... 가장 핵심인 부분은 "나머지 노드는 그 노드로 들어오는 강의 순서 중 가장 큰 값을 i라고 했을 때, 들어오는 모든 강 중에서 Strahler 순서가 i인 강이 1개이면 순서는 i, 2개 이상이면 순서는 i+1이다"라는 부분이다. #include #include #include #include using namespace std; i.. 공감수 0 댓글수 0 2022. 9. 2.
  • [백준] 14567 선수과목 (Prerequisite) c++ https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 풀이과정 dp와 위상정렬을 같이 쓰는 문제다. 위상정렬 함수를 보면 진입차수가 0일 경우(1,4,6번 노드)에 큐에 푸시를 하며 정답 배열에 1을 넣어준다. 그리고 큐가 비어있지 않을 때까지 연결되어있는 노드를 돌며 dp를 해주며 최종적으로 max인 값(res)를 출력해준다. #include #include #include #include using namespace std; int N, M, A, B; int indegr.. 공감수 0 댓글수 0 2022. 9. 2.
  • [백준] 2623 음악 프로그램 c++ https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 풀이과정 위상 정렬 함수는 다른 문제와 동일하지만, 입력을 받고 벡터 함수에 넣는 것이 색다른 문제였다. 위 사진처럼 수를 입력받고, 부등호에 따라 이중 반복문으로 벡터 함수에 넣어주며 진입차수를 1씩 늘려주었다. 큐의 앞부분 now의 값을 res에 넣어주며 개수가 N개가 아닐 때는 순서를 정하는 것이 불가능하다는 뜻이므로 0을 출력해준다. #include #include #i.. 공감수 0 댓글수 0 2022. 9. 2.
    문의안내
    • 티스토리
    • 로그인
    • 고객센터

    티스토리는 카카오에서 사랑을 담아 만듭니다.

    © Kakao Corp.