복습 정리 노트

2차원 배열에서 특정 직사각형 구간을 잡아 얻을 수 있는 구간의 최대 합을 가장 빠른 시간에 구할 수 있는 알고리즘은 무엇일까요? 특정한 점화식을 사용하는 세그먼트 트리를 이용하면 2차원 공간에서의 최대 구간합을 O(N^2 log N)에 구할 수 있다는 것이 잘 알려져 있으며, 이 알고리즘을 사용하는 문제가 정보 올림피아드에 '금광'이라는 이름의 문제로 출제되어 많은 사람들이 이를 금광 세그라고 부릅니다. 이 포스트에서는 금광 세그에 대해 공부한 것을 간단하게 설명해보고, 이를 구현해볼 것입니다. 백준 BOJ 10167번 : 금광 N개의 점이 주어지고, 각 점에 대해 x, y 좌표와 가중치 w가 주어질 때, 특정 직사각형 형태의 구간을 잡아 얻을 수 있는 최대 구간 합을 구하는 문제입니다. 풀이 코드가 ..

이 포스트에서는 시스템 프로그래밍(system programming)의 실습 과제 중 하나인 Attack Lab(어택 랩)의 풀이를 다룬다. Attack Lab은 버퍼 오버플로우를 활용하여 문제의 의도대로 프로그램을 조작하여 원하는 데이터를 얻는 등의 처리를 하는 과제이다. 프로그램은 ctarget과 rtarget의 2개가 존재하며, ctarget은 touch1, touch2, touch3의 3개의 함수가 존재하고 rtarget은 touch2, touch3의 2개의 함수가 존재한다. (편의상 이들을 Phase 1 ~ 5로 칭하기도 한다.) ctarget은 code injection attack을 이용하여 attack하고 rtarget은 return-oriented programming을 이용하여 atta..

이 포스트는 시스템 프로그래밍(System programming)에서 다루는 과제인 bomb lab(밤랩)의 풀이를 다루고 있다. 대표적인 원서인 컴퓨터 시스템(Computer Systems)에서도 다루고 있으며, 카네기멜론 대학(CMU)에서 만들어진 과제이다. 만약 이 글을 검색을 통해 들어왔다면 과제를 도움받기 위해 들어왔을 것이지만, 혹여나 자발적으로 풀어보고 싶은 사람이 있다면 아래의 링크에서 다운해볼 수 있다. http://csapp.cs.cmu.edu/3e/labs.html 그 중에서도 Bomb Lab(밤랩)은 어셈블리 코드 내에 있는 폭탄에 해당하는 코드를 찾아서 해체시키는 컨셉의 과제이다. 쉽게 말해서 어셈블리 코드를 해석하는 것을 연습해볼 수 있는 과제이다. 그럼 바로 풀이와 해설을 정리..

알고리즘에 대한 글을 작성하면 일반적으로 하나의 주제를 잡고 정리해야 하는데, 글 하나에 정리할 정도로 내용이 많지 않은 작은 테크닉이나 단일 문제들의 경우 포스트 하나마다 따로 작성하기가 용이하지 않기 때문에, 이 카테고리에 큰 형식의 틀 없이 모아서 작성해보려고 한다. 백준 BOJ 10986번 : 나머지 합 N개의 수로 이루어진 수열에 대해 연속된 구간의 합이 M으로 나누어 떨어지는 구간의 수를 구하는 문제이다. (1 ≤ N ≤ 10^6) 가장 먼저 떠오르는 풀이는 누적 합을 이용해서 O(N^2)에 푸는 건데, 그렇게 할 경우 당연히 시간 초과이다. i ~ j번째 구간의 합이 M으로 나눈 나머지가 0이라는 것과 동치는 무엇일까? 누적 합을 이용하여 생각해보면, 1 ~ j번째 구간 합에서 1 ~ (i-..

vector, string 내에서 인접한 값끼리 비교할 때 for(int i=1; i

백준 BOJ 14958번 : Rock Paper Scissors 문제 난이도 : Diamond V 알고리즘 분류 : FFT (고속 푸리에 변환) 배열이 2개가 주어지고, 각각의 배열의 값들이 가위바위보에 해당하는 Rock, Paper, Scissors라고 할 때, 아래의 배열이 이동하면서 매칭되는 칸끼리 가위바위보를 수행하여 위치에 따라 가장 많이 이길 수 있는 횟수를 구하는 문제입니다. 이 문제의 상황과 같이 배열과 배열을 일대일로 비교를 여러 번 해야하는 경우 FFT를 활용해볼 수 있습니다. 한 쪽의 벡터를 뒤집은 뒤 이산 합성곱을 수행해주면 항마다 일대일로 매칭되어 곱해진 값이 더해지므로, 이를 활용하기 위해 적절히 벡터의 값을 1 또는 0으로 세팅해주어야 합니다. 문제 상황에 대해 생각해보면 N칸..

백준 BOJ 13055번 : K-Inversions 문제 난이도 : Diamond V 알고리즘 분류 : FFT (고속 푸리에 변환) B가 A보다 먼저 나오는 쌍을 inversion이라고 할 때, B와 A 사이의 거리가 K일 때 그 쌍을 K-Inversion이라고 정의합시다. A와 B로만 이루어진 문자열에 대해 0 ~ N-1사이의 모든 K-inversion의 수를 구하는 문제입니다. 예를 들어 문제에서 예시로 든 BABA를 가지고 설명하자면, 앞의 BA와 뒤의 BA는 모두 B → A 순서대로 나타나며 B와 A 사이의 거리가 1이므로 1-inversion이고, 이는 총 2회 나옵니다. 그리고 맨 앞의 B와 맨 뒤의 A 역시 inversion에 해당되고, 두 문자 사이의 거리는 3이므로 3-inversion은..

백준 BOJ 13575번 : 보석 가게 문제 난이도 : Platinum I 알고리즘 분류 : FFT (고속 푸리에 변환), 분할 정복을 이용한 거듭 제곱 N개의 값 중에서 K개를 중복을 허용하여 선택할 때, 얻어질 수 있는 합의 가짓수를 구하는 문제입니다. 예를 들어 N = 3, 주어진 배열 A = { 1, 2, 3 }, K = 2라고 할 때 1 + 1 = 2, 1 + 2 = 3, 1 + 3 = 2 + 2 = 4, 2 + 3 = 5로 총 4가지 합을 얻을 수 있어서 답은 4가 됩니다. (문제 조건에 따라 다른 조합으로 같은 합을 얻더라도 하나의 합으로 카운트 해주어야 합니다.) FFT를 이용하면 두 집합의 합으로 얻어질 수 있는 값들의 종류와 그 가짓수를 구할 수 있으므로, FFT를 활용하여 풀이하는 방..

백준 BOJ 13279번 : 곱의 합 쿼리 문제 난이도 : Platinum IV (FFT로 해결할 시 체감 난이도 Platinum I, 그러나 O(N^2) 풀이가 통과되어 하향 조정) 알고리즘 분류 : FFT (고속 푸리에 변환) N개의 수로 이루어진 수열 A에서, 쿼리 K가 주어지면 A의 길이 K인 부분 수열들의 곱의 합을 구하여 출력하는 문제입니다. 이 때 쿼리 문제이므로 쿼리의 수는 최대 N개가 주어질 수 있습니다. 예를 들어 N = 3이고 A = { 1, 2, 3 }이라면, K = 2가 주어졌을 때 길이가 2인 부분 수열은 { 1, 2 }, { 1, 3 }, { 2, 3 }이 있으므로 이들의 곱의 합을 구하면 11이 됩니다. 문제 조건을 보면 쿼리는 최대 N개 들어올 수 있고 이는 결국 1 ~ N..

백준 BOJ 20176번 : Needle 문제 난이도 : Platinum I 알고리즘 분류 : FFT (고속 푸리에 변환) 3개의 직선이 있고 3개의 직선 위에 점들의 좌표가 주어질 때 서로 다른 직선 위의 3개의 점이 일직선에 있는 쌍이 몇 개나 있는지를 구하는 문제입니다. 입력은 3개의 직선에 대해 직선 위의 점의 수 N, 점의 x 좌표 N개가 순서대로 주어집니다. 2 1 2 3 0 1 2 2 2 3 예를 들어 입력이 위와 같이 주어졌다고 가정하면, 맨 위에서 좌표 1, 중간에서 좌표 2, 맨 아래에서 좌표 3을 선택하면 하나의 직선을 만들 수 있습니다. 또한 맨 위에서 좌표 2, 중간에서 좌표 2, 맨 아래에서 좌표 2를 선택해도 역시 직선 하나를 만들 수 있습니다. 따라서 위의 입력에 대한 답은 ..