본문 바로가기

분류 전체보기78

[BOJ 12015] 가장 긴 증가하는 부분 수열 2 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 해당 문제 [BOJ 11053] 가장 긴 증가하는 부분 수열 문제와 거의 똑같다. 다만 배열의 크기가 1,000,000이기 때문에 위에서 쓴 O(N^2) 알고리즘으로는 못 푼다. 대신 O(N log N) 알고리즘을 이용하여 풀면 된다. 자세한 풀이는 LIS 에 있다. #include #include #include using namespace std; int n; int main() { scanf.. 2020. 4. 7.
가장 긴 증가하는 부분 수열, LIS(Longest Increasing Subsequence) LIS는 어떠한 수열에서 증가하는 부분 수열중 길이가 가장 긴 수열를 뜻합니다. LIS를 찾는 알고리즘은 다이나믹 프로그래밍을 이용한 O(N^2) 알고리즘과 이보다는 좀 더 복잡한 O(N log N) 알고리즘이 있습니다. 부분 수열이란 어떠한 수열에서 일부 숫자를 지워서 만들 수 있는 새로운 수열을 의미합니다. O(N^2) O(N^2) 알고리즘은 비교적 간단하게 구현할 수 있습니다. dp[i] = i 번째 원소를 마지막으로 하는 LIS의 길이 dp[i]를 구하는 법은 1 ~ (i - 1)까지의 원소들 중 i번째 원소보다 값이 작은 것들 중 dp의 값이 가장 큰 것에 1을 더하면 된다. 즉, j = 1 ~ (i - 1)을 순회할 때, a[i]보다 a[j]가 작다면, dp[i] = max(dp[i], dp[.. 2020. 4. 7.
[BOJ 11053] 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net 가장 긴 증가하는 부분 수열의 길이를 구하는 문제이다. 굳이 연속적인 배열이 아니여도 상관없다. 주어진 수열을 순회하면서, 각 순회마다 현재위치에서 첫번째 위치까지 돌면서 각 위치의 값보다 현재 위치의 값이 크면 현재 위치까지의 가장 긴 증가수열은 각 위치의 길이 + 1이다. 이를 통해서 구하면 된다.. 2020. 4. 7.
[BOJ 9465] 스티커 https://www.acmicpc.net/problem/9465 9465번: 스티커 문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점 www.acmicpc.net DP로 풀 수 있는 비교적 간단한 문제이다. 첫 번째 행의 스티커를 고르면 다음 열에서는 두 번째 행의 스티커를 골라야 하고 두 번째 행의.. 2020. 4. 7.
[BOJ 2606] 바이러스 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다. www.acmicpc.net 위 문제는 간단하게 BFS로 풀 수 있다. 1번 컴퓨터에서 갈 수 있는 모든 컴퓨터를 구하면, 몇 개의 컴퓨터가 바이러스에 걸리는지 알 수 있다. 이를 위해서 큐에 1번을 넣음 큐에서 값을 하나 꺼냄 꺼낸 값과 연결된 모든 값 중 방문하지 않은 곳을 큐에 넣음 큐에 넣을 때마다 바이러스가 걸린 컴.. 2020. 4. 7.
Lower Bound & Upper Bound Lower Bound & Upper Bound은 이분 탐색에서 파생된 알고리즘으로 Lower Bound는 "찾는 값 T 이상이 처음 나오는 위치를 찾는" 알고리즘이고, Upper Bound는 "찾는 값 T 초과한 값이 처음 나오는 위치를 찾는" 알고리즘이고, Lower Bound 알고리즘 자체는 이분 탐색과 매우 유사하다. 중간 값이 작으면 시작 위치를 중간 다음 위치로, 크거나 같으면 끝 위치를 중간 위치로 이동시킨다. 이분 탐색과는 다르게 끝 위치를 중간 이전 위치가 아닌 중간 위치로 움직인다. 간단하게 생각해보면 값이 작다는 건 중간 위치까지는 원하는 값 이상이 절대 없기에 다음 위치로 이동시키지만, 크거나 같다면 중간 위치의 값이 찾는 값 이상인 처음 위치일 수도 있기에 중간 위치로 설정한다. #.. 2020. 4. 3.
이분 탐색(Binary Search) 이분 탐색(Binary Search)이란 특정 값을 비교적 빠르게 찾는 알고리즘입니다. 선형 탐색의 경우 N개 값 중에 T라는 값을 찾는다면 최악의 경우 O(N)의 시간 복잡도를 가집니다. 하지만 이분 탐색은 최악의 경우 O(logN)의 시간 복잡도를 가집니다. 이분 탐색은 1가지 조건이 필요합니다. 입력받은 값들이 정렬되어 있어야합니다. 이분 탐색은 특정 값을 찾을 때 탐색 범위를 절반씩 나눠가며 값을 찾는데, 이때 절반으로 나누는 기준이 값의 크기입니다. 크기에 따라 나누어진 절반의 오른쪽 범위인지, 왼쪽 범위인지를 구별합니다. 이분 탐색의 기본 로직은 처음에 Left, Right 값을 인덱스의 시작, 끝으로 초기화한다. Left, Right의 중간 위치의 값이 찾는 값 T보다 크면 Left를 중간 .. 2020. 4. 3.
[BOJ 17144] 미세먼지 안녕! https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼 www.acmicpc.net 위 문제는 1초마다 미세먼지가 상하좌우로 확산되고, 공기청정기에서 바람이 나와서 미세먼지를 청소한다. T초가 지났을 때의 미세.. 2020. 3. 25.
[BOJ 15685] 드래곤 커브 https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10) 입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다. 방향은 0, 1, 2, www.acmicpc.net [0, 100] 내에서 사각형의 4개의 점이 드래곤 커브의 일부인 사각형의 개수를 찾는 문제이다. 드래곤 커브를 모두 그린 다음에 .. 2020. 3. 25.

티스토리툴바