본문 바로가기

코딩테스트

 (46)
[Python] 그래프 문제 풀이 정리(1) https://www.acmicpc.net/problem/10451# 내 풀이import syssys.setrecursionlimit(2000)T = int(input())def find(a): if a==parent[a]: return a else: parent[a]=find(parent[a]) return parent[a] def union(a,b): a = find(a) b = find(b) if a!=b: parent[b]=afor _ in range(T): N = int(input()) n_list = list(map(int, input().split())) ans = set() parent ..
[Python] 트리 # 9-1 트리 알아보기트리란?노드와 에지로 연결된 그래프의 특수한 형태순환 구조(cycle)를 지니고 있지 않고, 1개의 루트 노드가 존재한다.루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖는다.트리의 부분 트리(subtree) 역시 트리의 모든 특징을 따른다.트리의 핵심 이론(구성 요소)노드 : 데이터의 index와 value를 표현하는 요소에지 : 노드와 노드의 연결 관계를 나타내는 선루트 노드 : 트리에서 가장 상위에 존재하는 노드부모 노드 : 두 노드 사이의 관계에서 상위 노드에 해당하는 노드자식 노드 : 두 노드 사이의 관계에서 하위 노드에 해당하는 노드리프 노드 : 트리에서 가장 하위에 존재하는 노드(자식 노드가 없는 노드)서브 트리 : 전체 트리에 속한 작은 트리 https://www..
[Python] 그래프(2) # 8-5. 벨만-포드벨만-포드(bellman-ford-moore) 알고리즘이란?그래프에서 최단 거리를 구하는 알고리즘특정 출발 노드에서 다른 모든 노드까지의 최단 경로까지의 최단 경로 탐색음수 가중치 에지가 있어도 수행할 수 있으며, 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있다.시간 복잡도 : O(VE)벨만-포드 핵심 이론에지 리스트로 그래프를 구현하고 최단 경로 리스트 초기화하기에지 리스트는 출발 노드, 종료 노드, 가중치 변수로 구성돼 있다.모든 에지를 확인해 정답 리스트 업데이트 하기업데이트 반복 횟수는 노드 개수 -1이다.모든 에지 E = (s,e,w)에서 D[s]!=max값 이며 D[e]>D[s]+w일 때 D[e]=D[s]+w로 리스트 값을 업데이트 한다.음수 사이클이 없을 때 ..
[Python] 그래프(1) # 8-1. 그래프의 표현 2차원 리스트python에서 3행 4열 2차원 리스트를 생성할 때는 두가지 방법이 있다.# 리스트에서 객체를 생성하는 방법A = [[0 for col in range(4) for row in range(3)]# 얕은 복사를 일으켜 생성하는 방법# 이 방식은 선언 후 값을 변경하면 다른 원소의 값도 변경될 수 있다.A = [[0]*4]*3 에지 리스트(edge list)에지를 중심으로 그래프를 표현한다. 리스트에 출발 노드, 도착 노드(+가중치)를 저장하여 에지를 표현한다.구현이 쉽지만 특정 노드와 관련되어 있는 에지를 탐색하기는 어렵다.노드 사이의 최단 거리를 구하는 벨만-포드 혹은 최소 신장 트리를 찾는 크루스칼 알고리즘에 사용한다. 인접 행렬(adjacency matrix)..
[Python] 그리디 문제 풀이 정리(2) https://www.acmicpc.net/problem/1339# 정답 풀이from collections import dequeN=int(input())A=[]num={}for _ in range(N): A.append(input())for i in A: # 각 문자열에서 for j in range(len(i)): # 문자열 알파벳 조사 k = 10**(len(i)-j-1) # 알파벳 자릿수 if i[j] in num: # dict에 있으면 더하고 num[i[j]]+=k else: # 없으면 추가 num[i[j]]=ksorted_dict = sorted(num.items(), key = lambda item: ite..
[Python] 그리디 문제 풀이 정리 https://www.acmicpc.net/problem/14916# 내 풀이n = int(input())if n%2==0: if (n%5)%2!=1: t = n//5 n%=5 k = n//2 # k는 2원 개수 n%=2 else: t = (n-5)//5 n = (n-5)%5 + 5 k = n//2 # k는 2원 개수 n%=2elif n>3: if n==5: n%=5 t = 1 k=0 else: n-=5 t = 1 k = n//2 # k는 2원 개수 n%=2 while k>=5: ..
[Python] 정수론 # 7-1. 소수 구하기전에 정리했지만 소수를 구하는 대표적인 판별법으로 에라토스테네스의 체가 있다.주어진 범위의 수 리스트를 생성한다.1은 소수가 아니므로 삭제 하고, 리스트 2부터 시작한다.선택한 수의 배수를 모두 삭제한다.이미 지운 수는 다시 지우지 않고, 지워지지 않은 수를 선택하며 리스트의 끝까지 반봇한다.이중 for문이지만 실제 시간 복잡도는 배수 삭제 연산으로 바깥쪽 for문을 생략하는 경우가 많아 O(Nlog(logN))이다.또한 N = a*b일때, a와 b는 N의 제곱근보다 클 수 없으므로 탐색은 N의 제곱근까지만 탐색한다. https://www.acmicpc.net/problem/1929import mathM, N = map(int, input().split())A = [0]*(N+1)..
[Python] DFS 문제 풀이 정리 2 문제 풀이 이어서 하기. 이번에는 골드 문제도 섞어서 도전! https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net import sys sys.setrecursionlimit(10000000) input=sys.stdin.readline n = int(input()) arr = [] visited = [[False]*n for _ in range(n)] visited2 = [[False]*n for _ in range(n)] for _ in r..

티스토리툴바