KoreanFoodie's Study

기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다. 각 주제들은 GeeksForGeeks 의 Top 10 algorithms in Interview Questions 글에서 발췌하였습니다. Floyd-Warshall (플로이드 와샬 - 최단거리 쌍) 플로이드 와샬(Floyd-Warshall) 알고리즘은 주어진 그래프의 모든 정점들에 대한 최소거리를 구하는 알고리즘이다. 원리는 매우 간단한데, 시작지점 i, 도착지점 j 의 거리 쌍을 중간 경유지 k 를 지나는 모든 경우에 대해 계속 relaxation 해주면 된다. 따라서 시간 복잡도는 (O^3) 이 나오게 된다. #include #include #define V 4 #define INF1000000 i..

기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다. 각 주제들은 GeeksForGeeks 의 Top 10 algorithms in Interview Questions 글에서 발췌하였습니다. 다익스트라 (최단 경로 알고리즘) 다익스트라는 주어진 시작 지점에서 최단경로를 구하는 알고리즘으로, 양의 가중치 간선들로 이루어진 그래프일 경우에 한 지점에서 특정 지점까지의 최단경로를 구하는 알고리즘이다. Naive 하게 모든 정점들을 체크하며, 거리값을 relaxation 해주는 경우 시간 복잡도는 O(V^2) 가 나온다. (dijkstra_slow 함수로 구현) Priority_Queue 를 사용하여 최소 거리의 정점을 Heapify 해줄 경우, 시간 복잡도는 ..

기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다. 각 주제들은 GeeksForGeeks 의 Top 10 algorithms in Interview Questions 글에서 발췌하였습니다. DFS (Depth First Search) DFS 는 깊이 우선탐색으로, 깊이 자료구조 형을 사용하거나, 재귀적으로 방문 체크를 진행하며 구현하면 된다. 포인트는 map 을 이용하여 adjacency list 와 visited 를 처리한 방식이다. 구체적인 코드는 다음과 같다. #include #include #include #include #include class Graph { std::map g; std::map visited; public: void addE..

기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다. 각 주제들은 GeeksForGeeks 의 Top 10 algorithms in Interview Questions 글에서 발췌하였습니다. 문제 링크는 제목에 링크로 걸어두었습니다. BFS (Breadth First Search) BFS 는 넓이 우선탐색으로, 큐(Queue) 자료구조 형을 사용하여 방문 체크를 진행한다. 구체적인 코드는 다음과 같다. #include #include #include using namespace std; class Graph { int N; list* g; public: Graph(int n) : N(n) { g = new list[n]; } void addEdge(int..

모두의 코드를 참고하여 핵심 내용을 간추리고 있습니다. 자세한 내용은 모두의 코드의 씹어먹는 C++ 강좌를 참고해 주세요! 템플릿 클래스 인스턴스는 같은 타입일까? 템플릿 클래스로 만든 두 클래스에서 인자만 바꾼다면, 해당 인스턴스들은 같은 타입일까? 다음 코드를 보자. #include #include template class Array { T data[N]; public: Array() {} Array(T (&arr)[N]) { for (int i = 0; i < N; ++i) { data[i] = arr[i]; } } T* get_array() { return data; } int size() { return N; } void print_all() { for (int i = 0; i < N; ++i..

모두의 코드를 참고하여 핵심 내용을 간추리고 있습니다. 자세한 내용은 모두의 코드의 씹어먹는 C++ 강좌를 참고해 주세요! 가변 길이 템플릿 C++ 템플릿을 이용하면 파이썬처럼 임의의 갯수의 인자를 받는 함수를 구현할 수 있다. #include template void print(T arg) { std::cout

바야흐로 예약대란이다. 유명하고 맛있는 곳을 방문하기 위해서는 사전작업이 거의 필수가 된 시대가 열렸다. 물론 너무 장사가 잘 되서, 굳이 예약 따위 받지 않는 음식점들도 부지기수다. 그런 곳들은 추운 겨울날 롱패딩을 부여 잡으며 같이 온 친구나 연인들과 펭귄 놀이를 할 준비를 해야한다. 아버지는 자칭 미식가이기에 맛집을 찾아가시는 편이다. 포장도 자주 해 오시고. 자칭 미식가인 아버지. 하지만 내가 생각하기에, 아버지는 혼(混)식가에 가깝다. 뭐든지 비비고 섞어 드시니까. 전문 용어로 쓰까 묵는다고 하던가? 맛집의 세계는 냉혹하다. 잘되는 곳은 잘되고, 안되는 곳은 안되는 법. 너무나도 당연한 말이지만, 음식점의 경우 그 편차가 제법 크다. 바로 옆집에 붙어 있어도 문전성시를 이루는 집과, 파리만 날리..

모두의 코드를 참고하여 핵심 내용을 간추리고 있습니다. 자세한 내용은 모두의 코드의 씹어먹는 C++ 강좌를 참고해 주세요! C++ 템플릿 도입 아래와 같은 벡터 클래스를 만들었다고 하자. class Vector { int* data; int capacity; int length; public: Vector(int n) : data(new int[n]), capacity(n), length(0) {} void push_back(int input); void remove(int index); int size() { return length; } void print_data() { for (int i = 0; i < n; ++i) { std::cout

마음이 따뜻하다는 것을 어떻게 정의내리면 좋을까. 그냥, 온기를 오감으로 느끼듯 따스한 마음이라는 놈을 자연스럽게 받아들이면 안되는 걸까. 따뜻한 마음이라는 녀석의 정체를 꼬질꼬질하게 파고들어 결론을 내려야 직성이 풀리는 슬프디 슬픈 나의 성격이여. 어쩌면 나는 따뜻한 마음을 가지기에 이미 틀린 운명을 타고난 건 아닐까 싶기도 하다. 그러나 타고난 팔자 따위, 노력으로 극복할 수 있다고 믿는 나이기에 아직 일말의 희망은 남아 있지 않을까. 사람은 변한다. 이전 글에서도 그 주제를 다룬 적이 있고 앞으로도 사람이 변한다는 나의 생각은 바뀌지 않을 것이다. 사람은 끊임없이 변한다. 물론 변모하는 생김새는 각기 다르다. 마치 먹구름에서 뛰쳐나온 빗방울이 서로 다른 무늬의 결정을 이루듯이. 그렇다면 나는 어떨까..

모두의 코드를 참고하여 핵심 내용을 간추리고 있습니다. 자세한 내용은 모두의 코드의 씹어먹는 C++ 강좌를 참고해 주세요! fstream 파일 스트림클래스 fstream을 상속받아 istream과 ostream을 입출력 클래스로 사용하자. std::ifstream in("test.txt"); std::string s; if (in.is_open()) { in >> s; std::cout