버러범의 개발이야기

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

원모양의 성벽이 있다 각 성벽안에는 또 다른 성벽이 있을 수 있다.

성벽들의 좌표와 반지름이 주어졌을때 가장 성벽을 많이 넘어야 하는 두 지점 간을 이동하기 위해 몇 번이나 성벽을 넘어야 하는지 계산하는 문제다.

성벽 안에 성벽이 있을때 바깥에 있는 성벽을 조상노드 안쪽에 있는 성벽을 자손 노드로해서 성벽들의 정보를 트리로 표현할 수 있다.

구현한 트리에서 최장 경로의 길이가 곧 구하고자하는 문제의 답이 된다.

트리의 최장 경로의 길이는 트리의 서브트리가 두개이상 있을경우 서브트리들 중 높이가 가장 큰 두 서브트리의 높이합 +2이다.

트리의 서브트리가 한개 이하일 경우 서브트리의 높이 +1이 최장 경로의 길이가 된다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/21.%20Tree%20traversal/FORTRESS.cpp

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

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

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

트리의 전위순회와 중위순회 결과가 주어졌을때, 해당 트리의 후위 순회를 출력하는 문제이다.

전위순회 결과의 첫번째 원소는 해당 트리의 루트이고, 중위순회 결과에서 루트를 찾아 루트의 왼쪽은 왼쪽 서브트리 오른쪽은 오른쪽 서브트리로 나눌 수 있다.

또한 이렇게 해서 얻은 각각의 서브트리의 크기를 이용해서 전위순회 또한 왼쪽 서브트리의 출력과 오른쪽 서브트리의 출력을 구분 할 수있다.

이제 전위순회와 중위순회를 각각 왼쪽 서브트리와 오른쪽 서브트리로 나눌 수 있으므로 나눠서 재귀호출한다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/21.%20Tree%20traversal/TRAVERSAL.cpp

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

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

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

문자열이 주어졌을때, 해당 문자열의 부분 문자열중 k번 이상 등장하는 문자열을 '말버릇'이라고 한다.

가장 긴 말버릇의 길이를 구하는 문제이다.

먼저 주어진 배열의 접미사 배열들을 사전순으로 나열한다. 그리고 어떤 부분 문자열 X가 출현하는 위치가 K군데 있다고 하자.

X는 K개의 접미사의 접두사가 된다. 이들 접미사는 항상 앞서 사전순으로 정렬한 접미사 배열에 인접하게 정렬됬어야 한다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/20.%20string/HABIT.cpp

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

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

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

문자열을 시계 방향, 반시계 방향 번갈아가면서 시프트하여 목표하는 문자열과 일치하려 했을때 필요한 최소 시프트 횟수를 구하는 문제이다.

문자열의 일치는 kmp알고리즘(유명하고 많이 쓰이는 알고리즘이지만 이해하기 다소 어렵다,,,)을 이용하여 풀 수 있다.

현재 문자열을 시계 방향으로(오른쪽으로) 시프트 해서 다음 문자열과 일치할때의 최소 시프트 횟수를 알고 싶다면,

다음 문자열을 두개 이어붙인 문자열과 현재 문자열을 kmp알고리즘으로 비교하면 된다.

이때 kmp알고리즘에서 나오는 벡터의 첫번째 요소가 최소 시프트 횟수가 된다.

반시계 방향으로(왼쪽으로) 시프트 해서 다음 문자열과 일치하는것은

현재 문자열을 두개 이어붙이것을 다음 문자열이 오른쪽으로 시프트하는것을 비교하여 일치할때의 시프트 횟수를 찾으면 된다.

즉, 반시계 방향일때는 shifts 함수의 매개변수 순서만 바꿔주면 된다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/20.%20string/JAEHASAFE.cpp

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

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

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

숫자들이 순차적으로 주어졌을때 해당 수열의 부분수열 합이 k인 경우의 수를 찾는 문제이다.

수열의 길이가 최대 50000000인것을 감안하면 수열을 값을 미리 계산하여 배열을 선언하고 거기에 담는 방식은 불가능 하다.

다른 방법으로는 프로그램이 실행될때 실시간으로 값을 생성하는것이 있다.

이를 위해서 구조체와 메서드를 작성하고 순차적으로 값을 생성해서 큐에 넣어 관리한다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/19.%20QueueStackDeque/ITES.cpp

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

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

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

( ) { } [ ] 이렇게 세 종류의 괄호를 나열한 문자열이 주어졌을때 해당 문자열이 짝이 맞는지를 확인하는 문제이다.

여기서 짝이 맞는다는 표현은 다음 세가지 조건을 모두 지켰을 경우를 말한다.

- ( 는 ) 와, { 는 } 와, [ 는 ]와 짝을 이루어야만 한다.

- 모든 괄호 쌍은 먼저 열린 뒤 닫힌다.

- 한 괄호 쌍이 다른 괄호쌍과 서로 '교차해' 있으면 안된다. 이 정의에 의하면 [ ( ] ) 는 짝이 맞지 않는 경우이다.

스택을 이용하면 다음과 같은 방식으로 문제를 풀 수 있다.

문자열을 순회하면서 열린괄호면은 스택에 넣는다.

닫힌 괄호면 현재 스택의 탑에 있는것과 대응한다면 스택의 탑을 pop하고 대응하지 않는다면 false를 리턴한다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/19.%20QueueStackDeque/BRACKETS2.cpp

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

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

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

조세푸스를 포함해서 병사들이 원형으로 앉아 순서대로 죽는다.

첫번째 병사가 처음으로 죽으면, 시계방향으로 k번째 사람이 죽기를 반복하다가 조세푸스를 포함한 병사 하나만 살아 남았을때 죽는것을 멈춘다고 한다.

이렇게 조세푸스가 마지막 두명중 하나가 되기 위해서는 조세푸스는 첫번째 병사로부터 몇자리 떨어진 곳에 있어야 하는지 구하는 문제이다.

이 문제를 풀려면 요소들을 순회하면서 삭제하는 작업을 반복적으로 해야한다.

이때 우리는 다양한 곳에서 요소를 추가/삭제할때 상수시간복잡도를 가지는 연결리스트( list )를 활용할 수 있다.

배열( vector, int[] )의 경우 맨 뒤 이외의 위치에서 원소 추가/삭제를 수행할때 선형시간복잡도를 가진다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/18.%20linearDS/JOSEPHUS.cpp

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

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

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

상자마다 인형이 담겨있는 갯수가 각각 다르게 주어졌을때, 아이들k명에게 똑같은 갯수의 인형을 남는 인형 없이 나누어 주려 한다.

주문을 할때 'h번 상자부터 t번 상자까지 다 주세요'(h<=t)라고만 할 수있다.

한번 만 주문할 수 있는 경우 가능한 주문 방법,

한 상자가 주문에 중복으로 포함 되지 않게끔 여러번 주문 할수 있는 경우 최대 주문 횟수, 이렇게 두가지를 구하는 문제이다.

h에서 t까지 구입했을때 남기지 않고 나눠줄 수 있는 경우는 (psum[t]-psum[h-1])%k==0인 경우다.

한번 만 주문할 수 있는 경우 가능한 주문방법 = 나머지가 같은 것들끼리 묶고, 각 묶음에서 두개를 뽑는 조합의 경우

0번부터 i번까지의 상자가 있고, 여러번 주문 할때 최대 주문 횟수를 maxBuys(i)라 할때

maxBuys(i) = max( maxBuys(i-1), maxBuys(j)+1) (이때 j는 psum[i]==psum[j]인 i보다 작은 최댓값)

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/17.%20partial%20sum/CHRISTMAS.cpp

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

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