본문 바로가기

전체 글

 (201)
[BOJ 1725] 히스토그램(Java, 스택) www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net ## 접근 이 문제는 시간복잡도에 유의해서 풀어야 한다. 만약에, 각 시작점마다 최고 넓이를 구하게 된다면, 시간 복잡도는 N * N으로 시간 초과가 발생하게 된다. 이 문제를 스택을 이용하면 시간 복잡도 N만에 문제를 해결할 수 있다. 문제를 자세히 살펴보자. 어떤 특정 시작점에서 자신보다 낮은 높이의 직사각형을 만나게 되면, 히스토그램을 더 이상 그릴 수 없다. 어떤 특정 시작점..
[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만에 삽입할 수 있는 값이 필요하다. 이진 탐색을 통해서, 위치를 찾을 수도 있지만 우선순위큐를 통해서 문제를..
이진 탐색 트리에서 전체 방문하는 방법은?(Pre-Order, In-Order, Post-Order, Reverse In-Order) Q. 이진 탐색 트리에서 전체 방문하는 방법은? CS 지식을 묻는 시험에서 자주 나오는 문제이다, 재귀적인 구조를 이해한다면 쉽게 답을 유추할 수 있다. 각 Order의 주체가 되는 것은 루트 노드라는 것을 잊지 않으면 된다. Pre-Order은 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순으로 방문한다. In-Order은 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리 순으로 방문한다. Post-Order은 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트 순으로 방문한다. 각 노드의 방문 순서를 출력할 수 있는데, 루트 노드의 위치에 printf를 호출해주면 된다. Q. 부모 노드를 출력하는 것이 모든 노드의 순서를 볼 수 있을까? 어떤 노드든 루트 노드가 될 수 있다. (물론 모든 트리에서 루트 노드..
정렬별 시간복잡도를 생각해보자(Bubble Sort, Selection Sort, Insertion Sort, Quick Sort, Merge Sort, Heap Sort, Time Complexity) Q. 정렬의 종류는 무엇이 있을까? 종류들을 나열하고, 간단하게 알고리즘에 대해서 설명하겠다. 오름 차순 정렬 기준으로 설명하겠다. 버블정렬 : 순차적으로 근접한 두 값을 비교하면서, 마지막에 거품(Bubble)처럼 하나의 값을 얻게 된다. 같은 과정으로 하나의 값들을 얻어보면 정렬할 수 있다. 선택정렬 : 선택정렬은 전체의 원소에서 가장 작은 값을 순차적으로 찾아가면서 정렬한다. 삽입정렬 : K번째 원소의 위치를 찾을 때, 1부터 K-1까지는 모두 정렬이 되어 있으므로, K -1번째부터 값을 비교하며 위치를 찾으면서 정렬한다. 퀵정렬 : 피벗을 선택하고, 피벗을 기준으로 왼쪽에는 피벗보다 작은 값이 오른쪽에는 피벗보다 큰 값이 오도록 한다. 재귀적으로 호출하며 모든 원소들을 정렬한다. 합병정렬 : 재귀..
CPU 스케줄링(gantt chart) CPU 스케줄링을 gantt chart로 계산해보자. Q. FCFS인 경우 평균 시간을 어떻게 될까? FCFS의 경우, 순차적으로 프로세스가 실행되므로 평균 시간은 각 프로세스의 시작 시간과 같다. 간단히 직관적으로 이해될 것이다. Q. 라운도 로빈(RR)의 경우 평균 시간은 어떻게 될까? 위의 그림을 이해해보자, P2는 4초에 시작하고 7초에 모두 마무리된다. P3도 7초에 시작해서 10초에 마무리된다. 하지만 P1은 0 ~ 4초까지 실행이 되고, 10초에 다시 시작되므로 대기시간이 (10 - 4)가 존재한다. 따라서 (P1의 대기시간 + P2의 대기시간 + P3의 대기 시간) / 3을 한 값이 평균 대기 시간이 된다. 다양한 CPU 프로세스 알고리즘이 존재한다. 어떤 방식이든 평균 대기 시간이라는 것..

티스토리툴바