버러범의 개발이야기

알고스팟 문제 링크: https://www.algospot.com/judge/problem/read/DICTIONARY

새롭게 정의된 사전순으로 입력된 단어들을 통해 새로운 사전순의 알파벳 순서를 알아내는 문제이다.

dfs를 이용한 위상 정렬을 사용하면 문제를 풀 수 있다.

dfs를 사용하면 어차피 우선순위가 낮은 알파벳 먼저 order에 push되므로 들어오는 간선이 하나도 없는 정점들을 굳이 먼저 탐색하지 않아도 된다.

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

알고스팟 문제 링크: https://algospot.com/judge/problem/read/EDITORWARS

n개의 노드에 관한 m개의 관계가 주어진다.

만약 ack a b 라고 하면 a, b 가 같은 집합에 속해야 하고 만약 dis a b 라고 하면 a, b 가 서로 다른 집합에 속해야 한다.

이때 어떤 집합에 속할 수 있는 노드의 최대 갯수를 구하는 문제이다.

상호배타적집합을 사용하면 문제를 풀 수 있다.

한가지 주의할 점은 enemy라는 vector를 이용하여 적대관계(서로 다른 집하에 속해야만 하는)에 있는 집합의 루트 정보를 유지해야한다.

동지의 적은 적이므로 ack일때 merge할 상대와 적대관계에 있는 집합끼리 merge를 해야한다.

적의 적은 동지이므로 dis일때 dis인 상대의 적과 merge를 해야한다. 

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/25.%20disjointSet/EDITORWARS.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

알고스팟 문제 링크: https://algospot.com/judge/problem/read/MEASURETIME

길이 N인 수열 A[]가 주어지고, A[]를 삽입정렬했을때 정렬 과정에서 숫자들을 총 몇 번이난 옮기는지 계산하는 문제이다.

일단 모든 노드의 값이 0인 팬윅트리를 생성한다. A[]의 요소를 왼쪽부터 탐색해서 각 값에 해당하는 팬윅트리 노드들의 값을 1씩 증가시킨다. 또한 자신보다 큰 값이 나왔던 횟수를 구하기 위해 전체 횟수 합에서 자신이하의 값이 나온 횟수합을 뺀다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/24.%20segmentTree/MEASURETIME.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

알고스팟 문제 링크: https://algospot.com/judge/problem/read/FAMILYTREE

0번 노드는 루트이고 1번부터 n-1번까지 각 노드의 parent의 번호가 주어진다.

정수로 노드의 번호 a, b가 주어질때 a와 b사이의 촌수(거리)를 구하는 문제이다.

문제에 제시된 트리를 전위탐색하면서 노드를 방문할때마다 trip이라는 vector안에 넣는다. 이때 depth와 현재 노드의 최초 방문 순서를 저장한다.

trip을 활용하여 RMQ를 생성하고 a, b의 공통조상을 찾는데 활용한다.

a, b의 거리는 ( a의 depth - 공통조상의 depth ) + ( b의 depth - 공통조상의 depth) 이다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/24.%20segmentTree/FAMILYTREE.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

알고스팟 문제 링크: https://algospot.com/judge/problem/read/MORDOR

등산로에는 일정 간격으로 해발고도를 나타내는 표지판이 있다. 

등산로의 부분구간을 등산하는 등산로가 있다. 등산중에 만나는 표지판중 최대 해발고도와 최소해발고도의 차이가 등산로의 난이도이다.

표지판 정보와 등산로의 구간이 주어질때 해당 등산로의 난이도를 구하는 문제이다.

등산로의 표지판 정보들을 선형탐색해서는 최대 최소를 찾는다면 시간안에 문제를 풀 수 없다.

구간 최소 쿼리(range minimun query, RMQ)를 이용하여 문제를 풀어보자.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/24.%20segmentTree/MORDOR.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

알고스팟 문제 링크: https://algospot.com/judge/problem/read/RUNNINGMEDIAN

수열을 다음과 같은 방법으로 추가한다고 하자.

A[0] = 1983

A[ i ] = (A[ i-1 ] * a + b) % 20090711

한 수열의 중간값은 수열에 새로운 수가 추가될 때마다 바뀔 수 있다.

수열에 새로운 수가 추가될 때마다 해당 수열의 중간값의 다 더한 중간값의 합을 20090711로 나눈 나머지를 구하는 문제이다.

수열을 추가해 나갈때 다음과 같은 불변식을 지키며 최대, 최소 힙을 유지한다면 최대 힙의 top값이 현재 수열의 중간값이 된다.

1. 최대힙의 크기는 최소힙의 크기와 같거나 1 더 크다.

2. 최대힙의 top값 <= 최소힙의 top값

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/23.%20priorityQueue%20and%20Heap/RUNNINGMEDIAN.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

알고스팟 문제 링크: https://algospot.com/judge/problem/read/INSERTION

크기가 n이고 1~n까지의 순서없이 섞여있는 수열이 있다.

해당 수열의 원래 형태는 알 수 없지만, 수열을 삽입 정렬하는 경우 각 원소가 왼쪽으로 몇 칸이나 이동했는지가 입력으로 주어진다.

이때 원래 수열을 찾아내는 문제이다.

원래수열이 A[]라 할때 마지막 숫자 A[n-1]이 왼쪽으로 몇 칸 움직였는지를 알면 A[n-1]이 어떤 숫자인지 알 수 있다.

만약 n이 5이고 마지막 숫자가 왼쪽으로3칸 움지였다면, 1~5의 숫자중 마지막 숫자보다 큰게 3개 있다는 것이고

이것은 마지막 숫자가 2라는것을 의미한다.

이러한 방법으로 트립을 이용해 k번째 숫자를 찾고 해당 노드를 삭제하는 방식으로 끝에서부터 수열을 맞춰갈 수 있다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/22.%20BinarySearchTree/INSERTION.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

알고스팟 문제 링크: https://algospot.com/judge/problem/read/NERD2

p와 q가 다음과 같이 정의된다.

p: 알고스팟 온라인 채점 시스템에서 푼 문제의 수

q: 밤 새면서 지금까지 끓여먹은 라면 그릇 수

대회에 참가하려는 신청자 a의 문제 수 pa와 그릇 수 qa를 다른 참가 신청자 b의 문제 수 pb와 그릇 수 qb에 비교한다.

이때, pa < pb && qa < qb 이면 신청자 a는 대회에 참가할 수 없다.

한 사람의 참가 가능 여부는 다른 사람들의 문제와 라면 그릇 수에 의해 결정 되기 때문에,

대회에 참가할 수 있는 사람의 수는 새로운 사람이 참가 신청을 할 때마다 계속 바뀐다.

신청자들 각각의 p와 q를 x, y로 바꿔서 이차원 평면의 점들로 생각해보자.

대회에 참가하기 위해서는 기존의 점들보다 x값이 크거나 y값이 크거나 둘중 하나는 해야된다.

이는 곧 신청자의 (p,q)에서 p에 바로 오른쪽 점의 y좌표가 q보다 작아야 한다.

위 기준에 맞아서 새 신청자를 참가시킬시에는 새점 (p,q)에서 p에 왼쪽에 있는점의 y좌표가 q보다 작다면 더 이상 대회에 참가할 수 없다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/22.%20BinarySearchTree/NERD2.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2