printf("Hello dev_TORY!");

https://www.acmicpc.net/problem/24444 24444번: 알고리즘 수업 - 너비 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방 www.acmicpc.net 이 문제는 트리 자료구조의 BFS 알고리즘의 대표적인 기초 문제라고 볼 수 있다. 이 문제를 해결하기 위해서는 다음과 같은 정보가 필요하다. 1. 각 노드들과 인접한 노드들의 정보 → 그래야 인접한 노드들을 타고 타고 들어갈 수 있다. 2. 각 노드들의 방문 여부 → 방문하지 않은 노드만 탐색하기 위함이다. 3. 인접 노드..

https://www.acmicpc.net/problem/24479 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 이 문제는 트리 자료구조의 DFS 알고리즘의 대표적인 기초 문제라고 볼 수 있다. 이 문제를 해결하기 위해서는 다음과 같은 정보가 필요하다. 1. 각 노드들과 인접한 노드들의 정보 → 그래야 인접한 노드들을 타고 타고 들어갈 수 있다. 2. 각 노드들의 방문 여부 → 방문하지 않은 노드만 탐색하기 위함이다. 문제에서는 1부터..

https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 이 문제는, 스택을 활용하는 대표적인 문제이다. 코드를 짜는 것은 어렵지 않으나, 풀이 알고리즘을 떠올리는 것이 어려웠다. 절단된 쇠막대기의 개수를 세기 위해 층별로 구분된 막대기에 레이저가 발사된 횟수를 세는 것이 아닌, 하나의 레이저가 발사될 때마다 해당 레이저가 몇 개(층)의 쇠막대기를 절단하고 있는지를 세어서 계산해야 한다. 로직은 다음과 같다. ')'이 들어오는 경우는 레이저이거나, 쇠막대기의 끝을..

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 이 문제는 시작 시간과 끝나는 시간으로 주어지는 여러 개의 회의 정보를 입력받아, 각 회의가 겹치지 않고 사용될 수 있는 회의실의 최대 개수를 구하는 문제이다. 그리디 알고리즘을 활용하는 대표적인 문제이다. 1. 끝나는 시간을 기준으로 오름차순 정렬 회의를 최대한 많이 하기 위해서는, 시작 시간이 중요할까? 끝나는 시간이 중요할까? 1시에 시작해서 5시에 끝나는 회의와 1시에 시작해서 9시에 끝나는 회의를 입력받았다고 가정해보자. 1시에 시작해서 5시에 끝난다면, 5시가 넘어서(5시도 포함) 진행되는 회의 전체가..

https://www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 이 문제는 단순히 큐에 대한 문제이다. 그래서 큐를 열심히 구현했는데 시간초과가 나왔다. 아래 코드는 시간초과가 나온 코드이다. class MyQueue: def __init__(self): self.myQueue = [] def push(self, n): self.myQueue.append(n) def pop(self): if len(self.myQueue)==0: re..

https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 위 문제는 냅다 구현해버리면 이중 반복문을 사용하게 되어 시간 복잡도가 O(N^2)이 되므로 시간 초과가 나온다. 시간 초과 풀이) n, m = list(map(int, input().split())) nums = list(map(int, input().split())) s = [] tmp = 0 cnt = 0 for i in range(len(nu..

https://www.acmicpc.net/problem/2670 2670번: 연속부분최대곱 첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다. N은 10,000 이하의 자연수이다. 실수는 소수점 첫째자리까지 주어지며, 0.0보다 크거나 www.acmicpc.net 위 문제는 DP를 이용해 푸는 전형적인 DP문제이다. 곱해지는 수로 인해 일시적으로 값이 작아져도 후에 뒤쪽에 1보다 큰 수가 위치할 경우, 커질 수 있기 때문에 뒤쪽까지 모두 탐색해보는 브루트포스 알고리즘을 사용했다. n = int(input()) a = [] for i in range(n): a.append(float(input())) dp = [0 for i in range(n)..

https://www.acmicpc.net/problem/2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 해당 문제는 단순히 있는 그대로 구현하면, 시간 초과가 나온다. 시간 초과가 나온 코드 먼저 보자. n = int(input()) cnt = 1 s = 0 flag = 0 for i in range(int(n//2)+1, 0, -1): s += i for j in range(i-1, 0, -1): s += j flag += 1 if s == n: cnt += 1 break e..

https://www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다. www.acmicpc.net 스스로 풀기는 했지만 시간이 오래걸렸기 때문에, 포스팅하며 코드를 리뷰해보고자 한다. 위 문제는 임의의 수 N을 입력받아 1부터 N까지를 이어서 쭉 썼을 때, 전체의 자릿수를 구하는 문제이다. 아마 반복문으로 N까지 돌리면 시간초과가 나올 것이다. 따라서, 나는 입력받은 수의 자릿수를 구해서 반복문 통해 해결하였다. 알고리즘을 정리하자면 다음과 같다. 전체 자릿수를 구해주기 위해서는 각 자릿수의 갯수 * 각 자릿수의 길이를 해주어야 한다. 예를들면 십의 자릿수를 갖는 수는 10~99까지 총 90개가 존재하므로, 90*..

https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 이 문제는 단순히 거듭제곱의 결과를 나누어 나머지를 출력하는 문제이다. 하지만, 일반적으로 사용하는 반복문을 사용하여 거듭제곱을 구할 경우, 시간초과가 난다. 왜냐하면 반복문을 이용한 거듭제곱은 N번 곱해줘야하므로 시간복잡도가 O(N)이 나오기 때문이다. 시간 복잡도를 줄이기 위해서는 분할 정복 이라는 알고리즘을 사용해야된다. 분할 정복 알고리즘을 사용하면 시간복잡도를 O(logN)으로 줄일 수 있다. 따라서 분할정복 알고리즘에 대해 간단히 살펴보고 분할정복 알..