backjoon
1.[백준] 11720번 - 숫자의 합 구하기
해당문제는 Python의 리스트 자료구조를 통해 쉽게 해결할 수 있다.주어진 숫자를 리스트의 형태로 저장한 뒤 해당 리스트를 index를 이용해 탐색하면서 각 자릿수의 값을 더하면 된다.이때, 자릿수를 더할 때는 정수형으로 변환하여 더한다.
2.[백준] 1546번 - 평균 구하기
최고 점수를 기준으로 전체 점수를 다시 계산해야 하므로 모든 점수를 입력받은 후에 최고점을 별도로 저장해야한다.또한 문제에세 제시한 한 과목의 점수를 계산하는 식은 총합과 관련된 식으로 변환할 수 있다.따라서 일일이 변환 점수를 구할 필요 없이 한 번에 변환한 점수의
3.[백준] 11659번 - 구간 합 구하기 4
문제에서 수의 개수와, 합을 구해야 하는 횟수는 최대 100,000이다. 게다가 구간마다 합을 매번 계산하면 0.5초 안에 모든 구간 합 계산을 끝낼 수 없다. 따라서 구간합을 이용하여 문제를 풀도록 한다.배열 A의 합 배열을 S라고 할때, S\[i] = A\[0] +
4.[백준] 11660번 - 구간 합 구하기 5
먼저 질의의 개수가 100,000이므로 이 문제는 질의마다 합을 구하면 안 되고, 구간 합 배열을 이용해야 한다는 것을 알 수 있다.구간 합 배열이 1차원에서 2차원으로 확장된 것으로 생각하여 구간 합 배열을 어떻게 구성하지 고민하는 것이 이 문제의 핵심이다.2차원 구
5.[백준] 10986번 - 나머지 합
N의 최댓값이 106개로 모든 구간 합을 구해야 하므로 1초 안에 연산하기는 어렵다. 따라서 구간 합 배열을 이용하여 해결한다.나머지 합 문제 풀이의 핵심 아이디어(A + B) % C는 ((A % C) + (B % C)) % C와 같다. 다시 말해 특정 구간 수들의 나
6.[백준] 2018번 - 수들의 합 5
이 문제는 시간 복잡도 분석으로 사용할 알고리즘의 범위부터 줄여야 한다. 우선 문제에 주어진 시간 제한은 2초이다. 그런데 n의 최댓값은 10,000,000으로 매우 크게 잡혀 있다. 이런 상황에서는 O(nlogn)의 시간 복잡도 알고리즘을 사용하면 제한 시간을 초과하
7.[백준] 1940번 - 주몽
N의 최대 범위가 15,000이므로 O(nlogn) 시간 복잡도 알고리즘을 사용해도 된다. 일반적으로 정렬 알고리즘의 시간 복잡도는 O(nlogn)이므로, 정렬을 사용해도 된다. 따라서 입력받은 N개의 재룟값을 정렬한 다음 양쪽 끝의 위치를 투 포인터로 지정해 문제에
8.[백준] 1253번 - 좋은 수 구하기
시간 복잡도를 생각해보면, N의 개수가 최대 2000이라 가정해도 좋은 수 하나를 찾는 알고리즘의 시간 복잡도는 N^2보다 작아야 한다.만약 좋은 수 하나를 찾는데 시간 복잡도가 N^2인 알고리즘을 사용하면 최종 시간 복잡도는 N^3이 되어 제한 시간안에 문제를 풀 수
9.[백준] 12891번 - DNA 비밀번호
P와 S의 길이가 1,000,000으로 매우 크기 때문에 O(n)의 시간 복잡도 알고리즘으로 문제를 해결해야 한다. 이때 부분 문자열의 길이가 P이므로 슬라이딩 윈도우의 개념을 이용하여 문제를 쉽게 해결할 수 있다.이 문제를 풀면서 고려해준 사항은 다음과 같다.먼저 처
10.[백준] 11003번 - 최솟값 찾기
일정 범위 안에서 최솟값을 구하는 문제이므로 슬라이딩 윈도우와 정렬을 사용하면 된다.윈도우의 크기는 문제에서 최솟값을 구하는 범위가 i-L+1부터 i까지 이므로 L로 생각하면 된다.최솟값을 찾기 위한 정렬의 경우 일반적인 정렬에서는 O(nlogn)의 시간 복잡도를 가지
11.[백준] 1874번 - 스택 수열
스택의 원리를 정확하게 알고 있는지를 묻는 문제이다. 이 문제는 스택의 pop, push연산과 후입선출 개념을 이해하고 있다면 쉽게 풀 수 있다. 스택에 넣는 값은 오름차순 정렬이어야 한다는 것에 유념하며 문제를 풀면 된다.문제를 푸는 과정의 아이디어는 다음과 같다 스
12.[백준] 17298번 - 오큰수
N의 최대 크키가 1,000,000이므로 반복문으로 오큰수를 찾으면 제한 시간을 초과한다. 따라서 스택에 다음과 같은 아이디어를 추가해 이 문제를 풀어보면 된다.입력으로 주어진 수열과 스택의 top을 비교하는 과정을 진행한다.입력으로 주어진 수열이 스택의 top보다 크
13.[백준] 2164번 카드2
큐를 잘 이해하고 있는지를 묻는 문제로, 가장 위의 카드를 가장 아래에 있는 카드 밑으로 옮기는 동작은 큐의 선입선출 성질을 이용하면 쉽게 구현할 수 있다.
14.[백준] 11286번 - 절댓값 힙
N의 최대범위가 100,000으로 O(nlogn) 시간 복잡도를 가진 알고리즘으로 풀 수 있다. (1초 == 약 2000만번).데이터가 새로 삽입될 때마다 절댓값과 관련된 정렬이 필요하므로 우선순위 큐로 문제를 해결할 수 있다.단, 이 문제는 절댓값 정렬이 필요하므로
15.[백준] 2750번 - 수 정렬하기
파이썬에서는 sort()함수를 이용해 쉽게 정렬할 수 있지만, 이번에는 정렬을 직접 구현해 문제를 해결해 보겠다.N의 최대 범위가 1,000으로 매우 작기 때문에 O(n^2) 시간 복잡도 알고리즘으로 풀 수 있다. 버블 정렬의 시간 복잡도가 O(n^2)이므로 버블 정렬
16.[백준] 1377번 - 버블 소트
버블 정렬의 swap이 한 번도 일어나지 않은 루프가 언제인지 알아내는 문제이다.'버블 정렬의 이중 for 문에서 안쪽 for문 전체를 돌 때 swap이 일어나지 않았다는 것은 이미 모든 데이터가 정렬됐다는 것을 의미한다.해당 문제는 N의 최대 범위가 500,000이므
17.[백준] 1427번 - 소트인사이드
자연수를 받아 자릿수별로 정렬하는 문제이므로 먼저 숫자를 각 자릿수별로 나누는 작업이 필요하다.파이썬에서는 input 데이터를 list로 변환하면 자동으로 각 자릿수로 나누어 리스트화해주기 때문에 변경이 매우 간편하다.따라서 list변환을 사용하고 N의 크키가 1,00
18.[백준] 11399번 - ATM
문제에서 예시로 든 상황에서 알 수 있듯이 모든 사람이 돈을 인출하는데에 최소한의 시간이 들기 위해서는 시간이 적게 드는 사람이 먼저 돈을 인출해 가는 방식으로 풀어야 한다는 것을 알 수 있고, 따라서 시간이 적게 드는 사람이 앞에 있도록 오름차순으로 정렬하면 된다.
19.[백준] 11004번 - K번째 수
주어진 값대로 배열을 정렬하고 입력으로 받은 K값에 따라 출력해주면 된다.N의 최댓값이 5,000,000이므로 O(nlogn)의 시간복잡도를 가지는 정렬을 수행해야 한다.따라서 sort()함수, 병합정렬 등을 이용하여 해결하면 된다.
20.[백준] 2751번 - 수 정렬하기2
N의 최대 범위가 1,000,000이므로 O(nlogn)의 시간 복잡도로 정렬을 수행하면 된다.따라서 sort()함수를 이용하여 수행하면 다음과 같다.
21.[백준] 1517번 - 버블 소트
N의 최대 범위가 1,000,000이므로 O(nlogn)의 시간 복잡도로 정렬을 수행하면 된다.따라서 해당 문제는 병합정렬을 사용하여 해결하면 다음과 같다.
22.[백준] 10989번 - 수 정렬하기 3
이 문제는 N의 최대 개수가 10,000,000으로 매우 크기 때문에 O(nlogn)보다 더 빠른 알고리즘이 필요하다.문제에서 주어지는 숫자의 크기가 10,000보다 작다는 것을 바탕으로 기수정렬과 함께 많이 사용되는 계수 정렬(counting sort)을 사용하여 문
23.[백준] 11724 - 연결 요소의 개수
노드의 최대 개수가 1,000이므로 시간 복잡도 N^2이하의 알고리즘을 모두 사용할 수 있다.문제에서 말한 연결 요소란 에지로 연결된 노드의 집합이며, 한 번의 DFS가 끝날 때까지 탐색한 모든 노드의 집합을 하나의 연결 요소로 판단할 수 있다.문제를 보고 구현과정을
24.[백준] 2023번 - 신기한 소수
문제를 읽어봤을때, 자릿수에 따라서 해당 숫자가 소수임을 확인해 보야하 하므로 N의 값이 1일때, 2일때, 3일때 어떠한 수가 가능한지를 확인해 보는 과정이 필요하다.'먼저 N의 값이 1일때, 즉 자릿수가 1자리 인 경우에는 기본적으로 1~9까지의 수 중 소수를 찾아야
25.[백준] 13023번 - ABCDE
문제를 읽어보면 알 수 있듯이 서로의 관계의 길이가 5이상인 경우를 찾으면 된다는 것을 알 수 있다.따라서 서로의 관계를 표현할 때에는 인접리스트의 형식으로 표현하고, 해당 관계들을 DFS를 사용하여, 관계의 길이가 5이상인 경우를 찾아내면 된다.문제에서 N의 최대 범
26.[백준] 1260번 - DFS와 BFS
문제에서도 알 수 있듯이 DFS와 BFS를 사용하여 주어진 조건대로 출력하는 문제이다.DFS의 경우에는 재귀함수 또는 스택을 이용하고, BFS의 경우에는 큐를 이용하므로, 해당 개념을 이용하여 풀면 된다.
27.[백준] 2178번 - 미로탐색
N, M의 최대 데이터 크기가 100으로 매우 작기 때문에 시간 제한은 별도로 생각하지 않아도 된다.문제의 요구사항은 지나야 하는 칸 수의 최솟값을 찾는 것으로, 최단거리 문제이기 때문에 BFS를 떠올릴 수 있다.해당 문제의 조건에 따라 완전 탐색을 진행하면서 몇 번째
28.[백준] 1167번 - 트리의 지름
가장 긴 경로를 찾는 방법을 구하는 문제로 다음과 같은 아이디어를 통해 경로를 구하도록 한다.가장 긴 경로 찾기 아이디어임의의 노드에서 가장 긴 경로롤 연결돼 있는 노드는 트리의 지름에 해당하는 두 노드 중 하나이다.처음에 DFS방식으로 해서 시간초과가 난 코드
29.[백준] 1920번 - 수 찾기
주어진 N의 최대 범위가 100,000이므로 O(nlogn) 시간 복잡도로 해결할 수 있다.이진탐색의 시간복잡도는 O(logn)이므로 주어진 M개의 숫자를 순서대로 보면서, A배열에서의 이진 탐색을 진행하면 O(nlogn)의 시간 복잡도로 해결이 가능하다.
30.[백준] 11047번 - 동전 0
문제의 설명을 보면 뒤의 동전 가격 Ai가 Ai-1의 배수가 된다고 하였으므로, 원하는 동전 값 K를 최소의 동전을 이용해서 만들기 위해서는 가장 가격이 큰 동전부터 차례대로 사용하면 된다.따라서 그리디 알고리즘을 떠올릴 수 있다.
31.[백준] 1715번 - 카드 정렬하기
문제를 통해 알 수 있듯 카드 묶음의 카드의 개수가 작은 순서대로 먼저 합치는 것이 전체 비교횟수를 줄일 수 있는 방법임을 알 수 있다. 이때, 더한 값을 다시 저장할때마다 정렬이 일어나야 하므로 우선순위 큐를 이용해서 해결하면 된다.
32.[백준] 1744번 - 수 묶기
문제를 읽어보고 수를 적절히 묶는 방법을 생각해보면 다음과 같이 분류될 수 있다는 것을 파악할 수 있다.'음수인 수의 목록, 0의 수의 목록, 1의 수의 목록, 1 보다 큰 양수의 목록'음수의 목록의 경우 오름차순으로 정렬이 되어 있을 때, 작은 값들 부터 곱해서 결과
33.[백준] 1931번 - 회의실 배정
문제의 상황에서도 알 수 있듯이, 1개의 회의실에 회의가 겹치지 않게 배정하기 위해서는 먼저 회의시간이 적은 회의들을 위주로 봐야되겠다고 생각할 수 있다. (회의시간이 적은 것들이 많을수록 회의의 개수는 커지기 때문)하지만 회의시간이 적다고 해서 그 회의들이 이어져 있
34.[백준] 1541번 - 잃어버린 괄호
문제에서 요구한 대로 가장 최솟값을 만들기 위해서는 가능한 큰 수를 빼야한다.주어진 수식은 + 와 - 로 이루어져 있기 때문에 더하기에 해당하는 부분에 괄호를 쳐서 먼저 모두 계산한 후,빼기를 실행하면 문제가 해결된다.
35.[백준] 1929번 - 소수 구하기
주어진 범위내에서 소수 값을 구하는 문제로 에라토스테네스의 체를 이용하여 문제를 풀면 된다.이때 'N의 제곱근 + 1' 전까지 탐색하는것에 유의하며 문제를 풀면된다.
36.[백준] 1456번 - 거의 소수
거의 소수를 구하기 위해서는 2부터 주어진 B의 값의 제곱근까지의 수 중 소수인 것들만 찾고, 해당 소수들을 주어진 A와 B사이의 범위에 맞추어 가며 제곱해 나가는 식으로 구하면된다.여기서 B의 제곱근 까지의 소수를 구하는 이유는 거의소수란 어떤 소수의 N제곱(N>=2
37.[백준] 1747번 - 소수&팰린드롬
에라토스테네스의 체를 이용해 최대 범위에 해당하는 모든 소수를 구해 놓은 후 이 소수들의 집합에서 N보다 크거나 같으면서 팰린드롬 수인 것을 찾아내면 되는 문제이다.팰린드롬 수를 판별할때 숫자의 값이 리스트 형태로 적절하게 변환이 가능하다는 점을 이용하여 투포인터를 이
38.[백준] 1934번 - 최소공배수
최소 공배수는 A와 B가 주어졌을때 'A\*B / 최대공약수'를 계산하여 구할 수 있으므로 최대공약수를 구하는 함수를 구현하여 해결하면 된다. 이때 윸클리드 호제법을 이용해 최대공약수를 구하면 된다.
39.[백준] 1850번 - 최대공약수
유클리드 호제법을 이용한 최대공약수 찾기 문제로, 주어진 주 A,B의 최대 공약수를 찾고 해당 최대공약수만큼 1을 출력해주면된다.여기서 정답은 천만 자리를 넘지 않는다고 하였으므로, for문을 사용해서 1을 출력한다 하더라도 제한시간인 2초안에 풀 수 있다는 것을 확인
40.[백준] 18352번 - 특정 거리의 도시 찾기
모든 도로의 거리가 1이므로 가중치가 없는 인접 리스트로 이 그래프를 표현할 수 있다.도시의 개수가 300,000, 도로의 최대 크기가 1,000,000이므로 BFS 탐색을 수행하면 해당 문제를 해결할 수 있다.
41.[백준] 1707번 - 이분 그래프
노드의 집합을 2개로 나누는데, 인접한 노드끼리 같은 집합이 되지 않도록 임의로 분할 할 수 있다고 한다.잘 생각해보면 트리의 경우, 항상 이분 그래프가 된다는 것을 알 수 있다.따라서 기존의 탐색 메커니즘에서 탐색한 노드에 다시 접근하게 됐을 때 현재 노드의 집합과
42.[백준] 1717번 - 집합의 표현
최대 원소의 개수가 1,000,000이고 질의 개수가 100,000으로 큰 편이므로 경로 압축을 하는 유니온 파인드를 통해 문제를 해결하면 된다. 따라서 다음과 같은 순서로 설계할 수 있다.1 처음에는 노드가 연결돼 있지 않으므로 각 노드의 대표 노드는 자기 자신이다.
43.[백준] 1976번 - 여행 가자
도시의 연결 유무를 유니온 파인드 연산을 이용해 해결할 수 있다.즉 입력으로 주어진 값들이 서로 연결되어 있는지를 파악하는 과정을 통해 문제를 해결할 수 있다.
44.[백준] 1043번 - 거짓말
문제를 통해 알 수 있듯이 같은 파티에 참석한 사람끼리는 같은 이야기를 들을 수 밖에 없다. 이 문제에서 주의해야할 점은 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 듣는 경우 지민이는 거짓말쟁이로 알려지게 된다는 점이다.따라서 같은 파
45.[백준] 2252번 - 줄 세우기
학생들을 노드로 생각하고, 키 순서 비교 데이터로 에지를 만든다고 생각했을 때, 노드의 순서를 도출하는 가장 기본적인 문제이다. 특히 답이 여러 개일때 아무것이나 출력해도 된다는 전제는 위상 정렬의 결괏값이 항상 유일하지 않다는 알고리즘의 전제와 동일하다는 것을 알 수
46.[백준] 1516번 - 게임 개발
사이클이 없는 방향그래프에서 순서를 찾는 문제이므로 위상정렬을 통해 해결할 수 있다. 이 문제를 푸는과정에서 주의해야 할 점은 다음 예와 같다.1노드 15초, 2노드 13초 3노드는 1노드와 2노드가 지어진 후 지을 수 있다고 할때,일반적인 큐를 이용해서 진입차수를 판
47.[백준] 1948번 - 임계경로
문제에서 모든 노드가 일방통행이고 사이클이 없다라고 하였으므로 위상정렬을 떠올릴 수 있다. 해당 문제는 출발 도시와 도착 도시가 주어지기 때문에 일반적인 위상정렬이 아닌 시작점을 출발 도시로 정하고 위상정렬을 수행하면서 각각의 노드까지의 거리의 최대값을 구하는 과정을
48.[백준] 1753번 - 최단경로
시작점과 다른 노드와 관련된 최단 거리를 구하는 문제로, 다익스트라 알고리즘의 가장 기본적인 문제이다.따라서 다음과 같은 매커니즘을 통해 시작점으로 부터 각각의 노드까지의 최단거리를 구하면 된다.인접 리스트로 그래프 구현하기주어진 노드들 간의 연결을 인접리스트를 이용하
49.[백준] 1916번 - 최소비용 구하기
시작점과 도착점이 주어지고, 이 목적지까지 가는 최소 비용(최단거리)를 구하는 문제이다. 또한 버스 비용의 범위가 음수가 아니기 때문에 다익스트라 알고리즘을 통해 해결 할 수 있다.
50.[백준] 1854번 - K번째 최단경로 찾기
시작점과 도착점이 주어지고 해당 목적지까지 가는 K번째 최단경로를 구하는 문제이다.K번째 최단 경로를 해결하기 위해서는 다음과 같은 아이디어로 접근하면 된다.최단 경로를 표현하는 리스트를 K개의 row를 갖는 2차원 리스트의 형태로 변경하고자 한다. 이렇게 하면 최단
51.[백준] 11657번 - 타임머신
시작점 및 다른 노드와 관련된 최단 거리를 구하는 문제지만, 특이한 점은 에지에 해당하는 이동하는 시간이 양수가 아닌 0 또는 음수가 가능하다는 점이다. 이렇게 시작점에서 다른 노드와 관련된 최단 거리를 구하는데, 에지가 음수가 가능할 때는 벨만-포드 알고리즘을 사용하
52.[백준] 1219번 - 오민식의 고민
벨만-포드 알고리즘의 원리를 바탕으로 요구사항에 따라 내부 로직을 바꿔야 하는 문제이다. 기존 벨만-포드는 최단 거리를 구하는 알고리즘이지만, 이 문제에서는 도착 도시에 도착할 때 돈의 액수를 최대로 하고 싶기 때문에 업데이트 방식을 반대로 변경해야한다. 또한 돈을 무
53.[백준] 11404번 - 플로이드
모든 도시의 쌍과 관련된 최솟값을 구하는 문제이다.그래프에서 시작점을 지정하지 않고, 모든 노드와 관련된 최소 경로를 구해야 하므로,플로이드-워셜 알고리즘을 통해 해결하면 된다.플로이드-워셜 알고리즘은 다음과 같다.DS = Math.min(DS, DS + DK)DS는
54.[백준] 11403번 - 경로 찾기
모든 노드 쌍에 관해 경로가 있는 지에 대해 묻고 있으므로, 플로이드워셜 알고리즘을 통해 문제를 풀면 된다.
55.[백준] 1389번 - 케빈 베이컨의 6단계 법칙
사람들을 각각 노드로 봤을 때, 각각의 노드에서 여러 노드로 가는 최소값을 구해주고 이러한 값들을 더해준 후, 비교하면 되므로,플로이드-워셜 알고리즘을 통해 해결하면 된다.
56.[백준] 1197번 - 최소 스패닝 트리
최소 신장 트리를 묻고 있는 문제로, 최소 신장 트리를 구하여 해결하면 된다.최소 신장 트리는 데이터를 노드가 아닌 에지 중심으로 저장하므로 인접 리스트가 아닌 에지리스트의 형태로 저장한다.이 리스트는 일반적으로 노드 변수 2개와 가중치 변수로 구성된다.또한, 사이클
57.[백준] 17472번 - 다리 만들기 2
문제에서 주어진 N과 M의 크기가 매우 작은 편이라 시간 복잡도에 제약은 크지 않다.문제를 해결하기 위해서는 먼저 주어진 지도에서 섬으로 표현된 값을 각각의 섬마다 다르게 표현하는 과정이 필요하다.이후에는 각 섬의 모든 위치에서 다른 섬으로 연결할 수 있는 에지가 있는
58.[백준] 1414번 - 불우이웃돕기
인접 행렬의 형태로 데이터가 들어오기 때문에 이 부분을 최소 신장 트리가 가능한 형태로 변형하는 것이 필요하다.먼저 문자열로 주어진 랜선의 길이를 숫자로 변형해 랜선의 총합을 저장한다.이때 i와 j가 같은 곳의 값은 같은 컴퓨터를 연결한다는 의미이므로 별도 에지로 저장
59.[백준] 11725번 - 트리의 부모 찾기
트리를 어떻게 구조화 할지에 대한 문제이다. 인접리스트로 트리의 구조를 만들어보고, DFS를 통해 비교해가면서, 부모노드의 번호를 저장해주면 된다.이때 트리의 루트 노드가 1이라고 주어져 있으므로, 1번 부터 DFS를 진행하면 된다.
60.[백준] 1068번 - 트리
트리의 관계를 인접리스트로 표현하고, DFS를 통해 부모-자식의 관계를 설정하여 표현할 수 있다.따라서 DFS 및 visited배열을 통해 주어진 입력대로 관계를 설정하고 풀어나가면 된다.
61.[백준] 14425번 - 문자열 집합
문제 분석 집합 S에 속해 있는 단어들을 이용해 트라이 구조를 생성하고, 트라이 검색을 이용해 문자열 M개의 포함 여부를 카운트하는 전형적인 트라이 자료구조 문제이다. 소스 코드
62.[백준] 1991번 - 트리 순회
문제에서 주어진 노드간의 관계를 트리 형태의 자료구조에 적절하게 저장하고, 그 안에서 탐색을 수행하면 된다.따라서 인접리스트의 형태로 트리의 관계를 표현하고, 재귀함수를 통해 탐색을 수행하여 문제를 해결하면된다.
63.[백준] 2042번 - 구간 합 구하기
해당 문제에서는 데이터 변경이 일어나므로, 데이터 변경시에 시간이 많이 소요되는 합 배열로는 풀 수 없다.따라서, 세그먼트 트리의 개념을 이용해서 풀면된다.다음의 3단계로 진행된다.트리 초기화질의 값 구하기데이터 업데이트 하기이후, 만든 트리 리스트의 2^k번째 인덱스
64.[백준] 10868번 - 최솟값
세그 먼트 트리의 개념을 이용해서, 원하는 구간의 최솟값을 구할 수 있다.주어지는 N개의 값들을 리프노드에 저장하고, 최솟값을 만족하도록 위로 올라오면서, 최솟값 트리의 형태로 만들어준다.그 후, 원하는 구간을 찾아 올라오면서 최솟값을 얻어내면 된다.
65.[백준] 11505번 - 구간 곱 구하기
문제 분석 이 문제를 풀기에 앞서 다음과 같은 개념이 필요하다. >(AB) % C == (A%C)(B%C) % C 위의 개념을 인지하며, 세그 먼트 트리를 이용해 풀면된다.