[이코테] 편집 거리

https://www.acmicpc.net/problem/15483 15483번: 최소 편집 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 소문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. www.acmicpc.net 문제 설명 두 개의 문자열 A와 B가 주어졌을 때, 문자열 A를 편집하여 문자열 B로 만들고자 합니다. 문자열 A를 편집할 때는 다음의 세 연산 중에서 한 번에 하나씩 선택하여 이용할 수 있습니다. 삽입(Insert): 특정한 위치에 하나의 문자를 삽입합니다. 삭제(Remove): 특정한 위치에 있는 하나의 문자를 삭제합니다. 교체(Replace): 특정한 위치에 있는 하나의 문자를 다른 문자로 교체합니다. 이때 편집 거리란 문자열 A를 편집하여 문자열 B로 만..

• format_list_bulleted Algorithm
• · 2021. 2. 26.
• textsms

[이코테] 팀 결성

문제 학교에서 학생들에게 0번부터 N번까지의 번호를 부여했다. 처음에는 모든 학생이 서로 다른팀으로 구분되어, 총N+1개의 팀이 존재한다. 이 때 선생님은 '팀 합치기' 연산과 '같은 팀 여부 확인' 연산을 사용할 수 있다. '팀 합치기' 연산은 두 팀을 합치는 연산이다. '같은 팀 여부 확인' 연산은 특정한 두 학생이 같은 팀에 속하는지를 확인하는 연산이다. 선생님이 M개의 연산을 수행할 수 있을 때, '같은 팀 여부 확인' 연산에 대한 연산 결과를 출력하는 프로그램을 작성하시오. 입력 조건 첫째 줄에 N,M이 주어진다. M은 입력으로 주어지는 연산의 개수이다.(1

• format_list_bulleted Algorithm
• · 2021. 2. 8.
• textsms

[이코테] 서로소 알고리즘

서로소 집합 수학에서 서로소 집합(Disjoint Sets)이란 공통 원소가 없는 두 집합을 의미한다. 예를 들어 집합[1,2]과 집합[3,4]은 서로소 관계이다. 반면에 집합 [1,2]와 집합 [2,3]은 2라는 원소가 두 집합에 공통적으로 포함되어 있기 때문에 서로소 관계가 아니다. 서로소 집합 자료구조는 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조라고 할 수 있다. 서로소 집합 자료구조는 union과 find 이 2개의 연산으로 조작할 수 있다. union(합집합) 연산은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산이다. find(찾기) 연산은 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다. 스택과 큐가 각각 push(넣기), pop(꺼내기) 연산..

• format_list_bulleted Algorithm
• · 2021. 2. 2.
• textsms

[이코테] 최단 경로 알고리즘 - 전보

실전 문제 import heapq import sys input = sys.stdin.readline INF = int(1e9) #노드의 개수, 간선의 개수 , 출발 지점 입력받기. node,line,start = map(int,input().split()) #각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기 graph = [[] for i in range(node+1)] #최단 거리 테이블을 모두 무한으로 초기화 distance = [INF] * (node+1) #모든 간선 정보를 입력받기 for _ in range(line): x,y,z = map(int,input().split()) #x번 노드에서 y번 노드로 가는 비용이 z라는 뜻 graph[x].append((y,z)) def ..

• format_list_bulleted Algorithm
• · 2020. 12. 15.
• textsms

[이코테] 최단 경로 알고리즘 - 미래도시

실전 문제 INF = int(1e9) #무한을 의미하는 값으로 10억을 설정 #노드의 개수와 간선의 개수 입력받기. node,line = map(int,input().split()) #2차원 그래프 무한으로 채워서 선언. graph = [[INF]*(node+1) for _ in range(node+1)] #자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화 for a in range(1,node+1): for b in range(1,node+1): if a == b: graph[a][b] = 0 #각 간선에 대항ㄴ 정보를 입력받아, 그 값으로 초기화. for _ in range(line): #A와 B가 서로에게 가는 비용은 1이라고 설정 a, b = map(int,input().split()) gr..

• format_list_bulleted Algorithm
• · 2020. 12. 15.
• textsms

[이코테] 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)

플로이드 워셜 알고리즘 저번에 공부했던 다익스트라 알고리즘은 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우'에 사용할 수 있는 최단 경로 알고리즘이다. 이번에 공부할 플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 사용할 수 있는 알고리즘이다. 다익스트라 알고리즘에서는 출발 노드가 1개이므로 다른 모든 노드까지의 최단 거리를 저장하기 위해서 1차원 리스트를 이용하였다. 반면에 플로이드 워셜 알고리즘에서는 다익스트라 알고리즘과는 다르게 2차원 리스트에 '최단 거리' 정보를 저장한다는 특징이 있다. 모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담아야 하기 때문이다. 그렇기 때문에 2차원 리스트를 처리해야 하므로 N번의 ..

• format_list_bulleted Algorithm
• · 2020. 12. 15.
• textsms

<