알고리즘
-
BOJ) 가장 긴 바이토닉 부분 수열 (11054 번)알고리즘/백준 2021. 1. 7. 16:11
가장 긴 바이토닉 부분 수열 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 바이토닉 부분 수열은 요소들의 증감이 변곡점을 하나 이하로 가진 부분 수열이다. 즉, {1, 3, 5, 6, 4} 혹은 {1,2} 혹은 {7,3,5}와 같은 수열들이 바이토닉 수열이라 할 수 있다. 이 문제를 풀기 위해서는 LIS, LDS에 대한 개념이 있어야한다고 한다. LIS => Longest Increasing Subsequence (최장 증가 부분 수열) LDS => Longest Decreasing Subsequence (최장 감소 부분 수열)..
-
BOJ) 최솟값과 최댓값 (2357 번)알고리즘/백준 2021. 1. 5. 18:24
최솟값과 최댓값 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 앞서 포스팅한 세그먼트 트리를 활용하는 문제다. 위의 문제와 차이점이라면 구간 합을 구하는 대신, 최솟값과 최댓값을 저장한다는 점이다. 또한, 이 문제에서는 세그먼트 트리의 크기를 직접 구해서 초기화해줬다. 세그먼트 트리 초기화 private static class SegmentTree { int[] minTree, maxTree, numArr; private int size; public SegmentTre..
-
BOJ) 구간 합 구하기 (2042 번)알고리즘/백준 2021. 1. 5. 18:09
구간 합 구하기 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 세그먼트 트리를 이용해서 푸는 문제다. 우선, 이 문제를 풀기 위해서 세그먼트 트리에 대해서 공부해야했다. 백준 사이트에 블로그란에 기재되어있는 세그먼트 트리를 보고 풀었다. 세그먼트 트리란 무엇인가?? 먼저, 세그먼트 트리는 배열의 크기가 커질 경우, 연산 식에 유용하다. 공간 복잡도가 O(N^2)이고 시간 복잡도가 O(N^2)인 배열에 대한 연산이 있다면, 세그먼트 트리를 이용하여 O..
-
BOJ) 줄 세우기 (2252 번)알고리즘/백준 2021. 1. 2. 16:20
줄 세우기 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 오랜만에 포스팅을 하게 된 이유는 위상 정렬에 대한 정리를 하기 위해서이다. 위키에 따르면 위상 정렬(topological sorting)은 방향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 가장 대표적인 예로 대학의 선수과목(prerequisite) 구조를 들 수 있다. 만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 ..
-
BOJ) 평범한 배낭알고리즘/백준 2020. 8. 28. 16:49
평범한 배낭 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 짐의 개수 n, 버틸 수 있는 무게 k, n개 만큼의 짐의 정보 (무게 w, 가치 v)가 주어진다. 최대한 k에 맞추어, 최대 가치(max v)를 찾는 문제다. dp의 크기를 최대 가치 k까지 입력받을 수 있도록, k+1만큼 생성해준다. 짐의 정보를 순회하면서 w와 v를 가져온다. 그리고 k 부터 w까지 무게를 줄여나가면서, 현재 무게 ( i )의 dp값(가치) 과 dp[i-w] ..
-
BOJ) 숫자고르기알고리즘/백준 2020. 8. 28. 16:42
숫자고르기 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절� www.acmicpc.net 풀이 어제 풀었던 사이클 문제와 비슷한 것 같은데, 이 문제는 BFS로 풀었다. (사실 어제 푼 방법이 기억에 남지 않았다.) 1~N번까지 순회하면서 해당 인덱스가 가진 값을 타고 가는 검사를 통해, 시작한 인덱스 i번이 나오면 답에 추가를 해줬다. 위의 값을 가지고 있다면, 1번~ 7번까지 순회를 하면서 답을 찾는 것이다. 1번 index는 3이라는 값을 가지고 있다. 이 3이라는 값을 LinkedList에 넣고, 탐색을 한다. 3번 ..
-
BOJ) 한 줄로 서기알고리즘/백준 2020. 8. 28. 16:33
한 줄로 서기 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 � www.acmicpc.net 풀이 고민하는 시간에 비해 코드가 짧은 문제였다. 처음에는 우선순위 큐에 담아서, 적절한 sorting을 통해 출력하려고 했다. 하지만, 메모리 초과가 떴고 다시 고민했다. 주어진 정보들을 우선적으로 배열에 담고, 마지막부터(키가 제일 큰 사람부터) 자신의 왼쪽에 몇명이 있는지를 인덱스로 그 사람을 추가하면 된다는 것을 알았다. 문제의 예시를 통해 설명하면 더 쉽게 이해가 될 것 같다. 1 2 3 4 2 1 1 0 1~4의 값을 담은 배..
-
BOJ) 톱니바퀴알고리즘/백준 2020. 8. 28. 16:27
톱니바퀴 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 � www.acmicpc.net 풀이 생각보다 많이 까다로워서 푸는데 한시간정도 걸렸다. 가장 오래걸렸던 부분은 회전하기 전에 각 톱니바퀴들의 좌측과 우측의 극을 확인해야한다는 부분이다. 회전하면서 극을 새롭게 찾으면서 코드를 작성했어서, sholdTurn이라는 boolean 함수를 만들어 움직여야하는지 판별해줬다. 또한, 처음 입력받는 톱니바퀴의 상태는 가장 처음 인덱스가 문제의 설명처럼 좌측부터 있는 것이 아니라, 12시이 가장 맨 처음으로 주어진다는 것이 왜 이렇게 꼬아놓..