[Gold IV] 문자열 폭발 - 9935 문제 링크 성능 요약 메모리: 94712 KB, 시간: 396 ms 분류 자료 구조, 스택, 문자열 제출 일자 2023년 6월 19일 08:52:36 문제 설명 상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다. 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다. 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다. 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다. 상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 ..
[Silver IV] 주몽 - 1940 문제 링크 성능 요약 메모리: 70104 KB, 시간: 24 ms 분류 정렬, 두 포인터 문제 설명 주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다. 갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이..
[Gold V] 탑 - 2493 문제 링크 성능 요약 메모리: 106148 KB, 시간: 380 ms 분류 자료 구조, 스택 문제 설명 KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다. 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에..
메모이제이션 메모이제이션이란 동일한 계산을 반복할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 실행 속도를 빠르게 하는 기술입니다. 이는 동적 계획법(Dynamic Programming)에서 핵심이 되는 기술입니다. 캐싱이라고 표현되기도 합니다. 예를 들어 재귀 함수를 사용한 피보나치 수열 함수가 있다고 해봅시다. func fibonacci(_ n: Int) -> Int { if n Int { var fiboArray: [Int] = [0, 1] guard n > 1 else { return n } for num in 2...n { fiboArray.append(fiboArray[num - 2] + fiboArray[num - 1]) } return fiboArray..
LCS LCS란 보통 최장 공통 부분수열(Longest Common Subsequence)을 의미하지만, 최장 공통 문자열(Longest Common Substring)을 말하기도 합니다. 여기에서 부분수열(Subsequence)과 문자열(Substring)의 차이는 문자열이 연속적인지 아닌지에 따라 달라지는데요, 연속적이라면 문자열(Substring)이고, 비연속적이면 부분수열(Subsequence)입니다. 다음과 같은 예시가 있다고 가정해봅시다. [AUTABBEHNSAAB, BCUAMEFKAJNAAB] 위 예시에서 AAB는 연속적이기 때문에 문자열이라고 할 수 있고, UAENAAB는 비연속적이기 때문에 부분 수열이라고 할 수 있습니다. 위에서 말한 두 가지의 LCS를 구현하는 방법에 대해 알아보겠습니..
