알고리즘

똑같은 수나 문자를 여러 번 곱하는 것을 거듭제곱이라고 한다. 흔히 우리가 말하는 2의 4제곱(2^4=16), 5의 3제곱(5^3=125) 등은 거듭제곱을 표현한 것이다. 당연히 코드를 통해서 이를 빠르게 계산할 수 있다. 반복문 사용 a의 n제곱 값을 구하고 싶을 때, for문을 사용해 직관적으로 다음과 같은 코드를 작성할 수 있다. def power(a, n): ans = 1 for _ in range(n): ans *= a return ans 재귀함수 사용 반복문이 아닌 재귀적 방식으로도 위 코드를 구현할 수 있다. a의 n제곱을 쭉 풀어보면 다음과 같다. 위 식은 부분문제로 나눌 수 있다. 만약 a의 n제곱이 아닌 a의 n+1제곱을 구하고자 할 땐 a^n의 값에 a를 한 번 더 곱해주면 되는데, ..

문제 (링크) https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 나의 풀이 # 오답 import sys from collections import deque input = sys.stdin.readline move = [ [1, 0], [-1, 0], [0, 1], [0, -1] ] r, c = map(int, input().split()) dist = [[int(1e9)] * c for _ in range(r)] q_jihun =..

문제 (링크) https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 나의 풀이 import sys import heapq input = sys.stdin.readline n, m = map(int, input().split()) start = int(input()) graph = [[] * (n+1) for _ in range(n+1)] INF = int(1e9) distance = [INF] * (n+1) fo..

문제 (링크) https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 나의 풀이 n = int(input()) stairs = [0] * (n + 1) d = [0] * (n + 1) for i in range(1, n + 1): stairs[i] = int(input()) # 계단은 한 번에 한 개 or 두 개 # 세 개 연속 X # 마지막 무조건 도착 if n == 1: print(stairs[n]) elif n == 2: print(stairs[1] + st..

문제 (링크) https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 나의 풀이 n = int(input()) schedule = [] for _ in range(n): schedule.append(list(map(int, input().split()))) schedule = sorted(schedule, key= lambda x: x[0]) schedule = sorted(schedule, key= lambda x: x[1]) ans = 1 end_time = schedule[0][1] for i in range(1, n): if end_time

문제 (링크) https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 나의 풀이 n = int(input()) ans = 0 cities = list(map(int, input().split())) prices = list(map(int, input().split())) min_price = 1000000000 min_price_index = -1 for i in range(n-1): if prices[i] < min_price: min..

문제 (링크) https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 나의 풀이 n = int(input()) dp = [[0, 0] for _ in range(41)] dp[0][0] = 1 dp[0][1] = 0 dp[1][0] = 0 dp[1][1] = 1 for i in range(2, 41): dp[i][0] = dp[i-1][0] + dp[i-2][0] dp[i][1] = dp[i-1][1] + dp[i-2][1] n_list = [] for _ in range(n): n_list.append(int(input())) for n in n..

문제 설명 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요. 제한사항 삼각형의 높이는 1 이상 500 이하입니다. 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다. 입출력 예 triangle result [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 나의 풀이 def..