버러범의 개발이야기

알고스팟 문제 링크: 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

BOJ 문제 링크: https://www.acmicpc.net/problem/17836

(n,m)크기의 성 입구 (1,1)에서 시작해 (n,m)위치에 있는 공주를 구하는 문제이다.

용사는 현재 무기로는 마법의 벽을 통과할 수 없으며, 성 어딘가에 반드시 한개 존재하는 '그람'을 얻으면 벽을 부수며 성내부를 이동할 수 있다.

기본적인 틀은 bfs를 사용한다. bfs를 이용하면 성에 각 칸을 최초로 발견할때마다 해당 칸을 최단시간에 발견한게 된다.

현재 상태에서 이동할 수 있는 다음칸들을 탐색할때 다음칸에 해당하는 cache가 비어있을 경우에만 queue에 push하고,

다음 칸들을 최초로 탐색할때마다 최초 탐색 시간을 cache에 저장한다.

만약 다음칸들을 탐색하다가 공주를 봤다면 현재시간 + 1 을 바로 return한다.

이때 cache는 '그람'을 소지했는지에 대한 상태도 나타낼수 있어야 하므로 3차원 배열로 표현한다.

코드 원본: https://github.com/sbl133/BOJ/blob/main/%2317836.cpp

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

알고스팟 문제 링크: 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

BOJ 문제 링크: https://www.acmicpc.net/problem/3190

뱀이 1행1열을 시작으로 N*N크기의 게임판을 매 초마다 이동하는데 다음과 같은 규칙을 따른다.

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

L개의 줄로 뱀의 방향 변환 정보또한 주어지는데 정수 x와 문자 c로 이루어져 있으며, 게임 시작 시간으로부터 x초가 끝난 뒤에

왼쪽(c가 'L')또는 오른쪽(c가 'D')로 90도 방향을 회전시킨다는 뜻이다.

뱀이 다음으로 전진할 위치를 방향에 맞게 구한다.

만약 다음 위치가 벽에 막히거나 몸통과 부딪친다면 게임을 끝낸다.

다음 위치에 사과가 있는경우 사과를 없애고 꼬리를 전진시키지 않는다. 만약 이번턴에 방향을 전환해야 된다면 방향또한 전환 시킨다.

코드 원본: https://github.com/sbl133/BOJ/blob/main/%233190.cpp

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

알고스팟 문제 링크: 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

BOJ 문제 링크: https://www.acmicpc.net/problem/14500

정사각형 4개를 이어 붙인 폴리오미노를 테트로미노라 한다.

테트로미노를 90도 회전, 대칭 해서 만들 수 있는 모든 모양의 블럭들중 하나를 각 칸마다 숫자가 적혀있는 N*M종이위에 놓는다.

이때 블럭으로 덮은 칸들의 수들의 합이 최대가 되는 경우를 구하는 문제이다.

먼저 필요한것은 테트로미노로 만들 수 있는 모든 블럭들의 경우들을 구하는 것이고, 총 19개의 경우가 있다는걸 알 수 있다.

가장 직관적인 방법은 이 19개의 블럭들을 하나하나 좌표로 표현해서 푸는 방법이다.

다른 방법으로는 재귀를 이용해 블럭을 한칸씩 4가지 방향으로 4번 확장시키고 나머지 예외를 처리하는 방법이 있다.

첫번째 방법은 블럭들의 좌표를 하나하나 좌표로 표현한다는게 너무 하드코딩 아닌가 생각이들 수 있다.

하지만 두번째 방법으로 풀더라도 블럭들의 모든 경우를 생각해야 하며 해당 알고리즘으로 커버하지 못하는 모양( ㅗ, ㅓ, ㅏ, ㅜ)

들을 예외처리 해야한다는 부담이 있기 때문에 첫번째 방법으로 풀었다.

코드 원본: https://github.com/sbl133/BOJ/blob/main/%2314500.cpp

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

알고스팟 문제 링크: 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