제민

https://youtu.be/o9BnvwgPT-o?si=h9QqnjghGsans5cF 플로이드-와셜과 같은 최단경로 알고리즘입니다.플로이드-와셜은 음수 간선이 존재하는 경우에서는 사용 가능하고, 음수 "사이클" 이 존재하는 경우 사용 불가능했습니다.  다익스트라는 음수 간선이 존재할 경우 사용할 수 없다는 특징을 갖습니다. 한 정점에서부터 다른 정점까지의 최단경로를 구할 수 있습니다.2024/05/13 기본 틀 학습 (경로복원 X) BOJ 1753 최단경로 G4https://www.acmicpc.net/problem/1753 설명이 있는 코드는 이곳에서 확인 가능합니다.더보기#include using namespace std;typedef pair Pii;#define X first //가중치#defi..

해당 글을 보고 정리한 내용입니다. 오프라인 쿼리와 Small To Large단어만 들으면 어려워보이지만 그렇지 않다. 오프라인 쿼리는 주어진 쿼리를 순서대로 처리하지 않아도 되는 경우에 사용할 수 있는 테크닉이다.쿼리를 모두 저장하고 역순으로 돌면서 쿼리를 처리하는 기법이다. Small To Large는 작은 집합을 큰 집합으로 합치는 테크닉으로, 시간복잡도를 줄이는데 큰 도움이 된다.오프라인 쿼리의 연습 문제로 "BOJ 13306 트리" 가 있다.https://www.acmicpc.net/problem/13306 해당 문제에서 쿼리는 총 두 종류로, 0 X : X와 X의 부모를 잇는 간선을 제거1 A B : A와 B를 연결하는 경로가 존재하는가? 문제를 잘 보면 쿼리를 순차적으로 살펴보았을 때, 마지..

https://www.acmicpc.net/problem/18251 중위 순회로 각 노드의 높이와 가중치를 저장해 놓고, 스위핑을 통해 최대값을 구하면 됩니다.주의할 점은 모든 노드의 가중치가 음수일 경우인데, 그럴 경우 그 중 가장 큰 가중치를 출력해주면 됩니다.중위순회를 하면 가장 왼쪽 노드부터 오른쪽으로 방문하므로 중위순회 중 백터에 값을 넣게 되면 자연스럽게 왼쪽 노드부터 오른쪽 노드가 순서대로 들어가게 됩니다. 포화 이진 트리이므로 트리의 높이는 log2(N)으로 구할 수 있습니다. 더보기#include using namespace std;typedef long long ll;#define YY first#define WW secondint n;ll W[28'0003];vector> P;void..

https://www.acmicpc.net/problem/13314 13314번: 플로이드에 오타가?평소에 코딩 실력이 부족하다고 느끼고 있는 지구이는 익명게시판에서 “백스페이스 키를 쓰지 않고 코딩하기를 추천합니다” 라는 글을 읽게 되었다. 글의 최하단에는 매우 작은 글씨로 “효www.acmicpc.net작성했던 해설이 날라간 관계로 타 글로 대체함.https://ps.mjstudio.net/boj-13314더보기#includeusing namespace std;int d[103][103];int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n=100; for(int i=1;ihttps://www.acmicpc.ne..

https://youtu.be/dDDy2bEZRA8?si=zCkILIWQt98MpCdQ https://www.acmicpc.net/problem/11404 11404번: 플로이드첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가www.acmicpc.net그래프에서의 최단 경로 알고리즘 중 하나인 플로이드 워셜을 구현하는 문제이다.오버플로 방지를 위해 INF를 0x3f3f3f3f로 해준다.테이블을 채우는 과정에서 k는 경유지라고 보면 이해가 쉽다. i에서 j로 가는데 k를 거쳐가는 경우가 더 빠른지 확인하는 것이다.min 함수로 구현하면 ..

https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 유니온 파인드로 이런게 가능할지 몰랐다. Set을 사용한 풀이가 더 직관적인 것 같긴 하지만 유니온파인드가 조금 더 편한 느낌이 있다. 풀이는 다음과 같다. 1. parent 배열 초기화. 2. 값 x를 입력받으면 find(x)와 find(x-1)을 merge. (2-1. 이 때 find(x)의 부모가 find(x-1)인 구조가 되어야 한다.) (2-2. merg..

https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net https://jemin06.tistory.com/129 그래프(3) 문제 중 구슬 찾기마냥 순위를 정할 수 있지 않을까 생각했는데 아니었다. 결국 답지에서 아이디어를 찾았다. 풀이는 다음과 같다. 1. 모든 노드에 대해 선후관계를 정의한다. ex) 5 4 3 입력되었다면 5->4, 5->3, 4->3 식으로 간선을 긋는다. 2. 등수가 바뀐 쌍 a,b가 들어오면 a->b 간선이 존재한다면..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 유니온 파인드를 사용한 크루스칼 알고리즘으로 MST를 구해보았다. 더보기 #include using namespace std; int n,m; //정점 간선 수 int ans; int parent[10'003]; int rnk[10'003]; vector E; void init(){ for(int i=1;irnk[v]) swap(u,v); parent..

https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 열쇠가 a~f로 6개만 존재하기에 비트마스킹으로 해결할 수 있다.처음에 nkey 대신 key만 써서 틀렸었는데 아직도 틀린 이유를 모른다.key를 갱신하려고 하면 틀린다. #include using namespace std; #define Y first #define X second int n,m; char board[53][53]; bool vis[53][53][1..

https://www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아 www.acmicpc.net "최소 연산 횟수" 를 구하라 했으므로 BFS라는 것을 알 수 있다. vis 배열 대신 set으로 방문 처리를 했다. 다른 코드들을 보니, DFS 풀이도 존재했다. 이 코드에는 불필요한 연산들이 존재한다. 무한대로 증가하는 cur.X, 계속 1로 나누는 나누기 연산 등인데, 이를 없애면 vis 없이도 효율적인 코드를 작성할 수 있다. #include using namespace std; t..

https://m.blog.naver.com/fbfbf1/222278788809 유니온 파인드(Union Find) c++ 유니온 파인드 정의 - 공통 원소가 없는 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하... blog.naver.com 원래 바킹독 강의를 보면서 공부하려고 했는데 나오기까지 한참 남았길래 독학했습니다. https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 유니온 파인드를 ..

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 2024.04.07 별다른 테크닉 없이 위상정렬만 하면 되는 문제이다. 더보기 #include using namespace std; queue Q; vector graph[32'003]; vector ans; int degree[32'003]; int n,m; int main() { ios::sync_with_stdio(0); cin.tie(0); cou..

https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 푸는 방법이 맞았는데 실수했다. 나는 사이클이 생기면 ans++을 하면 된다고 생각했는데, 그럴 경우 서로 마주보는 화살표에 대해서 처리가 불가능하다고 생각했다. 근데 마주보는 화살표의 경우엔 한 칸 앞으로 갔다가 다시 돌아오면 이미 갔던 공간이기에 사이클이 성립한다. 방문 표시를 int로 남겨서 몇 번째 단계에서 방문한 공간인지 확인할 수 있게 한다. 예쁘게 ..

https://www.acmicpc.net/problem/4256 4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 트리의 순회마냥 분할 정복으로 해결이 가능하다. 비슷한 유형이라 해결하는데 큰 어려움은 없었다. #include using namespace std; int preorder[1003]; int inorder[1003]; int inidx[1003]; //inorder에서 특정 원소의 idx 저장 void postorder(int pre_S, int pre_E, int in_S, int ..

https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 트리의 순회를 풀며 분할 정복을 다시 한 번 되새긴 후, 이 문제를 접했다. 문제를 보고 처음 든 생각은 이진 트리이므로 LC RC 배열을 만들고 입력이 들어올 때마다 루트를 시작점으로 DFS를 돌며 트리를 복원한 후 후위 순회를 돌면 될 것 같단 생각이 들었고, 정답이 나왔다. (코드-DFS) 더보기 #include using namespace std; int root,x; int ..

https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 분할정복/재귀 #include using namespace std; int n; int inorder[100003]; int idx[100003]; int postorder[100003]; void preorder(int in_S, int in_E, int post_S, int post_E){ if(in_S>in_E || post_S>post_E) return; //분할정복 종료조건 int root_idx = idx[pos..

https://www.acmicpc.net/problem/20304 20304번: 비밀번호 제작 서강대학교 전산실에서 보안직원으로 일하는 향빈이는 한 통의 이메일을 받게 되었다. 이메일에는 서버 관리자 계정에 대한 비정상적인 로그인 시도가 감지되었다는 내용이 적혀 있었고, 첨부 www.acmicpc.net 문제를 보고 BFS라는게 떠오르지도 않았다. BFS 문제집에 있어서 숨바꼭질 문제처럼 1차원으로 왔다갔다 하면 되나 싶었는데 그것도 아니고... 답은 XOR에 있었다. 안전거리를 1 증가시키려면 [cur ^ 0x01n>>m; fill(dist,dist+n+1,-1); while(m--){ int p; cin>>p; dist[p]=0; Q.push(p); } while(!Q.empty()){ int cu..

오래전에 풀다가 막혔던 문제인데 그래프/트리를 땐 김에 풀어보기로 했다. 인접리스트/인접행렬 등 그래프를 나타내는 방법들을 배우고 나니 BFS를 틀에 얽메이지 않고 좀 더 자유롭게 쓸 수 있는 느낌이 들었다. https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net #include using namespace std; #define Y first #define X second int n,m,ans; ..

https://www.acmicpc.net/problem/20955 20955번: 민서의 응급 수술 민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서 www.acmicpc.net 트리의 특성을 기억해야 풀 수 있는 문제이다. 더보기 #include using namespace std; int n,m; vector graph[100003]; vector vis(100003,false); int treeCnt=0; void DFS(int cur){ vis[cur]=true; for(int nxt : graph[cur]){ if(vis[nxt]) continue; DFS(nx..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 더보기 DFS #include using namespace std; vector graph[100003]; int parent[100003]; void DFS(int cur){ for(int nxt : graph[cur]){ if(nxt==parent[cur]) continue; parent[nxt]=cur; DFS(nxt); } } int main() { ios::sync_with_stdio(0); cin.tie(); int n; cin>>n; for(int..

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 당시에 풀이를 보고도 뭔소린지 모르겠어서 넘겼었는데 그래프를 배운 김에 풀어보았다. 그래프를 배워도 딱히 풀이가 떠오른다거나 그런 건 없었다... 혼자 짰던 코드에서 애를 먹었던 부분은 방문했던 노드에 방문했는데 그게 시작점이 아니었을 때의 처리였다. 그래서 풀이를 찾다가 기존 코드와 가장 비슷한 풀이를 발견했다.https://geeks-mimic.tistory.com/m/37코드 이해에 많은 시간이 ..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 뭔가 틀릴거같았는데 바로 맞춰서 놀랐다... 문제를 이해하는데 애를 먹었는데 https://velog.io/@e_juhee/python-백준-1707-이분-그래프 이분에 깔끔하게 설명해주셔서 풀 수 있었다. 더보기 #include using namespace std; bool isBipartiteGraph; int n,m,k; int chk[20003]; vector graph[20003]; vo..

https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 분명히 알고리즘 상 문제는 없어 보였는데 문제를 잘못 읽었었다. 최대 점수가 3점인 줄 알아서 틀렸었다. 점수 탐색 범위를 늘리니 해결할 수 있었다. 더보기 #include using namespace std; vector graph[53]; vector ans[53]; int dist[53]; int n; void BFS(int st){ fill(dist,dist+51,-1); queue Q; ..

https://www.youtube.com/watch?v=9iI6fuOLiLg&t=1121s 진작에 봤어야 했는데 너무 게을렀다. 수요일날에 다 보고 적어도 이론은 이해를 했어야 했는데... 근데 솔직히 어려워서 미뤘던 것도 있었다. 요즘 앞에 배웠던 것들이 잘 기억나지 않아서 트리까지만 공부하고 동아리 활동을 하면서 내실을 다져야 할 것 같다. https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmi..

https://www.acmicpc.net/problem/1245 1245번: 농장 관리 첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다. 격자의 높이는 500보다 작거나 같은 음이 아닌 정수 www.acmicpc.net 처음 문제를 볼 때는 풀이를 생각하지 못했는데 정해를 보니 대단했다... 주변에 자신보다 높은 칸이 있다면 false로 바꿔서 ans++을 하지 못하게 한다. 그리고 제일 중요한 점은 자기 자신과 크기가 같은 칸만을 탐색한다는 점이다. 처음에 이를 모르고 풀어서 고생했다. #include using namespace std; int n,m,ans; int board[..

https://www.acmicpc.net/problem/5558 5558번: チーズ (Cheese) 入力は H+1 行ある．1 行目には 3 つの整数 H，W，N (1 ≦ H ≦ 1000，1 ≦ W ≦ 1000，1 ≦ N ≦ 9) がこの順に空白で区切られて書かれている．2 行目から H+1 行目までの各行には，'S'，'1', '2', ..., '9'， www.acmicpc.net 이 문제의 제일 큰 진입장벽은 언어였다. 일본어여서 문제 해석에서 좀 혼돈이 있었다. 치즈를 순서대로 먹지 않아도 되는 걸로 이해해서 비트마스킹으로 풀려니 dist[1024][1024][1024]가 메모리 초과를 일으켜서 답답했다. 문제를 해석하니 기본적인 BFS 문제였다. #include using namespace std; int h,..

https://www.acmicpc.net/problem/14923 14923번: 미로 탈출 홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이 www.acmicpc.net 벽 부수고 이동하기와 유사한 문제였다. 간만에 풀어보았는데 좋은 연습이 되었다. 실수로 board에 z축을 추가해서 맞왜틀을 했었다... #include using namespace std; int board[1003][1003]; int dist[1003][1003][2]; int dy[4]={1,0,-1,0}; int dx[4]={0,1,0,-1}; queue Q; int n..

https://www.acmicpc.net/problem/17244 17244번: 아맞다우산 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출 www.acmicpc.net 챙겨야 하는 물건의 수가 최대 5개로 작으므로 비트마스크를 사용해 해결할 수 있다. #include using namespace std; int N,M,Bit,idx; bool vis[53][53][35]; //y x bit char board[53][53]; int dy[4]={1,0,-1,0}; int dx[4]={0,1,0,-1}; queue Q; //y x cnt bit int ma..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 또다시 삼성의 벽을 느끼게 된 순간이다. 솔직히 문제 자체는 크게 어렵지 않지만 테크닉이 부족해서 시간이 좀 걸렸다. 처음 작성한 코드인데, 80%에서 시간 초과가 걸렸다. 아무리 봐도 답이 나오지 않아 Chat GPT에게 도움을 청했더니 board를 갱신하는 부분을 배열을 하나하나 돌면서 하지 않고, BFS를 사용하면 시간 초과 없이 해결할 수 있었다. 더보기 #include us..

https://www.acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net 1시간 20분 정도 걸려서 풀었다. 전에 풀었던 토마토와 비슷한 유형의 문제였다. 처음에 시간복잡도를 고려할 때 5비트 4진수의 가짓수인 1023에 판을 쌓는 경우의 수 120(5!)가지, 입구와 출구가 될 수 있는 가짓수 4가지... 등등 생각할 게 많아서 시간초과가 나지 않을까 걱정했는데 시간 제한이 2초로 널널해서 무난하게 통과할 수 있었다. 그래도 코드가 상당히 느려서..