백준 BOJ 18189 참 어려운 문제 https://www.acmicpc.net/problem/18189 문제 설명 i번 정점의 색이 A[i]인 크기가 N인 트리가 주어질 때, 색깔이 같은 두 정점을 고르면, 이 둘은 항상 조상-자식 관계가 아니다 의 조건을 만족하는 루트가 될 수 있는 정점을 모두 찾아라. 풀이 r을 루트로 하는 트리에서 모든 정점 v에 대해 색이
백준 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) 이것을
백준 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.
백준 BOJ 17143 낚시왕 문제 : https://www.acmicpc.net/problem/17143 아마 코테시즌이 되면 백준에 질문이 가장 많이 올라오는 문제가 아닐까싶은 문제, 낚시왕이다. 개인적으로 기출로 나왔던 시뮬레이션 문제들이 대부분 디스크립션을 한 번에 알아보기 힘들어서 늘 몇 번씩 읽어봤었는데 이 문제는 바로 로직을 구성할 수 있을 정도여서 코드를 짜는데 그렇게 오래걸리지는 않았다. 이런 시뮬레이션 문제에서
자료구조 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*
백준 BOJ 5916 농장관리 나는 야호다. 오늘은 농장관리라는 문제를 풀어볼거다. 문제: https://www.acmicpc.net/problem/5916 문제는 HLD의 기본문제다. HLD의 설명은 /hld 를 봐라. HLD의 기본만 알고있다면, 약간 까다로운 점이 존재하는데, 바로 이 문제의 쿼리가 노드에 있는게 아니라, 간선에 있다는 점이다. 간선 쿼리의 경우에는 그 간선이 자식쪽에 해당하는 노드에 속해있다고 생각하면 된다. 따라서
알고리즘 merge sort, quick sort를 구현해 보자 걱정이다. 이제 슬슬 내가 알고있는게 다 떨여저 간다. 근데 글쓰는거 왤케 재밋냐. 제목보고 들어왔을테니 정렬구현할꺼다. 머지소트랑 퀵소트(+ 간단한 함수포인터) 그리고 문제로 검증받아야 하니 여러문제의 풀이코드를 올리도록 하겠다. 그전에 신세한탄좀 하자 내가 std::sort()이 함수때문에 C++를 진입하지 못하고 '하... 모르겠다 걍 구현하고 말지' 라는 생각으로 'C'로 문제를 풀어왔다. 이
자료구조 priority_queue를 구현해 보자 사실 난 알고있는 알고리즘이 몇개 없다. 그래서 그나마 조금 할줄아는 구현글을 써보고자 한다. 사실 다른자료구조 부터 먼저 할려고 했지만 이 글이 나오자마자 우선 priority queue(이하 pq)부터 하고자 맘먹었다. pq는 매우 좋은 자료구조라 할 수 있다. 그 범용성도 매우 넓다. 예를들어 https://www.acmicpc.net/problem/1753 https://www.
백준 BOJ 13546 수열과 쿼리 4 H9 하위! 적당히 올릴 거 찾다 수쿼4를 낚아왔다. 뭐.. 풀 때는 고통받으며 푼거 같지만 모스를 안다면 심각히 힘든건 없어보이니 각설하고 풀이하자. 문제: BOJ 13546 수열과 쿼리 4 어떤 수열이 주어졌을 때 같은 두 값이 최대한 멀리 떨어진 거리를 구하는 문제이다. 이 문제를 푼다면, BOJ 13545 수열과 쿼리 0도 가볍게 날먹할
백준 BOJ 8291 Coprime Numbers 문제: https://www.acmicpc.net/problem/8291 길이가 n인 배열에서 서로소 쌍의 수를 구하는 문제 a[i]: arr[]에서 i의 개수 b[i]: arr[]에서 i의 배수의 개수 c[i]: gcd(arr[], arr[])가 i의 배수인 쌍의 개수 d[i]: gcd(arr[], arr[])가 i인 쌍의 개수 a[], b[], c[
백준 BOJ 17274 카드 공장 문제 : https://www.acmicpc.net/problem/17274 지문이 짧고 간단하다. 앞면은 A, 뒷면은 B로 카드쌍이 주어지는데 K라는 숫자가 주어질 때마다 전체 카드 중 현재 보이고 있는 면이 K이하인 카드를 모두 뒤집어주면 된다. 가장 먼저 떠오르는 방법은 매 쿼리마다 전체 카드를 보면서 하나씩 뒤집어주는 것이지만 전체 카드의 개수와 쿼리의 개수는 각각
백준 [BOJ : 16932]모양 만들기 하악하악 커동빵디 [분류] : 탐색(DFS) [조건]: 0으로 채워진 칸을 1로 바꾸었을때 연속적으로 존재하는 1의 개수가 가장 최대임을 찾으면 됩니다. [과정] : 1)먼저 연속적으로 붙어있는 1로 채워진 칸들이 존재한다면 이들을 구분해 주기 위해 그룹화를 진행해야 된다.(그룹화를 진행 해야되는 이유는 '구현방법'에서 설명하겠습니다.) 2)그룹화가 진행되면서 동시에 그룹화 된 그룹들의 원소의 수를
백준 BOJ 11724 연결 요소의 개수 출처 : https://www.acmicpc.net/problem/11724 아 먼저 참고할건 이 글은 문제 풀이랑은 상관이 없다.(맨 밑에 정답코드는 넣었다.) 입력을 한번 보자 vn, en이 먼저 주어지고 아래 무방향 엣지 정보인 u v가 주어진다. 여기서 우리는 그래프를 표현해야되는데 가장 짜증 나는건 나는 'C'로 문제를 푼다는 것이다. Q. 인접행렬로 그래프 표현해
백준 BOJ 15481 그래프와 MST 문제 : https://www.acmicpc.net/problem/15481 어떤 임의의 연결그래프가 주어졌을 때, 모든 간선에 대해서 해당 간선이 포함되는 MST의 가중치의 합을 구하라는 문제이다. 잘 생각해보면 간선을 MST에 이미 포함된 간선과 포함되지 않은 간선으로 나눌 수 있는데, 이 때 MST에 이미 포함된 간선에서의 MST 가중치 합은 너무 당연하게도 전체 MST의 가중치
백준 BOJ 3666 리스크 풀이 나는 talALGO 팀의 ploffer11 이다. Network Flow 문제들을 풀다 보면 자연스럽게 풀이가 없는 문제들도 풀게 되는 경우가 종종 있다. 3666이 대표적인 예인데, 일단 이 문제, 디스크립션부터 조금 애매하다. 조건부터 제대로 정리하고 넘어가겠다. Condition 1. 주둔하는 군대는 0이 될 수 없다. 2. 각 군대는 최대 한 칸 움직일 수 있다. 3.
