알고리즘/백준 (109) 썸네일형 리스트형 [BOJ 2812] 크게 만들기(Stack, Java) www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net ## 접근방법 이 문제는 스택을 이용해서 풀어야 한다. N이 500,000이므로 우선순위큐를 이용한 N * logN 시간복잡도가 걸린다면, 시간초과가 발생할 것이다. 따라서, 선형 탐색이 필요하다. K개를 지워서 가장 큰 수를 만드려면, 앞자리수가 커야 좋다. 값을 비교하고, 가장 큰 수를 만들수 있는 후보들을 저장하는 자료구조가 필요하다. 스택을 사용하면 입력된 순서대로 값의 비교가 가능하므로 자료구조로 스택을 사용할 것이다. 값을 비교할 때는, 스택의 peek 값과 현재 가르키는 값을.. [BOJ 1103] 게임(Java, DFS, DP, Cycle) www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net ## 접근 이 문제는 정답률에 비해서 어렵지 않은 문제이다. 보드의 크기만큼의 DP를 선언해주고, DP의 값을 갱신하면서 가장 큰 이동 횟수를 구해주면 된다. DP[nr][nc] = DP[r][c] + 1 nr, nc는 r, c에서 이동할 수 있는 신규 점을 의미한다. +1은 이동 횟수가 더해짐을 의미한다. 어떤 nr, nc를 접근할 때, 기존에 가진 값을 갱신하지 못하면 이동할 필요가 없다. 이 문제에서는 위.. [BOJ 11003] 최솟값 찾기(Deque) www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net ## 접근 특정 구간이라는 단어를 보면 세그먼트 트리를 습관적으로 이용하려고 했다. N * logN의 시간복잡도를 가지므로 나쁘지 않은 선택이지만 이 문제에서 시간 초과가 발생한다. 이 문제는 세그먼트 트리와 다르게 고정된 길이의 구간의 값들의 최솟값을 요구하고 있다. 세그먼트 트리보다 더 빠르게 최소값을 찾을 수 있지 않을까? 최소값을 바로 얻을 수 있는 자료구조가 필요하다. .. [BOJ 2357] 최솟값과 최댓값(Segment Tree, 세그먼트 트리, 자바) www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net ## 시간복잡도 문제에서, 특정 구간의 최솟값과 최댓값을 구해야 한다. 일반적으로 생각했을때, M개의 a와 b마다 정렬을 하고 최소값과 최대값을 구한다면 O(M * N * logN)의 시간복잡도가 발생한다. M과 N은 최대 10만이므로 무조건 시간초과가 발생한다. ## 세그먼트 트리 이 문제는 세그먼트 트리 개념을 모르면 풀 수 없다. 알고리즘에서 특정 구간들에 대한 계산된.. [BOJ 1701] Cubeditor (백준, JAVA, KMP) www.acmicpc.net/problem/1701 1701번: Cubeditor Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 www.acmicpc.net ## KMP 알고리즘 찾아야 하는 단어의 길이를 S, 전체 문서의 길이를 T라고 해보자. 모든 문서에서 단어를 비교하게 된다면 최악의 시간 복잡도는 O(T * S)가 된다. O(T * S)보다 시간을 줄일 수 있는 방법을 KMP 알고리즘이라고 한다. KMP 알고리즘의 핵심은, 검사된 문자의 정보를 이용하는 것이다. 찾아야 하는 단어의 문자의 substring(0, n)마다 .. [BOJ 11438] LCA 2(최소 공통 조상, 희소 행렬, 시간복잡도, JAVA) www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net ## 최소 공통 조상 최소 공통 조상이란, 트리에 각 노드에서 공통된 조상을 갖을 때 가장 가까이 있는 노드를 의미한다. 만약에, 트리의 높이가 H라고 했을 때, 순차적으로 탐색을 한다면 O(H)만큼 걸릴 것이다. 문제의 조건에서 발생할 수 있는 H는 최대 N과 같으므로, 시간복잡도가 O(N * N)이 되므로 제한 시간안에 정답을 찾을 수 없다. ## 희소 행렬 위에서 높이를 O(H)에 순차적으로 접근.. [BOJ 1655] 가운데를 말해요(Java, Time Complexity) www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net ## 시간복잡도 이 문제를, 단순히 정렬을 통해서 가운데를 찾는다고 생각하면, 시간복잡도는 N * N * logN이 된다. N의 범위는 100,000이므로 제한 시간안에 문제를 푸는 것이 불가능하다. 가운데를 알기 위해서는, 주어진 값들을 항상 관리하고 있어야 한다. 새로운 값을 logN만에 삽입할 수 있는 값이 필요하다. 이진 탐색을 통해서, 위치를 찾을 수도 있지만 우선순위큐를 통해서 문제를.. [BOJ 6591] 이항 숏다운 # 중간값이 왜 항상 정수인지 생각 # nCk = n-1Ck-1 + n-1Ck로 모든 문제를 풀려고 하지 말기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 import java.util.*; import java.lang.*; import java.io.*; class Main { static Scanner sc = new Scanner(System.in); static int n, k; static int[][] dp; static long answer = 1; public static void main (String[] args) throws .. 이전 1 2 3 4 ··· 14 다음
