전체 글

Big-O의 수학적 정의

g(n) 이 시간복잡도 O(f(n))을 가졌다는 것은 n이 상수 N 이상일 때 g(n)

이진 트리 반전(inverting binary tree)

크루스칼 알고리즘

한 줄 요약: disjoint set을 사용해 cost의 합이 최소가 되는 Minimum Spanning Tree(혹은 모든 노드를 연결한 덩어리)를 찾는 것. 선행 지식: 분리 집합(Disjoint Set)

언어 별 간략한 컴파일 과정

C, C++ .c/.cpp -> .obj -> .exe .obj와 .exe 모두 기계어이다. .obj -> .exe로 변환하는 과정에서 link(링킹)이 발생하는데, printf()같이 유저가 정의하지 않은 함수들을 다른 .obj파일에서 찾아와 기계어로 바꿔주는 과정이다. Java .java -> .class .class는 byte-code로 이루어져 있다. 즉 자바는 소스코드를 기계어로 바로 변환하는 게 아니라 byte-code로 먼저 변환한다. (byte code란 가상 컴퓨터(Virtual machine/VM)에서 실행되는 코드) 그 후 실행 플랫폼에 설치된 JVM에서 이 코드를 실행엔진(Execution Engine)에 넣고 인터프리터를 사용해 기계어로 변환한다. 더보기 이 과정에서 인터프리터 대..

트리 순회

인오더(Inorder) - 사진 참고 Left Root Right 프리오더(Preorder) - 트리의 루트 노드에서 DFS를 돌린 것과 유사 (단 항상 왼쪽노드를 먼저 선택) Root Left Right 포스트오더(Postorder) - 트리 좌하단부터 아래에서 위로 출력 가로 한줄씩 좌->우 방향으로 출력 Left Right Root

분리집합(DIsjoint set / Union find)

www.youtube.com/playlist?list=PLDV1Zeh2NRsBI1C-mR6ZhHTyfoEJWlxvq Union Find [Disjoint Set] Playlist Playlist of videos explaining the union find (disjoint set) data structure. www.youtube.com

4. 게임 속에 이야기를 녹여내는 방법 - 선택과 결과

이번 포스트에서는 "게임 속 스토리"에 대해 다뤄볼 생각입니다. 본격적인 내용을 다루기 전에, 게임에 있어 스토리란 그저 부가적인 요소에 불과하다고 바라보는 시각 또한 존재한다는 점을 짚고 넘어가고 싶습니다. "비디오 게임에게 스토리란, 포르노 영화에서의 스토리와 같다. 스토리가 있을 것이라고 짐작할 순 있지만, 크게 중요하지 않다." 라는 존 카멕의 말은 두고두고 회자될 정도로 수많은 논란을 불러일으킨 말이고, 해당 발언을 지지하는 측과 반대하는 측으로 나뉘어 공방을 벌이는 모습은 오늘날에도 심심치 않게 찾아볼 수 있습니다. 저는 개인적으로 게임에는 스토리가 굉장히 중요한 부분으로 작용할 수 있다고 생각합니다. 하지만 동시에 스토리가 긍정적인 효과를 줄 수 있는 게임들과 그렇지 않은 게임이 모두 존재한..

N-Queens

N-Queen 문제를 해결하는 아주 효율적인 풀이이다 #include #define MAX 15 using namespace std; int col[MAX]; int N, total = 0; bool check(int level) // level을 받는 이유: 매번 0~N까지 다 검사할 수도 있지만, 어차피 현재까지 채워진 부분만 검사하면 되므로 level까지만 검사한다. { for (int i = 0; i i이기 때문) return..

Tree LCA(Lowest Common Ancestor)

트리에서(이진 트리가 아니어도 된다) 두 노드가 주어졌을 때 두 노드의 공통 조상들 중 가장 깊이 자리잡고 있는 조상을 찾는다. 방법1. 루트에서부터 노드A, 노드B까지의 경로를 구한다. 이렇게 구한 두 경로를 대조하며 처음으로 경로가 달라지는 지점을 찾는다. 방법2. (권장) blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221282478466&parentCategoryNo=&categoryNo=128&viewDate=&isShowPopularPosts=true&from=search 42. 최소 공통 조상(Lowest Common Ancestor) 이번 시간에 공부할 내용은 최소 공통 조상(Lowest Common Ancestor)입니다. 최소 공통 조상이란 트리..

두 문자열의 LCS(Longest Common Subsequence)

두 문자열의 가장 큰 subsequence(부분수열)을 찾는다. ex. ABCABC, AABBCC -> ABC ex2. ABBCCA, BBCACA -> BBCC 더보기 (백준 9252) 참고: beginthread.tistory.com/142

위상 정렬 (topological sort)

A를 위해 B,C가 선행되어야 할 때 A,B,C를 위상정렬하면 B-C-A순 (혹은 C-B-A순)으로 정렬된다.

boj 1504

주의할 점: 경로 생성이 불가능할 떄 -1을 반환하게 만드는 과정(solve() 함수)이 생각보다 까다롭다. dist와 cost를 혼동하지 말자 - dist는 start에서 해당 노드까지의 거리로, 시작지점이 변하면 변하는 값이고, cost는 어떤 두 노드 사이의 거리로 프로그램 실행부터 종료까지 변하지 않는다. #include #include #include using namespace std; const int INF = 987654321; struct compNode { bool operator() (pair a, pair b) { return a.second > b.second; } }; int N, E; int n1, n2; // 지나야 하는 두 노드 int result = INF; vector..