최솟값 [골드 1] 문제 링크 https://www.acmicpc.net/problem/10868 풀이 세그먼트 트리를 활용하여 문제를 푼다. 매번 주어진 범위를 구해 문제를 풀면 O(NM)의 시간복잡도를 갖기 때문에 시간 초과가 난다. 세그먼트 트리의 경우 범위 조회에는 O(lgN), 위 문제의 경우 업데이트는 없지만 O(lgN)의 시간 복...

플로이드 와샬 개념 모든 최단 경로를 구하는 알고리즘으로 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 다익스트라와 차이가 있다. 다익스트라와 다르게 음의 간선이 있어도 계산 가능하다. 임의의 정점 S에서 E까지 가는데 걸리는 최단 거리를 구하기 위해, S와 E 사이의 노드인 M에 대해 S에서 M까지 걸리는 최단 거리와 M에서 E까지...

위상 정렬 개념 선행 조건이 있는 작업을 차례로 수행해야 할 때, 이를 결정하기 위해 사용하는 알고리즘. 사이클이 존재하지 않는 방향 그래프, DAG_(Directed Acyclic Graph)_에만 적용 가능하다. 진입 차수가 0인 정점을 큐에 삽입 큐에서 원소를 꺼내 연결된 모든 간선을 제거 수행 후 진입 차수가 0이 된 정점을 ...

다익스트라 개념 다이나믹 프로그래밍을 활용한 최단 경로 알고리즘으로 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 계산한다. 구현 출발 노드 설정 출발 노드 기준으로 각 노드의 최소 비용 저장 방문하지 않은 노드 중 가장 비용이 적게 드는 노드 선택 선택한 노드를 거쳐 특정한 노드로 가는 경우를 고려해 최소 비용 ...

AxB [브론즈 5] 문제 링크 https://www.acmicpc.net/problem/10998 풀이 #include<iostream> using namespace std; int A, B; int main(void) { cin >> A >> B; cout << A * B; ...

A + B - 5 [브론즈 5] 문제 링크 https://www.acmicpc.net/problem/10952 풀이 #include<iostream> using namespace std; int main(void) { int a, b; while(true) { cin >> a >&gt...

세그먼트 트리 (구간 합 트리) 개념 이진 트리의 형태로 여러 개의 데이터가 존재할 때 특정 구간의 합을 구하는데 사용하는 자료구조이다. 구간 (a,b)에 대한 구간 합 연산 시 O(lgN), i번째 수를 j로 바꿀 시 O(lgN)의 시간 복잡도를 갖는다. 구현 세그먼트 트리 인덱스는 1부터 시작하는데, 이는 세그먼트 트리를 재귀적으로 구성할...

아스키 코드 [브론즈 5] 문제 링크 https://www.acmicpc.net/problem/11654 풀이 character 타입 변수 입력 후 int 형태로 출력한다. #include<iostream> using namespace std; char ch; int main(void) { cin >> ch;...

AC [골드5] 문제 링크 https://www.acmicpc.net/problem/5430 풀이 문자열에서 숫자를 파싱 후 Reverse, Delete 명령어를 구현을 한다. 이를 자료구조의 특성을 이용해 Queue와 Stack을 써서 Reverse에 따라 어느 자료구조에서 데이터를 pop 할지 정한다. #include <iostre...

Z [실버1] 문제 링크 https://www.acmicpc.net/problem/1074 풀이 4분할된 사각형의 모음으로 간주하고, 구해야할 row, column 값에 따라 단계별 블록 수를 점진적으로 더해주며 row, column을 갱신한다. #include<iostream> using namespace std; int N,...