'Algorithm' 카테고리의 글 목록

2022. 7. 5. 23:23 Algorithm/BOJ

문제 링크 http://icpc.me/23245 23245번: Similarity In modern application systems, a recommendation system is very widely used to recommend books, music, ads, items, etc. The recommendation system needs to attract other users by providing the most interested items to each user. One way of recommendation is www.acmicpc.net 문제 출처는 2021 icpc 온라인 예선이다. 풀이 (pi < pj < pk)&& (qi < qj < qk) 인 (i, j, k)를 구하면 되..

[백준] 2679 맨체스터의 도로

2022. 6. 5. 02:04 Algorithm/BOJ

문제 링크 http://icpc.me/2679 2679번: 맨체스터의 도로 맨체스터에 있는 도로는 모두 일방 통행이다. 또한 이 도로는 모두 1시간에 지나갈 수 있는 차의 개수 제한이 있다. 길(경로)에도 차의 개수 제한이 있는데, 이것은 이 길에 있는 도로의 제한 중 www.acmicpc.net 풀이 네트워크 플로우를 기반으로 하고, 우선순위 큐를 이용한 풀이와 이분 탐색을 이용한 풀이가 있다. 차의 개수는 네트워크 플로우를 이용하면 쉽게 구할 수 있지만, 길 1개를 이용할 때의 최대 개수는 구하기 어렵다. 일반적인 네트워크 플로우처럼 경로를 고른다면, 경로를 고르는 순서에 따라 어떤 길에 한 번에 보낼 수 있는 최대를 보내지 않을 수 있다. 그렇기 때문에 다른 처리를 해줘야 한다. 우선순위 큐 풀이 ..

[백준] 8916 이진 검색 트리

2022. 5. 19. 21:56 Algorithm/BOJ

문제 링크 http://icpc.me/8916 8916번: 이진 검색 트리 각 테스트 케이스에 대해서, 입력으로 주어진 순열과 같은 트리를 만드는 순열의 개수를 9,999,991로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 3 2 5 4 1 6라는 예제가 있을 때 가장 앞에 나오는 3은 루트 노드로 순서가 바뀔 수 없다는 사실은 조금만 생각해본다면 알 수 있다. 그럼 2 5 4 1 6를 3의 왼쪽 트리와 3의 오른쪽 트리로 나눌 수 있다. 3보다 작은 2 1은 왼쪽 트리가 3보다 큰 5 4 6은 오른쪽 트리가 될 것이다. 그렇다면 재귀적으로 2 1과 5 4 6은 각각 트리가 되고, 첫 번째 수는 루트가 될 것이다. 여기서 조금 더 관찰해 본다면, 같은 모양의 트리가 나오기 위해서는 작은 ..

[백준] 3878 점 분리

2022. 4. 27. 22:29 Algorithm/BOJ

문제 링크 http://icpc.me/3878 3878번: 점 분리 평면 위에 여러 개의 검정 점과 흰 점이 있다. 이때, 길이가 무한대인 직선을 그어 흰 점과 검은 점을 분리하려고 한다. 직선은 어떤 점과도 만나면 안 된다. 직선으로 인해서 나누어지는 두 그룹 www.acmicpc.net 풀이 두 컨벡스 헐이 서로 만나지 않게 하면 된다. 검정 컨벡스헐을 구성하는 점을 A, 흰색 컨벡스 헐을 B라 하자. 두 컨벡스 헐이 만나지 않기 위해선 A의 점들 중 어떤 점도 B 내부에 있으면 안 된다. 또한 B의 점들도 A에 있으면 안 된다. 또한 두 컨벡스 헐을 이루는 모든 직선들끼리 서로 만나면 안 된다. 코드 #include using namespace std; using ll = long long; #de..

[백준] 1377 버블 소트

2022. 4. 12. 21:11 Algorithm/BOJ

문제 링크 http://icpc.me/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 풀이 개인적으로 알고 나면 쉽지만 아이디어가 많이 어려운 문제인 것 같다. 문제를 잘 관찰을 해본다면 출력을 하는 수는 정렬이 끝난 다음 시점의 i값이다. 편의상 인덱스가 작은 방향을 왼쪽, 큰 방향을 오른쪽이라 하겠다. 정렬이 모두 끝난 시점을 알기 위해서는 왼쪽으로 밀려난 수 중 가장 많이 밀려난 수가 몇 번 왼쪽으로 밀려났는지를 알면 된다. 그 이유는 왼쪽으로 가야 하는 어떤 수는 한번 ..

[백준] 2449 전구

2022. 4. 1. 02:21 Algorithm/BOJ

문제 링크 http://icpc.me/2449 2449번: 전구 입력의 첫 번째 줄에는 전구의 수를 나타내는 양의 정수 N과 전구가 표현할 수 있는 색의 수 K가 주어진다. 단, N은 1이상 200이하의 정수이며, K는 1이상 20이하의 정수이다. 두 번째 줄에는 N개 전 www.acmicpc.net 풀이 오랜만에 되게 재밌게 푼 dp문제다. 3차원 dp로 풀었는데 다른 사람 코드 구경하면서 2차원 dp로 내 풀이보다 훨씬 쉽게 풀 수 있는 걸 발견했다. 이 글에선 3차원 풀이를 작성하겠다. 시간 복잡도는 O(N^3 * K)에 해결할 수 있다. dp[l][r][i] : 구간 [l, r]을 i로 만들었을 때 최소 경우의 수 a[i] : a번째 전구의 색 위와 같이 정의를 하면 세 가지 케이스로 점화식을 세..

[백준] 7620 편집 거리

2022. 3. 24. 18:11 Algorithm/BOJ

문제 링크 http://icpc.me/7620 7620번: 편집 거리 가장 짧은 편집 스크립트를 출력한다. 한 명령을 한 줄에 하나씩 출력하며, 문제의 괄호에 나와있는 (a, d, m, c)중 하나를 출력하고, 그 명령을 수행하는데 사용한 글자를 출력한다. (출력할 글자 www.acmicpc.net 풀이 dp 역추적을 하는 문제다. 하지만 메모리를 특이하게 관리해야 하는 처음 보는 문제다. 역추적을 하기 위해서 dp테이블을 모두 가지고 있기엔 테이블의 크기가 17000 * 17000 * 4byte로 너무 크다. 그렇기 때문에 역추적을 위한 테이블을 17000 * 17000 * 2bit로 만들어 메모리를 최적화시켜야 한다. 역추적 테이블은 unsigned char 한 칸에 비트 연산을 이용하여 정보를 4개..

[백준] 1368 물대기

2022. 3. 16. 14:23 Algorithm/BOJ

문제 링크 http://icpc.me/1368 1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어 www.acmicpc.net 풀이 MST를 이용하여 풀 수 있다. 가상의 루트 노드를 하나 만들고, 어떤 물을 킬 때, 루트 노드에서 물을 끌어온다고 생각하면 쉽게 풀 수 있다. 물은 키는 행위는 루트 노드와 킬 노드를 연결시키는 것으로 매핑시키면 된다. 코드 #include using namespace std; struct T { int x, y, z; }; vector arr; int mat[302][302];..

[백준] 1126 같은 탑

2022. 2. 26. 16:39 Algorithm/BOJ

문제 링크 http://icpc.me/1126 1126번: 같은 탑 첫째 줄에 조각의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 각 조각의 높이가 주어진다. 높이는 500,000보다 작거나 같은 자연수이고, 모든 조각의 높이의 합은 500,000을 넘 www.acmicpc.net 풀이 dp문제다. dp인 것을 못 알아차리고 고민하다가 알고리즘 분류를 봤다. 처음 생각했던 점화식은 dp[i][a_size][b_size] : i번째 까지 봤을 때 a기둥의 사이즈와 b기둥의 사이즈로 dp를 정의하는 것이었다. 그러나 이 풀이는 52 * 5e5 * 5e5로 시간초과가 발생할 것이다. 그래서 a기둥과 b기둥의 높이를 더 컴팩트하게 정의할 수 있는 방법을 생각했다. 결론은 더 큰 기둥의..

[백준] 2662 기업투자

2022. 2. 23. 16:20 Algorithm/BOJ

문제 링크 http://icpc.me/2662 2662번: 기업투자 어떤 투자가가 여러 기업들에게 돈을 투자해서 최대의 이익을 얻고자 한다. 단, 투자는 만원 단위로 할 수 있으며 각 기업은 많이 투자할수록 많은 이익을 투자가에게 돌려준다. 돈을 투자하지 www.acmicpc.net 풀이 배낭 문제라고도 불리는 웰노운인 knapsack문제다. dp를 이용하여 풀 수 있다. dp[i][j] = max(dp[i - 1][j - k] + arr[k][i]) (0

[백준] 2481 해밍 경로

2022. 2. 17. 15:50 Algorithm/BOJ

문제 링크 http://icpc.me/2481 2481번: 해밍 경로 길이가 같은 두 개의 이진수 코드 w1과 w2가 있다고 하자. 이 두 코드 사이의 해밍 거리(Hamming distance)는 w1과 w2의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 www.acmicpc.net 풀이 해밍 거리가 1인 경우는 비트 하나만 다른 것을 의미하기 때문에 비트가 하나만 다른 것들을 모두 그래프로 만든 후에 bfs를 돌리면 된다. 비트 하나만 바꿀 때는 XOR연산을 하면 된다. 그래프를 만들 때는 N개의 수에 k번 비트 연산을 하고 그 수가 존재하는지 map으로 확인하면 O(NKlogN)에 만들 수 있다. cf) 입력을 int형으로 받아서 2시간 가까이 뇌절을 했다. 30자리..

[백준] 1533 길의 개수

2022. 2. 3. 15:26 Algorithm/BOJ

문제 링크 http://icpc.me/1533 1533번: 길의 개수 첫째 줄에 교차점의 개수 N이 주어진다. N은 10보다 작거나 같고, 시작점의 위치 S와 끝점의 위치 E, 그리고 정문이가 늦는 시간 T도 주어진다. S와 E는 N보다 작거나 같은 자연수이다. T는 1,000,000,000 www.acmicpc.net 풀이 본대 산책 2과 비슷한데 가중치가 있는 문제다. 가중치가 5 이하이기 때문에 정점을 늘려서 풀 수 있다. 정정 하나를 v0 v1 v2 v3 v4로 나누고 각 정점별 가중치를 1로 둔다. 이때 만약 u -> v의 가중치가 3이라면 u0 -> v2 -> v1 -> v0과 같은 방식으로 u -> v의 간선을 연결할 수 있다. 이렇게 그래프를 약간 변경하여 행렬제곱을 T제곱을 하면 O((5..

[백준] 12850 본대 산책 2

2022. 1. 27. 20:28 Algorithm/BOJ

문제 링크 http://icpc.me/12850 12850번: 본대 산책2 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 유배당한 불쌍한 정보대생을 위한 문제다.. 분할 정복을 이용한 O(logN) 행렬 제곱을 이용하여 풀었다. 이 글을 참고하여 풀었다. 행렬 곱셈식을 곱씹어본다면 왜 이렇게 풀이할 수 있는지 알 수 있다. Counting source to destination path of k length HERE author discusses three methods to count source to destination path of k length. I am not able to get the last method which is base..

[백준] 13977 이항 계수와 쿼리

2022. 1. 25. 22:00 Algorithm/BOJ

문제 링크 http://icpc.me/13977 13977번: 이항 계수와 쿼리 \(M\)개의 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 모듈러 역원에 대해 알아야 하는 문제다. 모듈러 역원에 대한 내용은 여기를 참고하자. n!을 전처리하여 미리 구해두고, 각 쿼리마다 n! * ((n-r)! * r!)^(mod-2)을 구하면 된다. 이때 제곱은 분할정복을 이용하여 계산한다. 코드 #include using namespace std; using ll = long long; const ll mod = 1e9 + 7; const int N = 4e6 + 6..

[백준] 9465 스티커

2022. 1. 25. 20:53 Algorithm/BOJ

문제 링크 http://icpc.me/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 dp문제다 dp[i][0] = max(dp[i-1][1], dp[i-2][1]) + arr[i][0] dp[i][1] = max(dp[i-1][0], dp[i-2][0]) + arr[i][1] 점화식은 위와 같다. 코드 #include using namespace std; const int N = 1e5 + 5; int arr[N][2], dp[N][2]; int main() { cin.tie(0)-..

티스토리툴바