본문 바로가기

분류 전체보기112

강한 결합 요소(Strongly Connected Components) 강한 결합 요소 : 그래프 안에서 강하게 결합된 정점 집합 cf> scc 활용 : scc마다 묶으면 cyclic 존재하지 않는 방향 그래프이기에 위상정렬 수행 가능하다 1. 알고리즘 코사라주 알고리즘(Kosaraju's Algorithm) 타잔 알고리즘(Tarjan's Algorithm) (1) 타잔 알고리즘 : 모든 정점에 대해 DFS(Depth-First Search, 깊이 우선탐색)을 수행하여 scc 찾는 알고리즘 : 부모로 돌아올 수 있어야 scc 성립 : 각 정점마다의 부모 노드가 무엇인지 기록(초기값은 자기자신) => union-find algorithm 개념과 비슷 (2) 작동 방식 1) 정점번호가 낮은 순으로 DFS 탐색 (이때, 연결리스트 통해 오름차순으로 정렬하였음) 2) 현재 정점의 .. 2023. 8. 15.
위상정렬(Topology sort) 위상정렬 : 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘(=순서결정 알고리즘) : DAG(Directed Acyclic Graph)인 경우에만 적용 가능 : 여러 개 답이 존재할 수 있음 => 현재 그래프는 위상 정렬이 가능한지 알려줌(정렬을 다 수행하지 않았는데 공백 큐가 발생하면 위상 정렬 실패, 순환그래프) => 위상정렬이 가능하다면 그 결과가 무엇인지 알려줌(정렬 수행한 위상정렬 결과) 1. 동작방식 1) 진입차수가 0인 정점을 큐에 삽입 2) 큐에서 원소를 꺼내 연결된 모든 간선 제거(연결리스트 이용) 3) 간선 제거 이후 0이 된 정점들을 큐에 다시 삽입 4) 큐가 빌 때까지 2~3) 과정을 반복 -> 이때, 모든 원소를 방문하기 전 큐가 빈 경.. 2023. 8. 14.
Floyd Washall Algorithm(플로이드 와샬 알고리즘) 1.플로이드 와샬 알고리즘 : 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘 :2차원 배열 이용하여 계속적으로 비용 업데이트 cf> 다익스트라(Dijkstra Alogrithm) :한 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로 :1차원 배열 이용 #include #define INF 100000 void Floyd_Washall(int(*g)[4], int size) { int cost[4][4] = { 0 }; int i, j,k; for (i = 0; i < size; i++) { for (j = 0; j < size; j++) { cost[i][j] = g[i][j]; } } for (i = 0; i < size; i++) { for (j = 0; j < size; j++) .. 2023. 8. 14.
카이사르 암호화/복호화 1. 암호화 과정 from util.header import printHeader def caesarCipher(plaintext, key): first = ord(' ') last = ord('~') ciphertext ='' for char in plaintext: ciphertext+=chr((ord(char)-first+key)%(last-first+1)+first) return ciphertext def main(): printHeader("1-3 Making Caesar Ciphertext", "2023-08-11","(c) Jeong, Min-Ji") plaintext = input("암호화할 문장을 입력하세요: ") cipherKey= int(input("key값을 정하시오:")) ciph.. 2023. 8. 12.
Dijkstra Algorithm[C] 다익스트라 알고리즘 : Dynamic Programming을 활용한 최단 경로 탐색 알고리즘 "현재까지 알고있던 최단경로를 계속해서 갱신해나가는 알고리즘" : 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줌 =>이때 최단거리는 그 이전까지 구했던 최단 거리 정보를 그대로 사용하기에 DP활용 알고리즘이다 ver1)선형탐색 1. 동작 방식 1) 출발 노드 설정(start 변수) 2) 초기에 출발 노드를 기준으로 각 노드의 최소 비용 저장 3) 방문하지 않은 노드 중 가장 비용이 적은 노드 선택 => 선형탐색과 힙 이용한 두 가지 구현방식 존재 4) 해당 노드를 거쳐 특정 노드로 가는 경우를 고려하여 최소 비용 갱신 5) 3~4) 과정 반복 => 이때 반복문을 이용하여 방문하지 않는 모든 .. 2023. 8. 11.
Day1 from datetime import datetime #별 출력 함수 def starLine(length): for i in range(length): print("*", end="") print("") #공백 출력 함수 def printSpace(length): for i in range(length): print(' ', end="") title = "1-1: Making Header" date = [datetime.today().year, datetime.today().month, datetime.today().day] date = list(map(lambda x: str(x), date)) date= '.'.join(date) name = "(c) Jeong, Min-Ji" titleLength .. 2023. 8. 9.

티스토리툴바