소오설 소오설

DFS는 Depth-First Search의 약자로 어떤 그래프가 있을 때, 임의의 한 정점[Vertex, Node]에서부터 시작하여 순회를 함에 있어서 한 노드의 끝까지 갔다가 Backtracking을 하는 알고리즘입니다. 그렇다면 BFS라고 불리는 Breadth-First Search는 어떠한 알고리즘일까요? 이는 Queue을 이용하여 문제를 푸는데 많은 도움을 줍니다. 저는 왜 Queue을 써야하는지 왜 그런 식으로 코드를 짜서 문제를 푸는지 이해하는데 많은 어려움을 겪었습니다. 일단 Queue자체는 Insertions(push)과 Deletions(pull or pop)이 상수 시간 내에 동작한다는 특징을 갖고 있습니다. 그렇기 때문에 어떤 연결된 그래프, Spanning Tree을 순회하기 위해..

DFS, BFS은 응용하기 참 까다롭습니다. 왜 Queue을 사용하는지, 왜 Stack인지, 왜 재귀인지 받아들이는 것이 어렵습니다. Graph Theory에서 배우는 간단한 용어를 알고 있으면 좋습니다. 어떤 식으로 BFS와 DFS의 논리가 작동하는지 뼈대를 알아야 응용함에 있어서 어려움을 최소화 할 수 있다고 믿습니다. The number of edges 일반적으로 간단한 그래프[Simple Graph]는 임의의 정점[Vertex, Node]의 집합과 엣지[Edge]들의 집합으로 구성되어 있습니다. 그리고 그래프는 다시 크게 Directed Graph와 Undirected Graph로 나눌 수 있습니다. 이름이 직관적으로 설명하는 것처럼 전자는 정점과 정점 사이에 방향이 존재하지만 후자는 그렇지 않습..

table에 있는 조각들을 game_board의 빈 칸에 채워 넣으면 되는 문제입니다. 제한 조건들이 있습니다. 정리해보면 1. 연속된 빈 칸에는 딱 맞는 조각만 채워 넣을 수 있으며 2. 좌우 대칭으로 조각을 바꾸는 것은 금지입니다. 3. table의 조각을 회전하여 game_board의 빈 칸에 맞출 수 있으면 인정입니다. 반환 값은 가장 많이 채워 넣은 빈 칸의 개수입니다. 더 얻어볼 수 있는 정보는 테이블은 모두 정방형 격자 모양이라는 사실과 0이 있으면 빈 칸, 1이 있으면 비어있지 않은 칸이라는 점입니다. C++을 사용하기 때문에 테이블의 상태는 이차원 벡터의 형태로 주어졌습니다. 또 한 가지 문제를 풀 때 늘 유념하는 것이 있는데 문제의 풀이가 복잡해지고 컨테이너 안에 또 다른 컨테이너가 있..

딱 떠오르는 건 재귀함수 정도입니다. 그러나 많은 시간을 요구하니 다른 방법으로 풀어보라고 합니다. 우선 눈에 보이는 특징은 모든 parameter의 변위가 1이 최대라는 점입니다. 그리고 입력 값이 20보다 크면 20으로 줄여주는 친절함도 눈에 보입니다. 그나저나 왜 w(15, 15, 15)를 매우 오랜 시간이 걸리는 예로 들어준 걸까요? 적어보면 다음과 같은 과정이 포함됩니다. w(15, 15, 15) = w(14, 15, 15) + w(14, 14, 15) + w(14, 15, 14) - w(14, 14, 14) 세 값이 하나라도 다르다면 둘 중 먼저 종결조건에 도달하는 경우가 생기지만 모두 같은 값이라면 셋이 동시에 종결조건에 이르러야 하기 때문에 긴 시간이 걸린다는 뜻이었습니다. 그런데 w(14..

f(0) = 1, f(1) = 1을 반환합니다. 먼저 ( x , y ) 를 x = 0의 출현, y = 1의 출현을 맵핑한 notation으로 쓰겠습니다. 예시에서 f(3) = f(2) + f(1) = { f(1) + f(0) } + f(1) = 1 + 0 + 1 -> (1, 2) 그렇다면 f(4) = f(3) + f(2) = { f(2) + f (1) } + { f(1) + f(0) }= [ { f(1) + f(0) } + f(1) ] + { f(1) + f(0) } = 1 + 0 + 1 + 1 + 0 -> ( 2, 3 ) 직감적으로 피보나치 수를 계산하라는 느낌이 옵니다. 그러나 그림을 통해 조금 더 확신을 갖고 어떤 점에서 동적 계획법을 활용하면 좋은지 확인해보는 것도 좋습니다. f(2)의 결과값이 ..

Combination까지는 문제가 없었는데 각 팀원간 시너지를 계산하는데서 어이없이 허둥댔다. 원래 사용한 방법은 그러나 Team Start를 나타내기로 했던 Com vector에 예를 들어 { 0, 3, 4, 7 } 이 들어있다면 _max - 1 - i로 Team Link를 표현할 경우 Team Link는 { 7, 4, 3, 0 } 이 들어있게 된다. 1, 2, 5, 6은 등장하지도 않는다. 따라서 Com vector를 따로 사용하지말고 member vector가 true or false로 선택되었는지 아닌지를 기록한다는 점을 활용해서 푸는 것이 훨씬 낫다.

어디서 메모리를 낭비한 걸까? 공부가 부족하다

여러 가지 방법을 시도해서 같은 결과를 뽑았는데 이것만 맞다고 처리해주었다.