[GeeksForGeeks] Detect cycle using DFS
·
Algorithm/Algorithm (문제풀이)
🔒 문제 Detect cycle in an undirected graph | Practice | GeeksforGeeks practice.geeksforgeeks.org 💭 생각의 흐름 일단 문제 자체에서 DFS를 사용하여 사이클을 탐색하라고 했다. 정석적인 DFS recursive function을 작성하고 사이클 생기는 시점에 true만 리턴하면 된다고 생각했다. Q. 사이클이 생기는 시점이 언제인가? A. BackEdge (부모노드 이외의 노드에 연결되는 선이 발견되는 시점) 따라서 visited (방문 기록) 배열을 두고 visited 상에 방문된 상태로 기록되있으면서 parent 노드가 아닌 노드로 연결되있을 경우 바로 true (사이클이 존재)를 리턴하도록 한다. ⚠️ 실수 아래 그림 처럼 그..
[Programmers] 전화번호 목록
·
Algorithm/Algorithm (문제풀이)
문제 해결 방법 (1) 접두어 -> 길이가 짧을 수록 접두어 Matching 될 확률이 증가함 -> Sort 아이디어 떠올림. (2) 이중 For loop 반드시 첫자리 원소가 접두어인 것이 아니라 모든 원소가 서로 접두어 관계를 갖지 않는지 확인해야할 필요가 있음. 실수 (1) break break문은 하나의 Loop 만을 탈출한다는 사실을 망각하고 다음과 같이 작성했었다. 이중 for loop 안에서의 break은 2번째 loop은 탈출하지 못한다. 물론 정답을 도출해 내는데는 영향을 미치지 않지만 Time Complexity 증가의 원인이 된다. (2) compare 오름차순 정렬을 전화번호의 '길이'를 기준으로 시도하기 위해 compare 함수를 다음과 같이 작성했었다. 근데 요놈이 효율성 검사에..
[Clion] 한글 깨짐 (UTF-8) windows-949
·
C/Error
Cmakelist.txt 파일에 다음 구문을 추가해야함 set(CMAKE_CXX_FLAGS "-fexec-charset=CP949")
[C++] std::array
·
C/C++
C style array int arr[size] = { 1, 2, 4, 6, 10} C++ 11 std::array = {1, 2, 4, 6, 10} 대체 std::array 얘 왜쓰냐고? C style쓰면 배열 사이즈를 sizeof(arr) / sizeof(int) 등 하드코딩해서 구해준 상태로 함수 호출시 넘겨줘야했음. std::array는 standard template을 따르기 때문에 Iterator, parameter as reference , algorithm container, range-based for loop 등이 적용 가능함. + parameter로 넘어갈 때 포인터로 자동 형변환 되지 않음. (보통 const reference로 받음) [Reference] http://www.cp..
[C++] Lambda Function
·
C/C++
What's Lambda? Lambda is Function Object When to use? 한번 쓰고 말 간단한 함수 ex) sort compare , set || priority queue costructor comporator 클로저 기법을 통한 Function Object 생성 #include using namespace std; class LambdaTest { private: int localVariable; public: // this is closure explicit LambdaTest(int a) : localVariable{a} {}; int LambdaTest::operator()(int x) const { // function object return return localVa..
[C++ 11] NULL vs nullptr
·
C/C++
흔히 IDE에서 free 할때나 포인터에 NULL 값을 넣을 때 자주 쓰는 'NULL' NULL의 원형을 살펴보면 다음과같다. 이놈은 2가지 경우에서 흔히 문제가 발생. any_function(NULL) switch _ case 에서 switch(NULL) 1번의 경우 argument를 int 0으로 인식하고 2번의 경우도 switch(0) 을 받게된다. NULL이 0으로 define 되어있는 것이 그 원인이다. (ambiguous) 이를 해결하기 위해 나온 C++11 의 표준 'nullptr' 포인터 변수에 nullptr을 대입하자. any_ptr = nullptr => left_value(any_ptr)가 포인터 변수라는 것을 알 수 있어 가독성 증가 => switch case & argument 에..