본문 바로가기

알고리즘

 (151)
[백준 / BOJ] 13506 카멜레온 부분 문자열 문제 출처 : www.acmicpc.net/problem/13506 13506번: 카멜레온 부분 문자열 문자열 S의 부분 문자열 T 중에서, 접두사(Prefix)도 될 수 있고, 접미사(Prefix)도 될 수 있고, 두 경우가 아닌 위치에도 등장하는 T를 카멜레온 부분 문자열이라고 한다. 문자열 S가 주어졌을 때, 카 www.acmicpc.net 카멜레온 부분 문자열이란, 문자열 S의 접미사이자 접두사인 부분문자열 T가 문자열S에서 한번 더 나오는 문자열을 말한다. 예를들어, fixprefixsuffix에서 fix는 카멜레온 부분문자열인데, fix가 접두사, 접미사, 그리고 중간에 한번 더 나오기때문이다. 마찬가지로 abcabcabc또한 카멜레온 부분문자열이다. 문자열 S가 주어졌을때, 가장 긴 카멜레온..
[백준 / BOJ] 14502 연구소 문제 출처 : www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net N*M그리드가 주어지고, 그리드의 상태가 주어진다. 0 : 빈칸 1 : 벽 2 : 바이러스 바이러스는 매초 상하좌우 빈칸으로 확산될수있다. 바이러스가 모두 확산된후 남아있는 빈칸의 수를 안전영역이라 한다. N*M그리드에 벽 3개를 적절히 설치했을때, 안전영역의 최대 크기를 구하는 문제다. 풀이 N과 M의 범위가 크지않아, 완전탐색으로 풀리는문제다. 시간복잡도는 1. N*M그리드 에서 3개의 빈칸을 선택하는 경..
[백준 / BOJ] 18119 단어 암기 - Trie 문제 출처 : www.acmicpc.net/problem/18119 18119번: 단어 암기 준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다. 다음과 같은 쿼리들이 주 www.acmicpc.net 준석이가 영어단어를 외울려고한다. 사전에 N가지 단어가적혀있으며, 모든 단어는 소문자로만 이루어져있다. 준석이는 처음에 모든 알파벳을알고있지만, 쿼리가 주어질때마다 알파벳을 까먹을수도 까먹은 단어를 기억할수도있다. 단어장에 적혀있는 N개의 단어와 M번의 쿼리 가 주어졌을때, 각 쿼리마다 준석이가 기억하는 단어의 개수를 출력하는 문제다. 풀이 최악의 경우, N = 10000 이때 각 단어의 길이..
[백준 / BOJ] 5639 이진 검색 트리 문제 출처 : www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 트리를 전위 순회한 결과가 주어졌을때, 트리를 후위순회한 결과를 출력하는문제다. 풀이 문제는 간단한데 입력은 그렇지 않았다.. 처음에는 완전이진트리를 생각하고 구현하다가 런타임에러가 떴다(배열 범위 초과). 다시 잘 읽어보니 노드가 한쪽으로 쭉 늘어날수있었다. 완전이진트리로 구현할려면, 배열의 범위가 2^10000 까지 가야해서 이 방법으로는 풀수없다. 런타임에러 코드 더보기 런타임에..
[백준 / BOJ] 16953 A -> B 문제 출처 : www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 정수 A와 B가 주어진다. A에 *2연산과, A*10+1연산을 할수있을때, A를 B로 바꾸는데 필요한 최소연산횟수를 구하는 문제다. 이때, A를 B로 바꾸지 못한다면, -1을 출력하면 된다. 풀이 전형적인 BFS문제다. BFS알고리즘은 자기와 가까운 위치부터 탐색하기때문에, 항상 최소연산으로 A를 B로 바꿀수있다. A와 B의 범위가 최대 10억이기때문에, check배열로는 같은숫자방문을 체크해줄수없다. 하지만, 연산의 증가폭이 넓기때문에, 모든경우를 다 봐줘도 시간초과가 나지않는다. 예시로, 1. *2 연산은 32번만 반..
[백준 / BOJ] 1918 후위 표기식 문제 출처 : www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net 중위 표기법으로 입력된 수식을 후위표기법으로 바꾸는문제다. 후위표기법이란, 연산자가 피연산자 뒤에 위치하는 표기법이다. 후위 표기법의 예는 A+B = AB+ A+B*C = ABC*+ A*B+C = AB*C+ A*(B+C) = ABC+* 등이 있다. 풀이 구현문제다... 재귀로 풀었다. 처음에는 연산자를 피연산마 맨뒤에 쌓아놓기만 하면 되는거로 구현했다가 다 지우고 다시짰었다... 문제에서..
[백준 / BOJ] 11660 구간 합 구하기 5 문제 출처 : www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net N과 M이 주어지고, N*N그리드에 숫자들이 주어진다. M개의 범위가 주어졌을때, 해당 범위에있는 숫자들의 합을 구하는문제다. 예를들어, 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 그리드에서, 1 1 1 4 는 10이다. 풀이 (구간합 구하기 3을 풀다 도망쳤다...) 일반적인 완전탐색으로는 풀지못한다. N의 범위가 1024이고, M이 10..
[백준 / BOJ] 6503 망가진 키보드 문제 출처 : www.acmicpc.net/problem/6503 6503번: 망가진 키보드 입력은 여러 개의 테스트 케이스로 이루어져 있고, 각 테스트 케이스는 두 줄로 이루어져 있다. 테스트 케이스의 첫째 줄에는 m이 주어진다. (1 ≤ m ≤ 128) 둘째 줄에는 상근이가 입력하려고 하는 www.acmicpc.net 상근이의 키보드가 망가져서, 키보드에서 작동가능한 키가 m개 밖에없다. 상근이가 입력하려는 문자가 주어졌을때, m개의 키를 눌러서 입력할수있는 최대 부분 문자열의 길이를 구하는 문제다. 풀이 예제 출력을보면 This can't be solved by brute force 라고 친절히 적혀있으므로 완전탐색으로는 풀리지않고, (문자열의 갯수가 완탐으로는 못풀만큼 입력되는듯) 다른 방법으로 ..

티스토리툴바