흰 스타렉스에서 내가 내리지

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net N의 범위가 500,000이다. Brute Force로 했을 때, 백만개의 데이터에 대해 for문을 돌려야 하므로 당연히 시간초과가 나겠거니 하고, 중복조합 등 다양한 방법으로 접근했지만, 생각보다 너무 복잡해져서, 구글링을 해보았다. 그런데 백만개의 데이터를 일일히 해도 시간초과가 나지 않는 것 같아 실제로 해보니 통과했다. 제한시간 2초에, 연산은 백만번에 O(N)이면 괜찮나 ..

https://www.acmicpc.net/problem/17427 17427번: 약수의 합 2 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 시간제한이 0.5초에 데이터의 범위는 1,000,000 이하이므로 O(n) (=약수를 하나하나 구하는것)은 시간초과가 난다. 1~n 의 수 중에서 1을 약수로 가지는 수는 n개, 2를 약수로 가지는 수는 n/2 개 ... 라는 것을 이용해야 한다. N = int(input()) ret = 0 for i in range(1, N+1): re..

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 입력 개수는 100,000개이고 시간제한이 0.1초이다. 일반적인 풀이 방법으로는 시간초과가 날게 분명하다. 도무지 방법이 떠오르지 않아 풀이를 찾아보았다. # 풀이 힙을 두 개 사용하여 입력 값들을 분배한다. 두 힙의 이름을 left와 right라고 하면, left와 right의 길이가 같으면 left에 요소를 삽입한다. 그렇지 않으면 right에 삽입한다. left와 right..

https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net # 1 N = int(input()) graph = [-1] for i in range(1, N+1): graph.append(int(input())) res = [] def dfs(v): visited[v] = True ret = graph[v] if not visited[graph[v]]: ret = dfs(graph[v]) return ret for i in range(1, N+..

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net N, S = map(int, input().split()) data = list(map(int, input().split())) end = 0 interval_sum = 0 answer = 1e9 for start in range(N): while interval_sum < S and end < N: interval_sum += data[end] end += 1 if interval..

https://www.acmicpc.net/problem/24040 24040번: 예쁜 케이크 Good Bye BOJ, 2021!이 열리는 오늘, 12월 31일은 종서의 생일이다. $N$ 명의 친구들은 종서에게 생일 선물로 예쁜 케이크를 만들어주려 한다. 여기에서, 예쁜 케이크는 다음과 같은 조건을 만족하는 www.acmicpc.net for _ in range(int(input())): n = int(input()) if (n-2)%3 == 0 or n%9==0: print('TAK') else: print('NIE') N의 범위가 저 정도면 O(1)의 알고리즘으로 풀어야 하며, 즉 정수론적으로 접근해야 함을 바로 파악해야 한다. 감이 안잡힐땐, 무작정 1부터 다 해보자. 패턴이 보일 것이다. 너무 깊..

* 1초 기준 n ≤ 500 : 시간복잡도 O(N^3) 가능 n ≤ 2,000 : 시간복잡도 O(N^2) 가능 , 시간제한이 5초라면 O(N^3)도 가능 n ≤ 200,000 : 시간복잡도 O(NlogN) n ≤ 10,000,000 : O(N) 기타 : 무조건 O(logN) ex)이진탐색 N의 범위를 보고 어떤 알고리즘을 사용해야 할지 머릿 속으로 대충은 그려져야 한다.

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 1 . DFS를 이용한 풀이 import sys from collections import deque n, m = map(int, sys.stdin.readline().split()) maze = [] for _ in range(n): maze.append(list(map(int, list(sys.stdin.readline().rstrip('\n'))))) def isSafe(maze, x, y, mark): if x=m or ..

https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net from operator import itemgetter n = int(input()) data = [] for _ in range(n): name, kor, eng, math = input().split() data.append([int(kor), int(eng), int(math), name]) data.sort(key = itemgetter(3)) data.sort(ke..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net n, ans = int(input()), 0 a, b, c = [False]*n, [False]*(2*n - 1), [False]*(2*n - 1) def solve(j): global ans if j == n: ans += 1 return for i in range(n): if not (a[i] or b[i+j] or c[j-i+n-1]): a[i] = b[i+j] = c[j-i+n-1] = True solve..