소오설 소오설

너무 단순하게 푼 것 같기도 합니다. 그냥 문제가 요구하는 대로 움직일 숫자들을 쭉 컨테이너에 담고 나서 한 칸씩 밀어서 다시 주어진 행렬의 값을 바꿨습니다. Elapsed time : 30min 다른 사람들 풀이를 참조 했는데 거의 비슷한 논리대로 푼 것 같기는 합니다.

정렬을 해서 값이 변화할 때마다 체크해선 풀 수 없습니다. { 5, 3 } 은 가장 긴 증가하는 부분 수열이 { 5 }, { 3 } 뿐인데 정렬을 하면 { 3, 5 } 가 되고 가장 긴 증가하는 부분 수열의 크기가 2가 되어 오답이 됩니다. 입력으로 받은 전체 수열을 Iterate하는 것은 같습니다. { 9, 10, 11, 1, 2, 3, 4, 5 }가 있다면 iter = 9부터 iter = 5까지 검증을 할 것입니다. Elapsed time : 12min 백준은 대체로 기본을 다지는데 유용한 것 같습니다. dp을 어디에 활용하면 좋을지 고민을 많이 한 문제인데 정답을 찾는 것 조차 dp을 활용합니다.

Permutation으로 금방 풀긴 했는데 또 시간 초과에서 걸려버렸습니다. 어차피 8명을 모두 세워야 하기 때문에 8명을 서로 다른 방법으로 세우고 나서 조건을 검사했습니다. 8!이라는 워낙 많은 케이스를 검증해야 하기 때문에 시간을 많이 잡아 먹는 것은 감안했지만 추측하기를 Satisfy함수에서 귀여운 Friends의 Index을 찾는 과정이 문제일 거라 생각했습니다. 그런데 그게 아니고 offset을 integer로 변환하는 과정이 문제였습니다. 그냥 char을 int로 cast해서 풀면 시간 초과를 해결할 수는 있었습니다. 아래의 코드 몇 줄이 시간 초과의 원인이라는 게 참 웃깁니다. figure 1a의 코드를 다음과 같이 바꾸니 성공은 합니다. 무려 6초나 걸려서 다른 사람들도 그런가 확인을 좀..

Elpased time : 32min BFS, DFS의 구조, 응용을 익히고 Vertices의 개수를 세거나 영역을 구하는 등 몇 가지 유형이 정해진 경우가 종종 있다고 생각합니다. 마땅히 C++의 어떤 STL을 응용한 것은 없습니다.

Elapsed time : 120min 시간 초과를 해결 할 수가 없었습니다. 완전히 다른 방법 사용한 방법 1. 문자열을 Delimiter로 분리하기

사용한 기술 1. 문자열 나누기 string::substr - C++ Reference (cplusplus.com) parameter로 일반적으로 두 개를 받습니다. std::string::substr ( begin , count ) 어떤 string의 begin index부터 count개의 문자를 std::string의 형태로 반환합니다. 2. for loop을 적당히 돌려서 원하는 Index에 접근하기 3. std::stringstream integer을 string으로 만들어서 새로운 string을 만들기 위해 사용했습니다. Elapsed time : 58min 문제점 for loop을 돌 때, 현재 검증하는 값을 iter로 두고 다음 index의 값과 비교하고 나서 새로운 string new_st..

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로 나눌 수 있습니다. 이름이 직관적으로 설명하는 것처럼 전자는 정점과 정점 사이에 방향이 존재하지만 후자는 그렇지 않습..