출처 : 백준, https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net 진짜 너무 어렵다 이러면서 머리를 싸맸는데 바본가봐.........하긴 올해도 2022년인데........ 더보기 풀이 if __name__ == '__main__': E, S, M = map(int, input().split()) for i in range(7980): if i % 15 == E-1 and i % 28 == S-1 and i % 19 == M-1: print(i + 1..
출처 : 백준, https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 더보기 풀이 if __name__ == '__main__': date = int(input()) consult = [[0, 0]] for _ in range(date): consult.append(list(map(int, input().split()))) matrix = [[0] * (date+1) for _ in range(date+1)] for j in range(1, date + 1): for i in range(1, date + 1): first = matrix[i][j-1] score = consult[j][..
출처 : 백준, https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 더보기 풀이 from itertools import combinations def calTeamScore(team, matrix): sum = 0 for i in range(0, len(team)): for j in range(i, len(team)): sum += matrix[team[i]][team[j]] + matrix[team[j]][team[i]] return sum if __name__ ==..
출처 : 백준, https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 더보기 첫 번째 풀이 : 틀림 def forLeftRight(candy, current, visited = None): [row, col] = current color = candy[row][col] count = 0 for index in range(col, -1, -1): if candy[row][index] == color: count += 1 if visited: visited[row][index] = 1 else: break for index in range(col+1, len(candy)..
출처 : 백준, https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 더보기 풀이 count = 0 def recursion(n): global count if not n: count += 1 return for i in range(3, 0, -1): if n >= i: recursion(n-i) for i in range(int(input())): recursion(int(input())) print(count) count = 0 재귀를 이용해 풀었다. 로직은 다음과 같다. 1. for문을 통해 3부터 1까지 감소하게 돌린다. 2. 들어온 수 n..
출처 : 백준, https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 더보기 첫 번째 풀이 : 실패 if __name__ == '__main__': n = int(input()) count_arr = [0] * (n+1) count_arr[1] = 1 count_arr[2] = 2 for i in range(3, n+1): count_arr[i] = count_arr[i-1] + count_arr[i-2] print(count_arr[n] % 10007) runtime ..
본 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리하는 글입니다. DAG (Directed Acyclic Graph) Directed : 방향성 있는 Acyclic : 싸이클이 없는 Graph : 그래프 즉, 싸이클이 없는 방향 그래프를 의미한다. 이를 만족하기 위해서는 모든 방향이 한쪽으로만 향해야한다. 작업의 순서와 같은 알고리즘을 표현할 때 주로 사용된다. 위상 정렬 (Topological Ordering) 위상 정렬은 그래프를 순서대로 시작점부터 종점까지 나열하는 정렬을 말한다. BFS와 DFS는 무방향 그래프와 방향 그래프 모두에게 적용 가능하지만 위상 정렬은 DAG에만 적용될 수 있다. 위상정렬을 구현하는 방법으로는 2가지가 있는데 1. Incomming Edge(노드로 들어..
순회 그래프를 탐색하는 것을 말한다. 그래프는 Adjacency Matrix의 형태나 Adjacency List의 형태로 구현되며 순회 함수 호출 시 이 형태로 들어간다. 순회 방법으로는 대표적으로 BFS와 DFS가 있는데 둘 모두 무방향 그래프와 방향 그래프 모두 사용 가능하다. 다만 방향 그래프에서는 어떤 노드에서 시작하느냐에 따라서 모든 노드를 순회할 수 없는 경우의 수가 생길 수 있다. BFS (너비 우선 탐색) BFS는 너비 우선 탐색으로 시작 노드부터 시작하여 그 노드와 연결된 노드들을 차례대로 방문하는 방법이다. Queue를 이용해서 구현할 수 있으며, 노드 N1로부터 노드 N2까지의 최단 경로를 알아내는데 주로 사용된다. 반복문을 이용한 BFS 문제 풀이 : 게임 맵 최단거리 DFS (깊이..
출처 : 백준, https://www.acmicpc.net/problem/9655 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 사기칠라고 진짜.. 더보기 풀이 n = int(input()) if n % 2 == 0: print('CY') else: print('SK') 원리는 간단하다. 돌은 무조건 1개 아니면 3개만 가져갈 수 있다. 만약 돌이 2개가 남아도 2개를 다 취할 수 없다. 즉, 상근이와 창영이가 한 턴을 끝내면 무조건 서로 홀수 개씩 가져가고 끝나게 되므로 한 턴 종료시 돌은 전체에서 짝수 개가 사라진다. 플레이어는 둘 뿐이므로 돌의 개수가 홀수라면 턴이 다 돌고 새 턴에서 돌이 남아 상근이가 우승하고, 짝수라면..
출처 : 백준, https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 다른 사람들 풀이 보니까 다 비슷하던데 나만 이렇게 생각했나봐............. 더보기 풀이 def solution(world): sum = 0 for line in world: count = 0 ing = False for box in line: if not ing and box == 1:#counting 시작 ing = True elif ing and b..
출처 : 백준, https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 더보기 풀이 def solution(pars): open = ['(', '['] close = [']', ')'] stack = [] prev_p = '' eq = '' for p in pars: if p in open: if prev_p in open: # 3. 열림-열림일 경우 : 식에 ( 괄호 추가 eq += '(' elif prev_p in close: # 5. 닫힘-열림..
출처 : 백준, https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 더보기 첫 번째 풀이 : 시간초과 from itertools import permutations def solution(num_arr, char_arr): per_char = permutations(char_arr, len(char_arr)) max_val = -1000000001 min_val = 1000000001 for ..
