본문 바로가기

전체 글

 (21)
2023 ICPC Sinchon Winter Algorithm Camp Contest 후기 이번 겨울 방학에 2023 ICPC Sinchon Winter Algorithm Camp Contest에 참가하여 1등(금상)을 했다. 방학 동안 열심히 공부하기도 했고 이제 초급 알고리즘은 많이 익숙해졌다고 생각해서 높은 등수가 나올 것이라고 예상은 했지만 1등까지 할 줄은 못했다. 물론 그날 컨디션도 좋았고 운도 많이 따라주었다고 생각한다. 문제 : https://www.acmicpc.net/category/801 해설 : https://www.acmicpc.net/board/view/111865 대회는 12시부터 5시였다. 평소 같으면 대회 시작하기 전까지 푹 자고 일어나서 밥을 먹고 대회를 했을 것 같지만 이 날 아침 9시에 선릉역 근처에서 삼성 SDS Pro SW 검정 시험이 있었어서 일찍 일어..
2023년 코포 정리 ● Codeforces Round #799 (Div. 4) - 2023.01.02 - 5 solve ● Codeforces Round #838 (Div. 2) - 2023.01.05 - 2 solve ● Educational Codeforces Round 90 (Rated for Div. 2) - 2023.01.06 - 1 solve ● Educational Codeforces Round 141 (Rated for Div. 2) - 2023.01.08 - 2 solve ● Codeforces Round #787 (Div. 3) - 2023.01.12 - 4 solve ● Codeforces Round #849 (Div. 4) - 2023.02.03 - 6 solve ● Codeforces Round #8..
[백준 9345] 디지털 비디오 디스크(DVDs) 1. 문제 https://www.acmicpc.net/problem/9345 9345번: 디지털 비디오 디스크(DVDs) 손님이 DVD를 카운터에 가져왔을 때 손님이 원하는 DVD가 전부 존재하면, (A번 선반부터 B번 선반까지에 있는 DVD를 전부 가져왔을 때 순서에 상관없이 A번 DVD부터 B번 DVD까지 있다면) "YES"를 출력하 www.acmicpc.net 2. 풀이 세그먼트 트리를 이용한 문제이다. 물론 나는 인덱스 트리로 풀었다. 인덱스 트리에 대해 잘 모른다면 먼저 공부하고 오자! 인덱스 트리 : https://kinngife.tistory.com/32 인덱스 트리 (Binary Indexed Tree) 1. 정의 인덱스 트리는 원소들의 구간 합을 빠르게 구하기 위해 사용하는 자료구조로 펜..
[백준 2243] 사탕상자 1. 문제 https://www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이 www.acmicpc.net 2. 풀이 세그먼트 트리를 이용한 문제이다. 물론 나는 인덱스 트리로 풀었다. 인덱스 트리에 대해 잘 모른다면 먼저 공부하고 오자! 인덱스 트리 : https://kinngife.tistory.com/32 인덱스 트리 (Binary Indexed Tree) 1. 정의 인덱스 트리는 원소들의 구간 합을 빠르게 구하기 위해 사용하는 자료구조로 펜윅 트리라고도 한다..
확장 유클리드 호제법 (Extended Euclidean Algorithm) 1. 정의 확장 유클리드 호제법은 두 정수 $a, b$에 대해 $GCD(a, b) = d$라고 했을 때, $ax + by = d$를 만족하는 $x, y$를 찾을 때 이용되는 알고리즘이다. 확장 유클리드 호제법에 대해 공부하기 전에 유클리드 호제법과 베주 항등식이 무엇인지 먼저 알아보자. 1) 유클리드 호제법 두 정수 $a, b$에 대하여 최대공약수 $GCD(a, b)$를 빠르게 찾는 알고리즘이다. $a$를 $b$로 나눈 나머지를 $r$이라고 할 때, $GCD(a, b) = GCD(b, r)$이 성립하는데 유클리드 호제법은 이 성질을 이용한다. 아래와 같이 한 숫자에서 다른 숫자를 계속 나누어서 나머지가 0이 될 때까지 위 성질을 이용하면 몇 번의 연산만으로 $GCD(a, b)$를 구할 수 있다. $a$를..
[백준 2517] 달리기 1. 문제 https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 www.acmicpc.net 2. 풀이 세그먼트 트리를 이용한 문제이다. 물론 나는 인덱스 트리로 풀었다. 인덱스 트리에 대해 잘 모른다면 먼저 공부하고 오자! 인덱스 트리 : https://kinngife.tistory.com/32 인덱스 트리 (Binary Indexed Tree) 1. 정의 인덱스 트리는 원소들의 구간 합을 빠르게 구하기 위해 사용하는 자료구조로 펜윅 트리라고도 한다. 세그먼트 트리와 같..
[백준 2042] 구간 합 구하기 1. 문제 https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 2. 풀이 기본적인 세그먼트 트리 문제이다. 나는 세그먼트 트리보다 인덱스 트리를 선호하므로 인덱스 트리로 설명하겠다. 인덱스 트리에 대해 잘 모른다면 먼저 공부하고 오자! 인덱스 트리 : https://kinngife.tistory.com/32 인덱스 트리 (Binary Indexed Tree) 1. 정의 인덱스 트리는 원소들..
인덱스 트리 (Binary Indexed Tree) 1. 정의 인덱스 트리는 원소들의 구간 합을 빠르게 구하기 위해 사용하는 자료구조로 펜윅 트리라고도 한다. 세그먼트 트리와 같이 기능을 하지만 구현이 좀 더 쉽고 직관적이며 많은 문제에 활용할 수 있다. 인덱스 트리는 원소를 업데이트(Point update)하거나 구간 합(Range query)을 구하는 데 걸리는 시간은 $O(logN)$이다. 2. 구현 1) 배열 크기 설정 인덱스 트리는 포화 이진트리로 먼저 배열의 크기를 구해야 한다. 단순히 배열에 원소만 들어가는 것이 아니라 원소들의 구간합 정보가 배열에 포함되어야 한다. 인덱스 트리의 리프 노드에 원소가 저장이 되어야 하고, 리프 노드부터 루트 노드까지 각각의 부모 노드는 자식 노드들의 합이 저장되어야 한다면 구현에 필요한 노드의 개수 즉, 인덱..

티스토리툴바