백준 BOJ 16074 Mountaineers 출처 : https://www.acmicpc.net/problem/16074 각 cell에 1, 2, 3, 4, ,,, (h * w)번호를 매긴 후 이 새로 인덱싱한 번호는 노드 번호로 취급 이후 각 인접한 노드(상, 하, 좌, 우)와 연결(엣지)을 하는게 두 노드 간의 cost는 누 도느 중 max값이 두 노드 사이의 cost가
백준 BOJ 13208 승현이와 승현이 출처 : https://www.acmicpc.net/problem/13208 문제에서 그래프가 주어진다. 이걸 또 다른 그래프로 바꿔야 한다. 주어진 그래프에서는 노드가 1, 2, 3, ,,, N까지 있다. 여기서 새로 만들어야 될 그래프는 N^2개의 노드를 가진다. (1, 1), (1, 2), (1, 3) ,,, (1, N), (2, 1), (2, 2),,,(2, N),,,(N, N) 이것을
코드포스 Codeforces Round #620 (Div. 2) E. 1-Trees and Queries 출처 : https://codeforces.com/contest/1304/problem/E LCA를 이용하면 댄다... 풀이는 int query(int nu, int nv, int u, int v, int len) 함수에 주석으로 적어놓았다.... 아래는 전체 코드 #include #define endl "\n" using namespace std; using ll = long long; struct TREE { int vn; vector>elist; vectors, p,
코드포스 Codeforces Round #294 (Div. 2) E. A and B and Lecture Rooms 풀이는 아래 그림으로 **대.체.한.다** 출처 : https://codeforces.com/contest/519/problem/E 아래는 소스코드 #include #define endl "\n" using namespace std; using ll = long long; struct TREE { int vn, sidx; vector>elist, p; vectorsize, depth; TREE(int a) : vn(a), sidx(1) { size.resize(vn + 1,
백준 BOJ 16213 dgeu-learning 출처 : https://www.acmicpc.net/problem/16213 요즘 HLD풀고 있는데 구현량이 꽤 있는 문제를 봐서 여기다가 올린다. (C한정) 참고로 난 구현량이 많으면 좋...다.... 힣... 오랜만에 정렬을 구현해 보고 싶다면 이 문제를 추천한다. 풀이 : MAXIMUM spanning tree를 만든다. 만들어진 트리를 가지고 heavy-light decomposition을 돌린다. min segment tree를 만든다. 엣지사이의 값을가지고
백준 BOJ 13016 내 왼손에는 흑염룡이 잠들어 있다 출처 : https://www.acmicpc.net/problem/13016 반갑읍니다. 누가봐도 tree dp인데 나는 아직도 tree dp를 풀어본적이 없어서 LCA로 비벼봄. 설명은 PPT로 대.체.한.다 는 여기 파일 업로드가 안대서 각 슬라이드 사진으로 첨.부.한.다 아래는 코드 #include #include struct e { int num, cost; }; struct node { int num;
백준 BOJ 10775 공항 출처 : https://www.acmicpc.net/problem/10775 한 6개월전 union-find 분류 훑다가 문제 이해가 안대서 넘겼는데 오늘 다시 보니깐 union-find풀이방법은 생각 안나고 이상하게 segment tree풀이가 생각났다. 간단한 설명 : i번째 비행기가 k번쨰 게이트에 도킹하고 싶다. 지금 k번째 게이트가 비어 있다면 도킹하면 된다. 그러나 k번쨰 게이트가 이미 도킹된 상태라면 1 ~ k -
백준 BOJ 1517 버블 소트 출처 : https://www.acmicpc.net/problem/1517 inversion counting 나는 merge sort tree 모른다. 아래 풀이는 segment tree 사용 #include #include struct info { int idx; long long val; }; long long answer, * tree; struct info *list, *sorted; void msort(struct info *, int, int); void merge(struct info *, int, int, int); int
백준 BOJ 18119 단어 암기 출처 : https://www.acmicpc.net/problem/18119 첫번 째 생각 : 완전 나이브 O(단어 개수 * 단어길이 * 쿼리 개수) 이러면 왠지 메모리에서 크트 당할꺼 같아서 좀 더 생각 해봄 두번 째 생각 : 어떤 알파벳에 대해서 내가 알고있다, 모르고 있다만 알고 있으면 대니깐 각 단어에 대해서 알파벳에 대해서 1(알고있다), 0(모르고
자료구조 hash table을 구현해 보자 이제 학교에서 해우면서 PS에서 사용하는 자료구조 포스팅은 이게 아마 마지막일듯 싶다. Q. ??? 너는 학교에서 rb-tree도 안배움?? A. 배웠다. 근데 못짠다. 그리고 PS에서 실제 구현하는 사람이 있을까 싶다.... 우리는 map이 있자나!!!! 그리고 내가 rb-tree를 못짜고 map을 사용하는 방법도 모르기에 hash table을 구현해서 문제를 비벼오고 있다. Q. 이글에선 충돌 어떻게 처리할거임? A.
자료구조 stack을 구현해 보자 스.택.을.구.현.해.보.자 알지? 연결리스트로할꺼임ㅋ 코드부터 보자 그리고 당연한 이야기겠지만 마지막에는 문제를 통해서 아래 코드를 검증해 볼 것이다. struct node { int num; struct node * pre; }; struct node *f, *r; void push(int); struct node pop(); int isempty(); void push(int num) { struct node *temp; temp
백준 BOJ 17835 면접보는 승범이네 출처 : https://www.acmicpc.net/problem/17835 아 이거 사실 증명 안하고 예전에 풀었던거 비슷하게 감으로 떄려 맞췄다. 그래서 정당성에 대한 설명은 못하겠고 풀이방법만 적을게.(누가 증명좀 ㅎ) 1. 역방향 그래프를 만든다. 2. 출발지는 면접장 전체다. -> pq, memo에 면접장 전부 반영해준다. 3. 다익스트라를 돌린다. 4. 그럼 memo[i]가
자료구조 queue를 구현해 보자 큐가 뭔지 다 알것이라 생각한다. 바로 코드부터 보자 아 그전에 연결리스트로 구현 할 것이다. Q. 하... ㅆ ㅣ.. ㅂ...... A. ㅎㅎ;; ㅈㅅ.. ㅋㅋ!! struct node { int x, y; struct node* next; }; struct node* f, * r; void push(int, int); struct node pop(); void push(int x, int y) { struct node*
알고리즘 merge sort, quick sort를 구현해 보자 걱정이다. 이제 슬슬 내가 알고있는게 다 떨여저 간다. 근데 글쓰는거 왤케 재밋냐. 제목보고 들어왔을테니 정렬구현할꺼다. 머지소트랑 퀵소트(+ 간단한 함수포인터) 그리고 문제로 검증받아야 하니 여러문제의 풀이코드를 올리도록 하겠다. 그전에 신세한탄좀 하자 내가 std::sort()이 함수때문에 C++를 진입하지 못하고 '하... 모르겠다 걍 구현하고 말지' 라는 생각으로 'C'로 문제를 풀어왔다. 이
자료구조 priority_queue를 구현해 보자 사실 난 알고있는 알고리즘이 몇개 없다. 그래서 그나마 조금 할줄아는 구현글을 써보고자 한다. 사실 다른자료구조 부터 먼저 할려고 했지만 이 글이 나오자마자 우선 priority queue(이하 pq)부터 하고자 맘먹었다. pq는 매우 좋은 자료구조라 할 수 있다. 그 범용성도 매우 넓다. 예를들어 https://www.acmicpc.net/problem/1753 https://www.
백준 BOJ 11724 연결 요소의 개수 출처 : https://www.acmicpc.net/problem/11724 아 먼저 참고할건 이 글은 문제 풀이랑은 상관이 없다.(맨 밑에 정답코드는 넣었다.) 입력을 한번 보자 vn, en이 먼저 주어지고 아래 무방향 엣지 정보인 u v가 주어진다. 여기서 우리는 그래프를 표현해야되는데 가장 짜증 나는건 나는 'C'로 문제를 푼다는 것이다. Q. 인접행렬로 그래프 표현해
