거창한 시작

선택 정렬 - 앞에서부터 어떤 값을 넣을지 선택하는 알고리즘 동작 - 주어진 리스트 중에서 최소값/최대값을 선택 - 선택한 값을 정렬되지 않은 앞의 갑과 교체 - 위 과정 반복 * 예시 + 1번 : 탐색하여 최소값 1를 찾고, 첫 번째 값과 교환 + 2번 : 탐색하여 최소값 2를 찾고, 두 번째 값과 교환 + 3번 : 탐색하여 최소값 3을 찾고, 세 번째 값과 교환 + 이하 과정 동일 구현 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 void selectionSort(int *list, int n){ // 최소값 인덱스, 임시 변수 int idx_min, tmp; for(int i=0; i

최단 경로 문제 - 그래프 이론에서 두 정점을 잇는 가장 짧은 경로를 찾는 문제 문제 종류 - 단일-쌍 최단 경로 문제 : V에서 V'로 가는 경로들 중 최단 경로 찾기 - 단일-출발 최단 경로 문제 : V에서 출발하여 그래프 내의 모든 정점에 도착하는 최단 경로 찾기 - 단일-도착 최단 경로 문제 : 그래프 내의 모든 정점에서 출발하여 V에 도착하는 최단 경로 찾기 - 전체-쌍 최단 경로 문제 : 그래프 내의 모든 정점 사이의 최단 경로 찾기 알고리즘 종류 1) Dijkstra algorithm (다익스트라 알고리즘) - 그래프 이론에서 하나의 시작 정점에서 다른 모든 정점으로 가는 최단 경로를 찾는 알고리즘 - 동작 * 출발 노드 선택 * U노드로 이동할 때, 현재 이동해서 U까지 온 비용과 이전에 ..

21.12.2020에 쓰는 여행일지 어제 너무 많이 마셨었다. 약 1천 원에 2L 맥주를 마실 수 있어서 3병이나 사고 다 마셨었다. 아침 일찍 일어나서 아직 가보지 못한 곳을 다녀보려는 계획은 수포로 돌아갔다. 오전 내내 숙취 때문에 누워있었다. 오후에는 정신을 차려서 몰도바 국기를 찾아 나서기로 했다. 시내로 발걸음을 옮기니 시장 같은 풍경이 펼쳐졌다. 5일장 같은 느낌이었다. 나는 그곳에서 내가 찾는 몰도바 국기를 찾아다녔다. 몇몇 분들이 볼도바 국기를 팔았지만 마음에 들지 않았다. 그중에 가장 마음에 들었던 국기는 아래의 국기이다. 마감질이 완벽하게 되었있어서 질적인 측면에서 최고였다. 그런데 가격을 4천원 불러주셨다. 나는 고민했었다. 4천원...? 루마니아와 불가리아에서도 3천원 이하로 샀는데..

어제는 피곤했기 때문에 하지 못한 도시 투어를 해보기로 했다. ​ 어제는 정신 없어서 찍지 못한 카운터를 찍어보았다. 잘 보시면 한국 이미지가 그려져 있다. 유독 한국 그림이랑 한국 글씨가 크게 보인다. 남산, 태극기, 63빌딩, 한복, 그리고 심지어 수렵도에 나오는 고구려 병사도 보인다... 주인이 그린 건 아니고 손님중에 누가 그리고 갔다고 한다. 한 번 만나보고 싶다. 엄청... 잘 그리셨네요. ​ ​ ​ ​ 어제 크리스티나가 준 지도를 따라서 천천히 도시를 걸어보기로 했다. 도시라기 보다는... 시내? 로타리? 현재 내가 가고 있는 곳은 수도 키시나우 쪽에서 가장 큰 공원이었다. 불가리에서 부터 쭉 느껴온 느낌이 아직도 남아있다. 사진을 보고 있으면 느껴지는 회색 빛의... 탁함... ​ ​ 키시..

몰도바에 도착했다! 이전 포스팅에서 말했듯이 엉덩이는 박살이었다. 아무리 좋은 버스를 타도 야간이면 내 엉덩이가 버티질 못했다... 목배게를 엉덩이에 양보하기까지 했으니...(엉덩이에 깔고 있었다.) ​ 예상 도착시각은 7시 였던 걸로 기억한다. 그래서 도착하면 호스텔로 가서 짐정리하고 이래저리 하면 되겠구나 싶었다. 그런데 도착하니 5시30분? 세상에 빠르면 참 좋은 것이 많다. 인터넷이 빠르면 좋다. 지하철이 예상시간 보다 빨리 도착하면 좋다. 음식이 빨리 나오면 좋다. 그런데 세상에 빠르면 좋지 않은 것이 여기 하나 있다. 새벽 버스는 빨리 도착하면 좋지 않다. 호스텔은 닫거나 교통은... ㅠㅠ 비까지 온다. 이때, 내 심정이 내린 사람들 중 아무나 잡고 '나좀 데려가면 안되?' 라고 호소하고 싶었..

오늘은 몰도바로 떠나기로 했다. 몰도바? 몰드브에서 모히또 한 잔은... 아닐 테고. 몰도바는 어느 나라일까? 구글링을 해보면 유럽 최빈국으로 나온다. 첫인상 부터 이렇게 시작하다니 편견없이 가보자. ​ 그럼 아침은 간단하게 먹었다. 안에 슈큐륌이 들오있는 뽱~ 아이 달콤해서 혀가 다 꼬였당~ ㅎㅎㅎ ​ ​ 나는 돌아다니는 국가 마다 국기를 모으고 있다. 이왕이면 완전 original로 구한다. 그런데 루마니아에는 완전 오리지널이 없었다. ㅠㅠ 곧 차 시간이 다가오는데... 국기는 찾아야 하는데... 그러다가 문구점 같은 곳에서 국기 색으로 매듭을 위한 리본 같은 것을 팔고 있었다. 그것을 사서 국기 비율로 해서 가방에 붙이기로 했다. 그리고 친절한 아주머니랑 함께 사진 찰칵! (실은 이 가게에서 사지 ..

당일 치기로 다녀오 계획이라서 아침일찍 호스텔에서 나왔다. 부쿠레슈티 노드(버스정류장)에서 8시22분 기차를 타고 bransov로 11:00에 도착한다. 가격은 48.60Lei. 할인을 받으려고 시도해봤지만, 현지 학생들만 할인이 된다고 역무원이 말해주었다. ​ 출발하기 전에 신이난 김.정.환... 밝아서 좋네... ​ ​ 아침 일찍 일어났지만 아침밥은 먹지 못했다. 눈물... ㅠㅠ 기차를 타기 전에 편의점에서 몇 개의 초코바를 샀었다. 그리고 그 모습을 보고 있던, 옆자리의 아주머니께서 미숫가루 같은 것을 주셨다. 음... 설명하자면, 엄청 많은 곡물들을 갈아서 (몇 가지는 다 갈리지 않아 씹을 수 있었다.) 물에 타먹는 것이었다. 엄첨 걸죽했고, 곡물 맛의 담백함이 폭발했다. 딱히 맛있다고 할... ..

신장 트리 (Spanning Tree) - 그래프 내의 모든 정점을 연결하는 트리 - 사이클은 없음 - N개의 정점과 N-1개의 간선 - 왼쪽 그래프는 오른쪽의 총 8개의 신장 트리를 가짐 최소 신장 트리 (Minimum Spanning Tree) - 신장 트리 중에서 간선들의 가중치 합이 최소인 트리 - 아래 그래프에서 굵은 간선으로 이루어진 트리가 최소 신장 트리 최소 신장 트리 알고리즘 - 최소 신장 트리를 찾을 수 있는 알고리즘 1) 크루스칼 알고리즘 (Kruskal's algorithm) - 탐욕적인 방법을 이용하여 모든 정점을 최소 비용으로 연결하는 방법 - 간선 선택 기반 - 동작 * 간선들을 가중치 오름차순으로 정렬 * 가중치가 작은 간선을 순서대로 선택하여 사이클을 이루는지 확인 * 사이..

Union(X, Y) 연산 - 서로 중복되지 않는 두 개의 집합을 병합 - X가 속한 집합(부모)에 Y가 속한 집합(부모)을 병합 Find(X) 연산 - 하나의 원소가 어떤 집합(부모)에 속해있는지를 반환 - X가 속한 집합(부모)을 찾아 반환 동작 구현 - 배열로 구현 * Union(X, Y) 연산에서 모든 원소를 순회하면서 Y가 속한 집합 번호를 X가 속한 집합 번호로 변경 * Union(X, Y)의 시간복잡도 O(n) * Find(X) 연산에서 한 번에 X가 속한 집합을 찾음 * Find(X)의 시간 복잡도 O(1) - 트리로 구현 * Union(X, Y) 연산에서 X가 속한 집합의 자손으로 Y가 속한 집합을 붙임 * Union(X, Y)의 시간복잡도 O(logN) * Find(X) 연산에서 트리를..

Graph - 노드와 간선으로 구성된 자료구조 - 객체 간의 관계를 표현하는 자료구조 - root와 부모-자식 관계가 없음 - 트리는 그래프의 부분집합 - 네트워크 모델 용어 표현 - 정점(vertex) : 객체. 노드 - 간선(edge) : 객체를 연결하는 선. 노드를 연결하는 선 - 인접 정점 : A 정점에서 간선으로 연결된 다른 정점 - 진입 차수 : 방향 그래프에서 A 정점으로 들어오는 간선의 수 - 진출 차수 : 방향 그래프에서 A 정점에서 나가는 간선의 수 - 단순 경로 : 경로 중에 반복되는 정점이 없는 경로. 같은 간선을 포함하지 않는 경로 - 사이클(cycle) : 단순 경로의 시작 정점과 종료 정점이 동일한 경우 그래프의 종류 1) 무방향 그래프 - 간선을 통해서 양방향으로 이동 - (..