Lemonlover🧘🏻‍♀️

어려운 코딩 테스트에서는 그래프 문제가 하나씩 출제 됩니다. 코딩 테스트 그래프 관련 문제라고 한다면, 아래 수준에서 나옵니다. 1. 최단거리 (플로이드 알고리즘 / 다익스트라 알고리즘) 2. 트리 3. 싸이클 찾기 4. 최소 스패닝 트리 이러한 문제를 푸는데 가장 먼저 해야할 것은 '노드와 노드를 엣지로 잇는 것' 입니다. 이것을 구현하는 방법에는 크게 두 가지가 존재합니다. 1. adjacent matrix 2. adjacent list 이 두 가지에 대해서 살펴볼 예정입니다. 그 전에 일반적으로 그래프의 두 가지 종류에 대해서 말씀드리겠습니다. 1. directed graph (방향 그래프) : 문제에서 주어진 그림에 화살표가 있거나, 문제 설명에 'a에서 b로만 갈 수 있다'라는 말이 있을 경우 ..

'재귀함수를 이용한 완전탐색의 기본에 대해서 (1)' 에서는 간단하게 숫자 조합을 고르는 방법에 대해서 알아 보았습니다. 사실 이것만 알면 그보다 좀 더 어려운 문제들 푸는 모든 준비는 끝났지만, 응용하는 방법을 알아보기로 합시다. https://www.acmicpc.net/problem/13302 13302번: 리조트 수영이는 여름방학을 맞이하여 많은 놀이 시설이 있는 KOI 리조트에 놀러가려고 한다. 리조트의 하루 이용권의 가격은 만원이다. 하지만 리조트의 규모는 상상을 초월하여 모든 시설을 충분히 즐기기 위해서는 하루로는 터무니없이 부족하다. 그래서 많은 이용객들은 3일 이상 연속으로 이용하기도 한다. KOI 리조트에서는 3일 연속 이용권을 할인된 가격 이만오천원에, 연속 5일권은 삼만칠천원에 판매..

https://stackoverflow.com/questions/9444714/how-is-quicksort-is-related-to-cache/9444866#9444866 How is quicksort is related to cache? I have seen many places say quicksort is good because it fits to cache-related stuff, such as said in wiki Additionally, quicksort's sequential and localized memory references work well with a ... stackoverflow.com 퀵 정렬은 in-place 정렬 입니다. in-place란 추가적인 공간을 요구하지 않..

1. what stable sort ? [출처 : https://www.geeksforgeeks.org/stability-in-sorting-algorithms/ ] stable sort란 무엇일까요? 아래 공들은 정렬이 된 상태입니다. 정렬되기 전과 비교했을 때 특징이 있습니다.그것은 공의 숫자는 정렬되었지만, 같은 숫자를 가진 공 사이에 색깔은 들어온 순서를 유지한다는 것입니다.이것이 바로 stable sort 의 개념! 입니다. (unstable sort 는? 그 반대겠죠. 그냥 막 섞입니다.) 2. why stable sort ? 그럼 이 stable sort가 왜 중요할까요? 예 ) 데이터가 들어온 순서는 유지하면서, 특정 key 값을 기준으로 sorting하고 싶을 때 그냥 아무생각 없이 so..

기본적인 sorting 알고리즘을 구현해 봤습니다. 설명은 링크를 따라가시면 굉장히 잘 되어있습니다.백준 수 정렬하기 문제를 여러가지 방식으로 풀어보면서 연습을 해봤습니다. 아래 코드는 모두 AC 받은 코드들입니다.코드는 C++로 되어 있구요. 나중에 혹시 면접 때 사용할 것을 생각하여 최대한 깔끔하게 작성해봤습니다. bucket sort / counting sort / radix sort 에 대해서는 sorting algorithm(advanced)에 작성하겠습니다. 아래 에니메이션은 각 algorithm이 어떻게 작동하는지 쉽게 알 수 있어서 공유해봅니다. [출처 : https://medium.com/@kamyarg/comparison-sorting-algorithms-and-mystery-of-nl..

종만북에서 나오지만요. '중복없이 몇 개 중에 몇 개를 선택하는 방법' 너무 중요하게 다루고 있죠.완전 탐색의 기본 중에 기본 어떤 상황에서 물어봐도 바로 나와야 할 대답입니다. 우선 간단한 for문으로 고르는 방법부터 알아보겠습니다. 123456for(int i = 0; i

오늘은 DP의 특별한 문제 형태라고 할 수 있는 LIS를 알아보겠습니다.보통의 DP로 풀게 되면 O(N^2)으로 풀게 됩니다. 하지만 N의 값이 커지면 O(NlogN)의 알고리즘이 필요합니다. 우선 LIS 문제 정의 부터 알아보겠습니다. The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. For example, the length of LIS for {10, 22, 9, 33, 21, 50, 41, 60, 80} is..

컴퓨터로 문제를 풀 때, 보통 그 문제는 탐색을 기반으로 합니다.문제가 정의하고 있는 '공간'을 탐색합니다. 상태를 논리적으로 정의할 수 없다면, 모든 공간을 커버한다는 보장이 없기 때문에해가 맞는 것인지 판별할 수 없습니다.그 다음 공간은 이전의 상태를 통해 발생하기 때문에, 트리처럼 공간이 뻗어 나갑니다. 그 공간을 방문하는 방법 중에 'BFS'와 'DFS'가 있습니다. 지금은 BFS(Breadth First Search)를 설명하려고 합니다. 영어 뜻 그대로 넓이 우선 탐색이다. 트리의 가지를 따라서 무작정 들어가지 않고, depth를 하나씩 늘려갑니다. 아래는 BFS와 DFS를 비교하는 그림입니다. 문제에 따라 어떤 방문 방법을 선택해야 정답을 빠르게 찾을 수 있을 것인지판단하고 적용해야 합니다...