버러범의 개발이야기

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

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

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

수열 S가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 문제이다.

재귀를 이용해서 현재 상황에서 바이토닉을 만들 수 있는 경우를 각각 따져가면서 가장 긴 경우를 반환하는 식으로 문제를 풀 수 있다.현재 상황을 구분하는 변수들로는 curPos(수열 S에서의 현재 위치), lastNum(가장 최근에 바이토닉의 일부로 고른 숫자),isDec(현재 만들고 있는 바이토닉이 증가중인지 감소중인지) 이렇게 3개가 있다.

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

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

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

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

슬라임이 각 에너지를 갖고 있고, 두 슬라임이 합쳐져서 생긴 슬라임이 갖는 에너지는 두 슬라임의 에너지 곱과 같다.

두 슬라임을 합치기 위해서는 각 슬라임이 갖고 있는 에너지의 곱만큼의 전기가 필요하다.

여러개의 슬라임이 주어졌을때 이 슬라임들을 하나의 슬라임으로 만들기 위한 전기의 최솟값을 구하는 문제이다.

직관적으로 에너지가 최소인 두 슬라임을 합쳐가기를 반복하는 그리디 알고리즘을 사용하면 답을 구할 수 있을거 같다.

priority_queue를 사용하면 이를 쉽게 구현할 수 있다.

참고로 원래 그리디 알고리즘을 사용할때는 정당성증명까지 신경쓰면서 문제를 풀어야 되지만,

이전에 알고스팟 문제로 풀었던 문자열 합치기랑 정당성증명 부분이 똑같은거 같아서 그냥 그리디 알고리즘을 사용했다.

MOD를 사용하는 부분에서 마지막에만 나머지를 취하는게 아니라 계산 도중 ret값에 나머지를 취하는걸 볼 수 있는데,

이렇게 하는 이유는 ret값이 longlong범위를 벗어나 오버플로우가 나는 것을 방지하기 위해서다.

이렇게 할수 있는 이유는 (A * B * C * D * . . . ) % MOD == (A * MOD) * (B * MOD) * (C * MOD) * (D * MOD) * . . . 의 원리와 같다.

사실 문제를 풀면서 계속 시간초과가 나와서 엄청 헤맸다. 처음에는 알고리즘 자체에 효율성이 떨어져서 시간초과가 나는줄 알고 한참 생각했다.

그러다 도저히 모르겠어서 일단 입출력을 cin, cout보다 빠른 scanf, printf를 바꿔서 제출했더니 정답이 나..왔더뻐..ㄱ

앞으론 scanf, printf를 더 애용해야겠다.

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

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

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

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

각 알파벳 A, B, C, . . ., Z 순서대로 1, 2, 3, . . ., 26만큼의 화폐가치가 있다.

길이가 N인 알파벳을 나열한 문자열을 만들어서 각 문자의 화폐가치의 합이 X인 문자열 화폐를 만들려한다.

주어진 조건을 충족하면서 사전순으로 가장 빠른 문자열을 출력하자.

문자열이 사전순으로 가장 앞서려면 A를 앞쪽에 최대한 많이 나열하면 된다는것을 직관적으로 알수 있다.

그러기 위해서는 Z를 뒤로 최대한 많이 배치해서 주어진 화폐가치를 최대한 채우고, 남은 자리는 A로 채운다.

이때, A와 Z사이에 남은 화폐가치를 채우기 위한 가치가 2~25사이인 문자가 하나 올 수 있다.

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

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

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

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

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

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

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

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

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

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