algorithm

편집 거리

편집 거리 알고리즘이란, 두 문자열의 유사도를 판단하는 알고리즘이다. 리벤슈테인 거리라는 이름으로도 불린다. 문제를 통해 알아보자. 문제 두 개의 문자열 A와 B가 주어졌을 때, 문자열 A를 편집하여 문자열 B를 만들고자 한다. 문자열 A를 편집할 때는 다음의 세 연산 중에서 한 번에 하나씩 선택하여 이용할 수 있다. 삽입 : 특정한 위치에 하나의 문자를 삽입한다. 삭제 : 특정한 위치에 있는 하나의 문제를 삭제한다. 교체 : 특정한 위치에 있는 하나의 문자를 다른 문자로 교체한다. 이때 편집 거리란 문자열 A를 편집하여 문자열 B로 만들기 위해 사용한 연산의 수를 의미한다. 문자열 A를 문자열 B로 만드는 최소 편집 거리를 계산하라. 입력 문자열 A, B 각 문자열은 영문 알파벳으로만 구성되어 있으며,..

못생긴 수

문제 못생긴 수란 오직 2,3,5만을 소인수로 가지는 수를 의미한다. 1은 못생긴 수라고 가정한다. n번째 못생긴 수를 찾아라. 못생긴 수 : {1,2,3,4,5,6,8,9,10,12,15....} 입력 n (1 ~ 1,000) 출력 n번째 못생긴 수를 출력한다. 풀이 n = int(input()) ugly = [0] * n # 못생긴 수를 담기 위한 테이블 (1차원 DP 테이블) ugly[0] = 1 # 첫 번째 못생긴 수는 1 # 2배, 3배, 5배를 위한 인덱스 i2 = i3 = i5 = 0 # 처음에 곱셈 값을 초기화 next2, next3, next5 = 2, 3, 5 # 1부터 n까지의 못생긴 수들을 찾기 for l in range(1, n): # 가능한 곱셈 결과 중에서 가장 작은 수를 선택..

백준 18353 - 병사 배치하기

www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다. 또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다. 예..

금광

문제 N*M 크기의 금광이 있다. 금광은 1*1 크기의 칸으로 나누어져 있다. 채굴자는 첫 번째 열, 어느 행에서 출발하여 금을 캐기 시작한다. 이후에 m번에 걸쳐 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동한다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 구한다. 입력 첫째 줄에 테스트 케이스 T (1 ~ 1000) 매 테스트 케이스 첫째 줄에 n, m (1 ~ 20) 둘째 줄에 n*m개의 위치에 매장된 금의 개수 (1 ~ 100) 출력 매 테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기를 출력한다. 풀이 # 테스트 케이스(Test Case) 입력 for tc in range(int(input())): # 금광 정보 입력 n, m = map(int, input()...

다이나믹 프로그래밍

어떤 문제를 해결하는데 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제는 컴퓨터로도 해결하기 어렵다. 그래서 연산 속도와 메모리 공간을 최대한 활용할 수 있는 효율적인 알고리즘을 작성해야 한다. 다만, 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다. 대표적인 방법이 바로 다이나믹 프로그래밍이다. 여기 일반적인 피보나치 수열 코드가 있다. def fibo(n): if n==1 or n==2: return 1 return fibo(n-1)+fibo(n-2) 그런데 피보나치 수열의 소스코드를 이렇게 작성하면 심각한 문제가 생길 수 있다. 바로 n이 커질수록 수행 시간이 기하급수적으로 늘어나기 때문이다. 이 소스코드의 시간 복잡도는 O(2^n..

프로그래머스 - 가사 검색

programmers.co.kr/learn/courses/30/lessons/60060 코딩테스트 연습 - 가사 검색 programmers.co.kr 문제 설명 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 친구들로부터 천재 프로그래머로 불리는 프로도는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다. 그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "fro??"는 "frodo", "front", "frost" 등에 매치..

백준 2110 - 공유기 설치

www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 문제 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가..

이진 탐색

이진 탐색은 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘이다. 이진 탐색 : 반으로 쪼개면서 탐색하기 이진 탐색(Binary Search)은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 이진 탐색은 위치를 나타내는 변수 3개를 사용하는데 탐색하고자 하는 범위의 시작점, 끝점 그리고 중간점이다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는게 이진 탐색 과정이다. 이진 탐색을 구현하는 방법에는 2가지가 있다. 재귀 함수 반복문 이진 탐색 - 재귀 함수 # 이진 탐색 소스코드 구현 (재귀 함수) def binary_search(array, target, start, end): if start > end: return None mid ..