본문 바로가기

전체 글

 (189)
개미( BOJ 2136 ) 문제 : https://www.acmicpc.net/problem/2136 2136번: 개미 길이가 L(2 ≤ L ≤ 1,000,000,000)인 막대기 위에 N(1 ≤ N ≤ 100,000)마리의 개미들이 서로 다른 위치에 살고 있다. 개미들은 크기가 매우 작기 때문에 이 문제에서는 개미가 크기가 없는 점이라고 생각 www.acmicpc.net 문제 파악하기 길이가 L인 막대기 위에 있는 N마리의 개미 중 가장 늦게 떨어지는 개미의 번호와 시간을 구하는 문제입니다. N마리의 개미는 왼쪽 또는 오른쪽 방향으로 움직이며 서로 만나면 반대 방향으로 이동합니다. 개미들이 부딪히는 모든 경우를 시뮬레이션하는 방법을 가장 먼저 떠올릴 수 있지만 개미가 많아질수록 구현도 어려워지고 시간 복잡도 역시 증가합니다. 그..
유클리드 게임( BOJ 4342 ) 문제 : https://www.acmicpc.net/problem/4342 4342번: 유클리드 게임 유클리드 게임은 두 명이서 하는 게임이고, 자연수 2개로 시작한다. 동혁이와 동규는 유클리드 게임을 하려고 한다. 동혁이가 먼저 시작한다. 동혁이는 큰 수를 작은 수의 배수만큼 뺀다. 이때, www.acmicpc.net 문제 파악하기 주어진 두 개의 자연수를 사용하여 유클리드 게임을 했을 때, 선공을 하는 사람(동혁)이 이기는지 후공을 하는 사람(동규)이 이기는지 확인하는 문제입니다. 두 사람은 항상 최적의 방법으로 게임을 한다는 설명을 통해 우리는 시작부터 승자와 패자가 결정되었다는 걸 확인할 수 있습니다. 그럼 두 개의 숫자를 가지고 누가 이기는지 어떻게 알 수 있을까요? 이는 유클리드 게임을 분석하..
옥토끼는 통신교육을 풀어라( BOJ 17838 ) 문제 : https://www.acmicpc.net/problem/17383 17383번: 옥토끼는 통신교육을 풀어라!! 옥토끼가 이런 식으로 문제를 풀면 tncks0121은 옥토끼가 5, 10, 15, 20, 25, 30, 34분에 문제를 풀었으므로 최대 5분동안 휴식을 한 것으로 간주한다. www.acmicpc.net 문제 파악하기 옥토끼가 N개의 문제를 푸는데 필요한 시간 간격의 최댓값이 가장 작아지는 경우를 구하는 문제입니다. 옥토끼는 한 번에 2개의 문제를 풀 수 있으며, 선택한 문제는 끝까지 해결한다고 합니다. 입력된 예시(3 4 5 9 10 14 15)를 보면서 문제를 자세히 이해해보겠습니다. 만약 가장 단순하게 입력된 순서대로 문제를 선택해서 해결한다면 아래와 같은 결과가 나오게 됩니다. ..
트라이(Trie) 트라이 구조는 문자열을 처리하는 알고리즘으로, 여러 문자열을 트리 구조를 활용하여 빠르게 처리하는 자료 구조이다. 맵을 사용한 구현 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 struct Node { map nxt; bool end; Node() { nxt.clear(); end = false; } void insert(char *val) { if(*val == '\0') end = true; else { if(!nxt[*val]) nxt[*val] = new Node(); nxt[*val]->insert(val+1); } } }; Colored by Color Scripter cs 포인터를 사용한 구현 기준 문제 : https://www.acmicpc.net/proble..
게리멘더링( BOJ 28433 ) 문제 : https://www.acmicpc.net/problem/28433 28433번: 게리맨더링 길이 $N$인 수열 $A_1, A_2, \cdots, A_N$이 주어집니다. 이 수열을 원하는 개수의 연속된 구간으로 나누어서, 각 구간의 합을 계산합니다. 합이 양수인 구간의 개수가 합이 음수인 구간의 개수를 초과 www.acmicpc.net 문제 파악하기 합이 양수인 구간을 음수인 구간보다 많이 만들 수 있는지 판단하는 문제입니다. 각 테스트케이스마다 최대 200,000개의 숫자가 주어지기 때문에 단순히 모든 경우를 확인하는 전탐색 알고리즘보다 효율적인 알고리즘이 필요합니다. 다행히 문제를 잘 살펴보면 나름 규칙성을 찾을 수 있습니다. 그럼 어떤 규칙을 찾을 수 있을까요? 문제 해결하기 문제를 관찰..
가우스 소거법 가우스 소거법은 연립 방정식의 해를 구하는 방법 중 하나로, O(N3) 알고리즘으로 쉽게 구현할 수 있다. 구현 기준 문제 : https://www.acmicpc.net/problem/22940 22940번: 선형 연립 방정식 하나 이상의 미지수에 대해 최고차항의 차수가 1을 넘지 않는 방정식을 선형 방정식이라 한다. 족, 다음과 같은 식을 의미한다. A1x1 + A2x2 + ... + Anxn = B 선형 연립 방정식이란 유한개의 선형 방 www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 4..
하늘에서 떨어지는 1, 2, ... , R-L+1개의 별( BOJ 17353 ) 문제 : https://www.acmicpc.net/problem/17353 17353번: 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 욱제의 은밀한 취미 중 하나는 매일 밤하늘을 감상하는 것이다. 😓 욱제는 하늘의 별들이 다음과 같은 규칙들을 따르며 떨어지는 걸 관찰했다. 별이 떨어지는 위치는 N개의 점이다. 점은 순 www.acmicpc.net 문제 파악하기 주어진 N개의 수열을 대상으로 [ L, R ] 구간에 1, 2, ... , R-L+1의 값을 더하는 쿼리와 X 위치의 값을 구하는 쿼리를 수행하는 문제입니다. 수열의 범위가 최대 100,000개이며 쿼리의 수가 최대 100,000개이기 때문에 효율적인 자료구조가 필요합니다. 또한, 수행할 쿼리 역시 모든 구간에 동일한 값을 더하는 작업..
느리게 갱신되는 세그먼트 트리 세그먼트 트리의 구간 갱신을 빠르게 처리하기 위한 방법으로, 별도의 배열을 사용하여 필요한 만큼만 부분적으로 세그먼트 트리의 값을 갱신하여 시간복잡도를 줄일 수 있습니다. 구현 기준 문제 : https://www.acmicpc.net/problem/2934 2934번: LRH 식물 상근이는 유전자 조작을 통해 줄기 두 개로 이루어진 식물을 만들었다. 이 식물은 줄기의 x좌표 L, R과 높이 H로 나타낼 수 있다. 아래 그림은 L=2, R=5, H=4인 식물이다. 상근이는 매일 매일 화단에 www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 3..

티스토리툴바