콜드플레이 콘서트...? 어느날 친한 친구가 콜드플레이 콘서트 티켓이 몇 장 생겼는데 한 번 가보지 않겠냐고 물어봤다.나는 콜드플레이 노래를 몇 개 알긴 해도 팬은 아니여서 조금 망설여졌다. 그런데 친구가 틀어주는 콜드플레이 노래들을 들어보니 익숙한 노래가 많았고가보면 재밌을 것 같다는 생각이 들어 가게 되었다. 실제로 어릴 때부터 "A Sky Full of Stars"라는 노래를 좋아했었으니, 그 노래를 듣기 위해서라도 한 번 쯤 가보고 싶었다. 콘서트 예습 콘서트를 제대로 즐기고 싶어서 유튜브에 뜨는 콘서트 예습 영상도 열심히 시청했다(저 영상 도움이 많이 됐다)콘서트 가기전에 노래를 들어보는데 익숙한 노래도 많고 가기전부터 신나는 기분이 들었다. 스탠딩 석 자리는 스탠딩석 입장번호 10000번..
테마소개 신촌 나의 신방에 나름 신상 테마인 "한나는 해고됐어" 방탈출을 하고왔다. 큰 기대는 하지 않았는데 생각보다 더 재밌었다! 장르 : 스릴러시간 : 70분공식 난이도 : ★ ★ ★체감 난이도 : ★ ★ ★ ★가격 : 27000원 스토리한나, 당신은 유능한 팀장이에요. 모두 당신처럼만 한다면 얼마나 좋을까요? 인테리어스케일이 엄청 크지는 않은데, 구성을 잘해놓아서 크게 느껴진다! 인테리어도 마지막 방에서 엄청 몰입되게 잘해놓아서 좋았다. 생각한것보다 퀄리티가 좋았다. 공포도공식 홈페이지 공포도는 0.5 라고 표시되어있는데, 생각보다 스토리나 연출이 기괴해서 쫄들은 무서울수도 있다. 인원우리는 총 4명이서 진행했는데 크게 무리는 없었다.다만, 여기는 혼방이 물리적으로 불가하고 추천인원은 2~3인이다...
프림 알고리즘(Prim`s Algorithm)이란?프림 알고리즘은 크루스칼 알고리즘과 더불어 최소 신장 트리를 찾는 대표적인 알고리즘 중 하나이다. 크루스칼 알고리즘과 최소 신장 트리에 대해 잘 모른다면 이전 게시물을 보고 오자. [알고리즘] 크루스칼 알고리즘(Kruskal Algorithm)이란? 크루스칼 알고리즘 C++ 구현, 최소 신장 트리(Mi최소 신장 트리(Minimum Spanning Tree)란?크루스칼 알고리즘에 대해 알아보기 위해선 우선 최소 신장 트리에 대해 알아야 한다.[caption id="attachment_414" align="alignnone" width="798"][그림1] 우선, 신장 트리(Spancode-lab1.tistory.com 프림 알고리즘 과정프림 알고리즘의 ..
최소 신장 트리(Minimum Spanning Tree)란?크루스칼 알고리즘에 대해 알아보기 위해선 우선 최소 신장 트리에 대해 알아야 한다.[caption id="attachment_414" align="alignnone" width="798"][그림1] 우선, 신장 트리(Spanning Tree)란 무방향(Undirected) 그래프의 최소 연결 부분 그래프이다. 좀 더 쉽게 설명하자면 N개의 정점을 가지는 그래프 중 최소 간선의 수인 N-1개의 간선으로 연결된 그래프를 뜻한다. N개의 정점이 N-1개의 간선으로 연결되어 있으면 이것은 필연적으로 트리 형태를 이루게 되기 때문에 신장 트리라고 불린다. [그림 1]을 보면 5개의 정점을 가진 그래프를 4개의 간선만을 사용해 연결하면 신장 트리가 되는 것..
벨만 포드 알고리즘(Bellman-Ford Algorithm)벨만 포드 알고리즘은 그래프 상에서 최단경로를 찾는 알고리즘이다. 최단경로를 찾는 다른 알고리즘인 다익스트라(Dijkstra)알고리즘과 다른 점은 간선의 가중치가 음수여도 가능하다는 점이다. 다만 다익스트라보다 수행시간이 더 오래걸린다는 단점이 있다.따라서 간선의 가중치에 음수가 없다면 다익스트라를, 음수가 있다면 벨만 포드를 사용하는게 일반적으로 좋다. 다익스트라 알고리즘에 대해 알고싶다면 다음 포스팅을 참고하자. [알고리즘] 다익스트라(Dijkstra) 알고리즘이란? 다익스트라 c++ 구현다익스트라(Dijkstra) 알고리즘이란?다익스트라 알고리즘은 그래프 상에서 시작 정점부터 나머지 각 정점까지의 최단거리를 계산하는 알고리즘이다.다익스트..
다익스트라(Dijkstra) 알고리즘이란?다익스트라 알고리즘은 그래프 상에서 시작 정점부터 나머지 각 정점까지의 최단거리를 계산하는 알고리즘이다.다익스트라 알고리즘은 그래프의 어느 간선의 가중치라도 음수가 있으면 안된다. (벨만-포드 알고리즘은 음수도 가능) 다익스트라 알고리즘을 구현하기 위해서는 다음과 같은 과정을 반복하면 된다. 1. 방문하지 않은 정점 중 가장 가중치 값이 작은 정점을 방문한다. (처음엔 시작 정점 방문)2. 해당 정점을 거쳐서 갈 수 있는 정점의 거리가 이전에 기록한 값보다 작다면 그 거리를 갱신한다. 이해가 잘 가지 않는다면 아래 예시를 보면 이해가 빠를 것이다. 위와 같은 그래프가 있다고 하자. 시작정점은 0번 정점이라고 가정하고 나머지 정점까지의 최단거리를 계산해보자.1차원 ..
백트래킹이란?백트래킹(Backtracking) 은 해를 찾는 도중 해가 아니어서 막힌다면, 되돌아가서 다시 해를 찾아가는 기법이다.해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않다면 그 경로를 더이상 가지 않고 되돌아간다. 이것을 가지치기(Pruning) 이라고 한다.즉, 백트래킹은 모든 가능한 경우의 수 중에서 특정 조건을 만족하는 경우만 살펴보는 것이다.해가 될 가능성이 있다면 유망하다(promising)고 한다.N-Queen 문제N-Queen 문제는 N X N 크기의 체스판에 N개의 퀸(Queen)을 서로 공격할 수 없도록 배치하는 문제이다. 이 때 퀸은 상하좌우, 대각선 방향으로 체스판의 끝까지 공격을 할 수 있다. 따라서 아래 그림처럼 직선, 대각선 상에는 퀸을 배치 할 수 없다.N-Q..
너비 우선 탐색, BFS 란?BFS는 그래프 탐색 방법 중 하나로 임의의 시작 정점에서부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.주로 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다.BFS는 큐(Queue) 자료구조를 이용해 구현한다. 큐 자료구조에 대해 알고싶다면 다음 포스팅 참고 [자료구조] 큐(Queue)란? , 큐 C언어 구현큐(Queue) 란?큐는 컴퓨터의 기본적인 자료구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 형식을 말한다. 나중에 집어 넣은 데이터가 먼저 나오는 스code-lab1.tistory.com BFS의 과정BFS 는 다음과 같은 과정을 거치게 ..
DFS란?DFS 는 Depth First Search 의 줄임말로 깊이 우선 탐색이라는 뜻이다. DFS는 보통 트리 혹은 그래프 탐색에서 사용되는 알고리즘으로 깊이를 우선하여 목표노드를 찾는 탐색법을 뜻한다.DFS는 특정 노드에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완전히 탐색하는 방법이다. DFS 예시위와 같은 트리 구조가 있다고 하자. 이 때 DFS 는 다음의 과정을 거치게 된다.가장 먼저 루트노드인 A를 방문하고, 스택에 추가한다.이후 스택의 top 부분에 있는 A의 인접 노드인 B노드를 방문하고, 스택에 B노드를 추가한다. (C노드를 먼저 방문해도 된다. 순서는 상관 없다)이후 스택의 top부분에 있는 B의 인접 노드인 D노드를 방문하고, 스택에 D노드를 추가한다.이후 스택의 top 부..
피보나치 수열피보나치수열은 제2항 까지는 1, 제3항부터는 바로 앞의 두 항을 더한 수가 반복되는 수열이다.1, 1, 2, 3, 5, 8, 13, 21, 34, 55...이러한 피보나치수열을 구현할 때는 보통 재귀를 통해 표현하게 된다. c언어에서는 아래와 같이 구현 할 수 있다.int fibo(int n){ if (n 이렇게 재귀를 통해 피보나치 수열을 구하게 되면 중복 연산이 많아져 매우 비효율적이다. 예를 들어 fibo(5)를 구한다고 하자.fibo(5)를 구할 때 위와 같은 과정을 거쳐 구하게 된다. 그림을 보면 fibo(1), fibo(2), fibo(3) 연산이 중복되는 것을 볼 수 있다. 만약 fibo(1), fibo(2), fibo(3) 연산의 값을 어딘가에 저장해 놓는다면, 중복해서..
퀵 정렬(Quick Sort)퀵정렬은 합병정렬과 비슷하게 분할정복(Divide and Conquer) 알고리즘이다. 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법으로 다음과 같은 과정을 거친다.1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 pivot(피벗) 이라고 한다.2. pivot을 기준으로 pivot보다 작은 요소들은 모두 pivot의 왼쪽으로 옮기고 pivot보다 큰 요소들은 모두 pivot의 오른쪽으로 옮긴다.3. pivot을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.3-1) 분할된 왼쪽 리스트와 오른쪽 리스트도 다시 pivot을 정하고 pivot을 기준으로 2개의 부분리스트로 나눈다.3-2) 재귀를 사용하여 부분 리스트들이 더이상 분할이 불가능 할 때까지 반..
삽입 정렬(Insertion Sort)삽입정렬은 두 번째 원소부터 시작하여 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다.위와 같은 배열을 오름차순으로 정렬한다고 하자.두 번째 원소인 5부터 시작하여 그 앞의 원소들과 비교를 시작한다.5와 7을 비교해 5가 더 작으므로 7을 한 칸 뒤로 옮기고 그자리에 5를 삽입한다.세 번째 원소인 1과 그 앞의 원소 7을 비교해 1이 더 작으므로 7을 한 칸 뒤로 민다.그 앞의 원소 5와 1을 비교해 1이 더작으므로 5를 한 칸 뒤로 밀고 1을 그 자리에 삽입한다.네 번째 원소인 4와 그 앞의 원소 7을 비교해 4가 더 작으므로 7을 한 칸 뒤로 민다.그 앞의 원소 5와 4를 비교해 4가 더..
