KoreanFoodie's Study

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)을 읽으며 유용한 내용을 정리해 보도록 하겠습니다. 모든 내용을 요약하는 것은 아니며, 대회에 포커싱을 맞춘 부분은 다루지 않을 수도 있습니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다! 핵심 : 1. 수행 시간 어림짐작은 유용하지만, 엄밀하지는 않으니 최적화 시에는 여러 인자들을 함께 고려해 보자. 2. 알고리즘의 정당성 증명은 해당 알고리즘의 통찰을 이해함에 있어 중요하다. 3. 알고리즘의 정당성 증명 방법은 귀납법, 반복문 불변식, 귀류법, 비둘기집의 원리, 구성적 증명 등이 있다. *챕터 2 에서는 한 번 되짚어 볼 만한 내용을 일부 발췌해 정리해 보겠습니다. 수행 시간 어림짐작하기 일반적으로 우리는 Time..

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다! 핵심 : 1. 기본적으로는 이중 for-loop 으로 풀 수 있으나, DP 를 사용하면 시간을 조금 단축할 수 있다. 2. 소수점 오차에 유의하자. 록 페스티벌 (난이도: 하, 문제 ID : FESTIVAL) 사실 2중 for-loop 만 돌리면 쉽게 풀 수 있는 문제이긴 하다. 따라서 따로 설명을 길게 적지는 않고, 코드에 주석을 조금 달아 두었다! 😄 #include #include "stdlib.h" using namespace std; int N, L; int days[1000]; int dp[1000]; double ans; doub..

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)을 읽으며 유용한 내용을 정리해 보도록 하겠습니다. 모든 내용을 요약하는 것은 아니며, 대회에 포커싱을 맞춘 부분은 다루지 않을 수도 있습니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다! 핵심 : 1. 프로그래밍은 문제 해결이다. 2. 간결하고 모듈화된 코드를 짜라. 이는 버그를 줄여주고 디버깅 효율을 높여준다. 3. 자주 범하는 실수에 대한 유형을 알아두자. 프로그래밍은 문제 해결이다. 1장에서는 알고리즘에 대한 코딩에 대한 저자의 철학과, 앞으로 다룰 주제에 대한 간략한 맛보기(?)가 제공된다. 거기에 배운 지 오래되어 기억의 저편에 묻혀 있거나, 생각해보면 좋은 꿀팁들에 대해서도 조언을 아끼지 않는다. 이번 글..

코딩 테스트를 대비하여, 알아야 할 알고리즘 목록을 정리하며 읽어보면 좋을 블로그 링크들을 연결해 보았다(제가 작성한 것은 아님). 읽어봄직한 글들에 링크를 달은 것이니, 코테로 손을 예열하기 전에 두뇌를 예열하는데 사용하면 좋겠다! 🤣 기본 정렬 - 퀵소트 - 힙소트 - 머지소트 우선순위큐(힙) 이분탐색 DFS(깊이 우선 탐색) BFS(너비 우선 탐색) 백트래킹 그리디(탐욕법) 누적합 투포인터(두 포인터) 위상정렬 DP 심화 연결 성분 (Connected Component) 다익스트라 플로이드 와샬 벨만 포드 유니온-파인드 (Disjoint set) MST(최소 스패닝 트리) 프림 크루스칼 세그먼트 트리 트라이 이분 그래프(Bipartite Graph). KMP CS CS 기초 지식

기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다. 각 주제들은 GeeksForGeeks 의 Top 10 algorithms in Interview Questions 글에서 발췌하였습니다. 링크드 리스트 덧셈 (Add two numbers represented by linked lists) 링크드 리스트로 숫자가 주어졌을 때, 두 리스트를 더해 다음과 같은 리스트를 리턴하는 함수를 구현해 보자. 해당 함수는 재귀적으로 구현할 수도 있고, stack 을 이용해 구현할 수도 있다. 혹은, 링크드 리스트를 reverse 시킨 후, loop 을 돌려 덧셈을 해도 같은 결과를 구할 수 있다. 아래 코드는 링크드 리스트를 역전시킨 방식을 구현한 코드이다. #inc..

기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다. 각 주제들은 GeeksForGeeks 의 Top 10 algorithms in Interview Questions 글에서 발췌하였습니다. 링크드 리스트 스트링 비교 string 을 링크드 리스트로 표현했다고 했을때, 다음과 같이 스트링을 비교하는 함수를 구현해 보자. 단, 투 포인터를 이용하여 순회한다. #include #include #include struct Node { char data; Node* next; Node(char data) : data{data}, next{nullptr} {} }; struct List { List() : head{nullptr} {} void insert(cha..

기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다. 각 주제들은 GeeksForGeeks 의 Top 10 algorithms in Interview Questions 글에서 발췌하였습니다. 노드 삭제 (Linked List Node deletion) Singly Linked List 에서 노드를 삭제할 때는, 간단하게 이전 노드의 다음 노드를 현재 노드의 다음 노드와 연결시켜주기만 하면 된다(prev->next = cur->next). 혹은, prev 노드 하나를 이용해도 된다(prev->next = prev->next->next). void delete_node(int x) { if (!head) { std::cout data == x) { head ..

기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다. 각 주제들은 GeeksForGeeks 의 Top 10 algorithms in Interview Questions 글에서 발췌하였습니다. 링크드 리스트 정렬 삽입 (Linked List insert in sorted way) 정렬된 링크드 리스트에서, 삽입을 수행할 때 정렬된 상태를 유지하려면 어떻게 해야 할까? 1. 링크드 리스트가 비어 있을 경우 삽입되는 노드를 헤드로 만든다. 2. 원소가 하나일 경우, 삽입되는 노드를 헤드로 만들고 기존 헤드와 연결한다. 3. 원소가 여러 개일 경우, 순회를 하며 알맞은 위치에 끼워 넣는다. #include #include #include struct Node {..

기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다. 각 주제들은 GeeksForGeeks 의 Top 10 algorithms in Interview Questions 글에서 발췌하였습니다. 단절선 (Articulation Edge) 단절점과 단절선은 비슷한 원리로 구할 수 있다. DFS 를 통해 방문 노드의 순서와, 해당 노드를 포함한 자식 노드들에서 가장 먼저 방문한 노드의 순서(최저 방문 순서)를 저장한다. 그 후, 해당 노드의 최저 방문 가능 순서가 인접 노드의 방문 순서보다 클 경우(즉, DFS 방식으로 해당 노드를 방문하는 과정에서 다른 노드에서 해당 노드를 방문할 수 없는 경우) 해당 엣지는 단절선이라고 할 수 있다. 코드는 GeeksForG..

기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다. 각 주제들은 GeeksForGeeks 의 Top 10 algorithms in Interview Questions 글에서 발췌하였습니다. Boggle : Find all possible words in a board of characters 다음과 같은 보드가 있다고 가정했을때, Dictionary에서 우리가 원하는 단어를 보드를 통해 만들 수 있는지 없는지 확인하는 코드를 짜 보자. 인풋과 아웃풋은 다음과 같다. 제약 조건은, 보드에서 상하좌우 + 대각선 총 8가지 방향으로 이동할 수 있다는 것과, 보드 위의 문자를 중복해서 방문하는 것은 안된다는 것이다. 해당 함수는 DFS 방식으로 구현해야 한다...