전체 글
[백준] 공통 부분 문자열
https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net lcs, lcp 문제로 흔히 불리우는 문제의 장르입니다. (dp로 해결) (이 문제는 longest substring 문제로 잘 알려져있습니다.) 우선 문제부터 간단하게 요약하면, 두 string이 input으로 들어오면, 해당하는 두 string의 부분 string중 가장 길이가 긴 것의 문자열 길이를 return 해야합니다. 간단한 그림을 통해 아이디어를 살펴봅시다. dp array..
[백준] 문자열 폭발
https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 스택(stack)을 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 문자열이 있고, 폭탄이 주어집니다. 문자열중 폭탄에 해당하는 문자열이 있는 경우 사라집니다. 이렇게 사라진 문자열에서 또 다시 폭탄에 해당하는 문자열이 있으면 또 사라집니다. 이 과정을 반복해 남는 문자열을 만드는 문제입니다. python에서는 문자열의 find 메소드를 제공합니다. 가장 처음에는 이 방법을 ..
[백준] N과 M (2)
https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net itertools 라이브러리의 combination을 이용해서 해결하는 문제입니다. 우선 문제부터 간단하게 요약하면, N과 M이 주어지면, 1~N의 숫자중 중복없이 M개를 고른 수열을 사전순으로 출력해야 하는 문제입니다. itertools의 combination의 경우 combination을 어떻게 구성하는지 출력해보면 다음과 같이 사전순으로 출력하는 것을 알 수 있습니다. 따라서 sorted된..
[백준] 2048 (Easy)
https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 구현 문제입니다. 문제부터 아주 간단하게 요약하면, 흔히 우리가 플레이 하는 2048을 문제에서 주어진 조건에 맞게 implement 하는 문제입니다. 이 때, 총 5번의 이동을 거친후 남게 될 수 있는 가장 큰 숫자가 무엇인지를 return 해야 합니다. move 함수는 현재 보드의 상태와, 이동방향을 받아서 새로운 보드를 만들어주는 함수입니다. 이 move 함수만 ..
[백준] 웜홀
https://www.acmicpc.net/problem/1865 1865번: 웜홀첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net벨만포드(Bellman ford) 알고리즘을 사용해야하는 문제입니다. 우선 문제부터 간단하게 요약하면, 도로는 양의 간선으로 양방향으로 구성되고, 웜홀은 음의 간선으로 단방향으로 구성됩니다. 이렇게 그래프가 구성되었을 때, random한 출발지 A 에서 다시 A로 간선들을 타고 되돌아 왔을 때, 음의 weight를 가지는 것이 하나라도 존재하면, YES를 아니면 NO를 출력해야 합니다. ..
거듭제곱 분할정복
# 11^12를 구해야하면 # exp(11,12)를 하면 됨 # 실제 사용시 recursion함수이기에 recursion error와 # 나머지를 return 하라는 문제조건 등에 유의하기 # ps: 나머지를 return 해야할시 return이 붙은 모든곳에서 나누어주어야함!! def exp(base: int, expo: int) -> int: if expo == 0: return 1 if expo == 1: return base a = exp(base, expo//2) b = expo%2 # print(f'a,b = {a,b}') return a*a*(base**b) print(exp(2,0))