'컴퓨터' 카테고리의 글 목록

2024. 8. 8. 16:36 컴퓨터/BASIS

git log --graph --simplify-by-decoration --pretty=format:'%d' --all 이렇게 하시면 됩니다

2022. 10. 11. 18:43 컴퓨터/코딩테스트

[문제] [코드] 이 문제는 위상 정렬을 이용해서 풀면 된다. 위상 정렬에 대한 내용은 여기에 정리해 두었다. https://woo-niverse.tistory.com/237?category=1038170 정렬 알고리즘 : 위상 정렬 (Topological Sorting) 방향이 있는 그래프의 정점들을 방향대로 나열하는 것 위상 정렬의 예시 예시를 위해 자랑스러운 나의 전공, 국문학과의 국어학 커리큘럼을 가져와보았다. 보통 'OO론' 과목은 'OOO의이해' 수업을 woo-niverse.tistory.com 먼저, 큐를 이용한 방법 import sys from collections import deque input = sys.stdin.readline N, M = map(int, input().split(..

정렬 알고리즘 : 위상 정렬 (Topological Sorting)

2022. 10. 11. 18:00 컴퓨터/알고리즘&자료구조

방향이 있는 그래프의 정점들을 방향대로 나열하는 것 위상 정렬의 예시 예시를 위해 자랑스러운 나의 전공, 국문학과의 국어학 커리큘럼을 가져와보았다. 보통 'OO론' 과목은 'OOO의이해' 수업을 선수과목으로 하여, 순서상 '이해' 과목을 먼저 들어야 한다. 그리고 제일 마지막은 역시.. 대학원 수업인 'OOO연구'. '국어학의이해'를 듣지 않고 '국어형태론'을 먼저 수강했다간 큰 코 다칠 수가 있다. 위상정렬을 사용하면 올바른 수강 순서를 찾을 수 있다. DAG(Directed Acyclic Graph) 위상 정렬은 사이클이 존재하지 않는 유향 그래프에 적용할 수 있다. 사이클이 존재한다면 출발점을 알 수 없기 때문에 위상 정렬이 불가능. 진입차수 & 진출차수 위상 정렬을 위한 '진입차수'와 '진출차수'..

그래프 탐색 : BFS(너비 우선 탐색)

2022. 10. 7. 13:19 컴퓨터/알고리즘&자료구조

지난 글에서 DFS(깊이 우선 탐색)에 대해 알아보았다. 오늘은 BFS(너비 우선 탐색)에 대해 알아보자. BFS(너비 우선 탐색) - 임의의 노드에서 시작해 인접 노드를 먼저 탐색한다. - 두 노드 사이의 최단 경로를 알고 싶을 때 실시할 수 있다. (DFS의 경우 모든 그래프를 살펴봐야 할 수 있음) 방문 순서 A → B → C → D → E → F → G → H → I → J → K 큐를 활용한 구현 BFS는 큐를 활용할 수 있다. 큐는 선입선출의 자료구조로, 먼저 들어온 데이터가 먼저 나가게 된다. BFS에서는 지금 시점에서 방문할 수 있는 노드들을 큐에 넣게 된다. A를 출력하면서, A의 인접 노드들을 쌓는다. 그 다음은 먼저 들어갔던 노드가 출력된다. 반복. 먼저 인접리스트 형식으로 그래프를 ..

그래프 탐색 : DFS(깊이 우선 탐색)

2022. 10. 7. 12:34 컴퓨터/알고리즘&자료구조

그래프를 탐색하는 알고리즘에는 DFS(Depth-First Search, 깊이 우선 탐색)과 BFS(Breadth-First Search, 너비 우선 탐색)이 있다. 오늘은 DFS 알고리즘에 대해 알아보자. 그래프를 탐색한다는 것 = 하나의 정점에서 시작하여 그래프의 모든 정점들을 방문하는 것 알아야 할 용어 : 루트 노드 (뿌리), 형제 노드 (같은 레벨에 놓은 노드들), 자식 노드 (어떤 노드 아래에 속한 노드) DFS(깊이 우선 탐색) "한 놈만 팬다" - 임의의 노드에서 시작해 자식 노드를 타고 제일 깊숙히 내려간다. 다시 돌아와 다른 형제 노드의 자식 노드를 타고 제일 깊숙히 내려간다. - DFS가 언제 필요할까? 모든 노드를 방문하고자 할 때 (모든 경우의 수를 구할 때 쓰기에 좋겠다!) - ..

[백준/약점체크] 16916번: 부분문자열

2022. 10. 7. 09:39 컴퓨터/코딩테스트

[문제] 링크: https://www.acmicpc.net/problem/16916 [내 코드] 문제를 해결하기 위해서 KMP 알고리즘을 공부하고 구현했다. 자세한 내용은 이 글을 참고. def LPS(pat, lps): leng = 0 i = 1 while i < len(pat): if pat[i] == pat[leng]: leng += 1 lps[i] = leng i += 1 else: if leng == 0: lps[i] = 0 i += 1 else: leng = lps[leng-1] def KMP(txt, pat): N = len(txt) M = len(pat) lps = [0] * M LPS(pat, lps) i = j = 0 while i < N: if pat[j] == txt[i]: j +=..

문자열 검색 : LPS와 KMP 알고리즘

2022. 10. 6. 19:16 컴퓨터/알고리즘&자료구조

문자열을 검색하는 문제를 해결하려고 한다. LPS와 KMP 알고리즘에 대해서 알아보자. 문제 'soo'가 'yunsoowoo'의 부분 문자열인지 알고 싶다면? 나이브하게 한 문자씩 대조해가며 알아보는 방법이 있다. 하지만 원본 문자열 yunsoo의 길이가 N이고 탐색 문자열 soo의 길이가 M일 때 시간복잡도가 최악의 경우 $O(NM)$으로 비효율적이다. LPS(Longest Prefix Suffix) 접두사(Prefix)와 접미사(Suffix) LPS 를 위해서는 문자열 맨앞에 있는 접두사와 맨뒤에 있는 접미사가 같은 경우를 먼저 찾아야 한다! 아래 문자열에서 서로 일치하는 접두사와 접미사를 찾아보자. 'AB'라는 문자열이 앞과 뒤에서 반복되는 것을 볼 수 있다. LPS는 서로 동일한 접두사와 접미사가..

최소 신장 트리 구하기 : 프림(Prim's) 알고리즘

2022. 10. 5. 19:04 컴퓨터/알고리즘&자료구조

프림 알고리즘은 최소 신장 트리를 구하는 데 사용한다. (최소 신장 트리를 구하는 또다른 방법으로 크루스칼 알고리즘이 있는데, 이에 대한 글은 여기서 보면 된다.) https://woo-niverse.tistory.com/227 최소 신장 트리 구하기 : 크루스칼(Kruskal) 알고리즘 신장 트리(Spanning Tree) 모든 정점을 연결하되, 사이클이 존재하지 않는 그래프 위 그래프에서 신장 트리를 찾는다면? 아래와 같이 다양한 신장 트리를 만들 수 있다!!! 원본 그래프의 부분 그래프 woo-niverse.tistory.com 프림 알고리즘 - 매순간의 최선의 조건을 선택하는 그리디 알고리즘 - 인접 정점들 중에서 가중치가 가장 작은 간선으로 연결된 정점을 찾는다 - 간선을 중심으로 하는 크루스칼..

티스토리툴바