ADsP 시험 접수..
2022. 10. 6. 20:42
수학과 통계/통계
통계 공부를 위해 ADsP 시험을 접수했다. 내 5만원 안녕~ 시험은 10월 29일, 3주 남았다. 열심히 해서 합격 후기를 남겨야겠다~
![thumbnail](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FZprTL%2FbtrNVhmSRgT%2FVaf0DUaaasqycCB53jP1Xk%2Fimg.png)
문자열 검색 : 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는 서로 동일한 접두사와 접미사가..
![thumbnail](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FPcmUn%2FbtrNQp6LayN%2F8hAaNCutOU7ZOgSbIe9Zw0%2Fimg.png)
최소 신장 트리 구하기 : 프림(Prim's) 알고리즘
2022. 10. 5. 19:04
컴퓨터/알고리즘&자료구조
프림 알고리즘은 최소 신장 트리를 구하는 데 사용한다. (최소 신장 트리를 구하는 또다른 방법으로 크루스칼 알고리즘이 있는데, 이에 대한 글은 여기서 보면 된다.) https://woo-niverse.tistory.com/227 최소 신장 트리 구하기 : 크루스칼(Kruskal) 알고리즘 신장 트리(Spanning Tree) 모든 정점을 연결하되, 사이클이 존재하지 않는 그래프 위 그래프에서 신장 트리를 찾는다면? 아래와 같이 다양한 신장 트리를 만들 수 있다!!! 원본 그래프의 부분 그래프 woo-niverse.tistory.com 프림 알고리즘 - 매순간의 최선의 조건을 선택하는 그리디 알고리즘 - 인접 정점들 중에서 가중치가 가장 작은 간선으로 연결된 정점을 찾는다 - 간선을 중심으로 하는 크루스칼..
![thumbnail](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbUjtTp%2FbtrNSBZPmL7%2FIaRz80X2cojm7IZ5KHjvo1%2Fimg.png)
[백준/약점체크] 1197번: 최소 스패닝 트리
2022. 10. 5. 18:27
컴퓨터/코딩테스트
[문제] [정답] 최소 신장 트리는 크루스칼 알고리즘이나 프림 알고리즘으로 찾을 수 있다. 크루스칼 알고리즘과 이를 위한 합집합 찾기 알고리즘 그리고 프림 알고리즘에 대한 글을 별도로 작성했으니 참고하면 되겠다. 크루스칼 알고리즘 import sys input = sys.stdin.readline V, E = map(int, input().split()) Vroot = [i for i in range(V+1)] Elist = [] for _ in range(E): Elist.append(list(map(int, input().split()))) Elist.sort(key=lambda x: x[2]) def find(x): if x != Vroot[x]: Vroot[x] = find(Vroot[x]) r..
![thumbnail](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FsIOms%2FbtrNMaO6whA%2FKfdjawNw9cNtQ5DCxmrsFk%2Fimg.png)
최소 신장 트리 구하기 : 크루스칼(Kruskal) 알고리즘
2022. 10. 5. 01:20
컴퓨터/알고리즘&자료구조
신장 트리(Spanning Tree) 모든 정점을 연결하되, 사이클이 존재하지 않는 그래프 위 그래프에서 신장 트리를 찾는다면? 아래와 같이 다양한 신장 트리를 만들 수 있다!!! 원본 그래프의 부분 그래프이므로 여러 개가 생길 수 있다 최소 신장 트리(Minimum Spanning Tree, MST) 신장 트리 중에서 간선 가중치의 합이 최소인 것 사용 사례 - 도시를 모두 연결하는 도로의 비용이 최소가 되는 것을 구하기 - 전화선의 길이가 최소가 되도록 전화 케이블 망을 구성하기 대표 알고리즘 - 크루스칼(Kruskal) 알고리즘 - 프림(Prim) 알고리즘 크루스칼 알고리즘 - 그래프의 간선들을 가중치의 오름차순으로 정렬한다 - 정렬된 순서대로 간선들을 선택한다 - 사이클이 발생하지 않도록 한다 동..
![thumbnail](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FTQCMp%2FbtrNNMNn7HZ%2FvuYgmJWGAK5Vvf6h8zYlb0%2Fimg.png)
합집합 찾기(union-find)
2022. 10. 5. 00:44
컴퓨터/알고리즘&자료구조
최소 신장 트리 찾기 문제를 풀어보려고 했더니, 크루스칼 알고리즘을 알아야 된다고 한다. 크루스칼 알고리즘을 공부하려고 했더니, 합집합 찾기 알고리즘을 알아야 한다고 한다. 오늘은 합집합 찾기 union find 알고리즘을 공부해보자! 크루스칼(Kruskal) 알고리즘 - 가장 적은 비용으로 모든 노드를 연결한다 - 그리디 알고리즘에 해당한다 - 최소 신장 트리에는 사이클이 존재하면 안 되는데, 사이클의 발생 여부를 union-find로 확인할 수 있다 - 노드 a 와 노드 d 가 이미 같은 그래프에 속하는데, 두 노드를 연결한다면 사이클이 발생한다!! - 따라서 두 노드가 같은 그래프에 속하는지 확인하기 위해 union-find 알고리즘을 사용한다 합집합 찾기(union find) - 서로소 집합 혹은..
![thumbnail](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbGXHIF%2FbtrNzKiDUQ3%2FkjHiqH3YsRwyZWsQPhI4Kk%2Fimg.png)
[백준/약점체크] 1916번: 최소비용 구하기
2022. 10. 3. 23:50
컴퓨터/코딩테스트
[문제] [내 코드] N = int(input()) # 도시의 개수 M = int(input()) # 버스의 개수 # 버스의 출발도시, 도착도시, 비용 graph = {} for n in range(N): graph[n+1] = {} for _ in range(M): a, d, c = map(int, input().split()) graph[a][d] = c start, end = map(int, input().split()) def bellman_ford(graph, start): dist = {} for node in range(1, N+1): dist[node] = float('inf') dist[start] = 0 # V-1 번 반복 for i in range(N-1): for node in gr..
![thumbnail](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2F7Jy6S%2FbtrNqt1zSYa%2FqiP2qVCDtaIkX2fnonoWK0%2Fimg.png)
노션 포트폴리오 리뉴얼
2022. 9. 30. 03:54
진로/취업
벼르고 벼르던.. 노션 포트폴리오 정리 이번에 큰맘 먹고 제대로 정리했다. 아직 빠진 내용이 많아서 채워 넣을 게 많지만.. 이전보다 훨씬 깔끔해진 것 같아서 뿌듯하다. 혹 노션으로 포트폴리오를 만들고자 하는 사람에게 도움이 될까 싶어 공유해본다. 노션 포트폴리오의 링크는 여기에 있다. https://www.notion.so/Yunsoo-Woo-1a6880d11298453eaf2a692b931386fd