kark's

일반적인 Queue 같은경우 FIFO(First In First Out) 구조로 먼저 들어가 있던 데이터가 가장먼저 반환되는 자료구조이다. Priority Queue는 먼저 들어가있는 순서는 상관없이 우선순위가 가장 높은것 먼저 배출되는 자료구조이다. 예시는 낮은수가 우선순위가 높다고 가정한다. 내부 원리를 이해해보자. 우선순위 큐는 이진트리 형식으로 구성되어있으며, 이 트리 구조를 활용해 빠르게 우선순위를 쉽게 확인할수 있다. Enqueue 우선순위 큐에 2, 4, 3 의 데이터 3개가 들어있고 새로운 데이터 1을 삽입하는 과정 위처럼 이진트리의 순서대로 맨 마지막 자리에 전달받은 요소를 추가시켜준다. 이후 자신의 부모 노드보다 우선순위가 높다면 자리를 교체해주며 트리의 Head까지 과정을 반복해주면 ..

백트레킹은 시도와 오류 방식을 기반으로 모든 방법을 시도하되, 현재의 경로가 해결책으로 이어질 가능성이 없다고 판단될때 이전의 분기점으로 되돌아가 다른경로를 시도하는 방식이다. 최적화 문제, 조합문제를 해결하는데 유용할수 있다. 예시의 경우를 살펴보자 위와같은 노드가 있고 노드의 리프에 도착했을때 모든 노드의 합이 6 이 되는 경로를 찾아야된다고 할경우를 가정해보자. DFS 방식으로 탐색을 진행할경우 왼쪽방향으로 먼저 탐색하게 될것이다. 위처럼 리프에 도달했을때 노드의 총합은 21이라는 틀린값이 나오게된다. 하지만 이때 백트레킹 기법을 활용하게 된다면 노드 중간에 이미 찾아야하는 값이 먼저 나와버렸고, 해당 정점이 리프가아니므로 더이상 탐색은 의미가 없게되어버린다. 이때 다시 부모 분기점으로 되돌아가 다..

깊이우선탐색은 그래프의 모든 정점을 탐색하는 알고리즘중 하나 주변의 모든 인접점을 확인하며 탐색을 진행하는 BFS 알고리즘과는 반대로 현재 갈수있는 경로가 있다면 해당경로의 가장 깊은곳까지 탐색하는 방식이다. 해당알고리즘은 Stack 자료구조나 재귀함수로 구현하는게 일반적이다. 비선형자료구조를 탐색, 사이클 감지에 유용하며 모든 레벨의 노드를 기억해야하는 BFS 알고리즘과는 다르게 DFS 현재의 경로만 기억하면 되므로 BFS 보다는 메모리 효율을 높일수 있다는 점이 있다. 또한 DFS 탐색방법과 백트레킹방식으로 최적의 해를 구하는데 유용할수 있다. 0 정점을 시작으로 탐색을 진행해보자 0 정점의 인접점은 1 , 2 의 정점이 있다. 재귀함수 형태로 진행되는 과정을 표현해보자면 위의 그림과 같다. 함수를 ..

BFS는 탐색 방법중 하나로 시작 정점을 방문한뒤 인접한 정점들을 모두 탐색하는 방법을 뜻한다. 순차적으로 접근하는 방식을 사용하기위해 Queue 의 자료구조가 적합하며 가장 일반적이다. 사용시 주의할부분은 방문한곳을 다시 방문하지않게 처리해줘야한다. 위의 그림과 같은 노드가 있다고 가정해보자. 목적은 노드중에 8값을 찾아야한다. BFS 알고리즘으로 다음과 같은 탐색을 할경우 시작점을 가장먼저 Queue에 넣음으로 시작해 인접한 모든 정점을 다시 Queue에 넣어준다. Queue에 들어있던 0의 정점을 빼준뒤 인접한 정점들을 전부 확인한 다음 확인된 정점들을 다시 넣어준다. 이후 더이상 인접한 정점이 없으며 하나씩 Queue에서 빼면서 대상을 확인하면 된다. 문제 https://www.acmicpc.ne..

소수란 1보다 크며 1과 자기 자신을 제외한 다른수로는 나눠지지 않는 수를 의미한다. 작은 수부터 소수를 구할때 완전한 규칙성은 없다. 소수 구하는법 ① 2부터 시작해서 소수를 구해야 되는 범위 N을 확인한다. ② 지워지지 않은 가장 작은수를 확인한다. ③ 해당 수의 배수를 전부 지운다. ④ 위의 ② ③ 과정을 반복한다.

데이터가 정렬된 상태에서 데이터의 크기를 절반씩 줄이면서 대상을 찾는 알고리즘 중앙값을 비교하여 절반씩 줄여가므로 시간복잡도는 O(logN) 이 필요하다. 위와 같은 배열이 있을때 35를 찾아야한다고 가정해보자 앞에서부터 순차적으로 탐색하게될시 6번의 탐색 과정이 필요하다. 이진탐색 과정을 살펴보자 ① 중간값 15 보다 크므로 오른쪽을 다음 탐색범위로 지정 ② 중간값 23 보다 크므로 오른쪽을 다음 탐색범위로 지정 ③ 중간값 35 로 탐색대상 확인 문제 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤..

기존의 데이터 집합단위를 더이상 나눌수 없는 크기가 될때까지 분할한 뒤 임시 저장공간에 순서를 저장하며 재조합하며 정렬하는 방식 평균 시간복잡도는 분할단계로 집합을 절반씩 분할하므로 O(logN) 의 시간복잡도를 갖고 병합단계 모든요소가 비교되므로 O(N) 의 시간복잡도를 갖게 되므로 전체적인 시간복잡도는 O(N log N) 로 안정적인 성능을 제공하지만 주어진 집합요소(배열 , 리스트)가 있을때 임시로 저장해둘 똑같은 크기의 집합요소가 더 필요하게 된다. 또한 해당 알고리즘 구현시 데이터들을 다시 함수에 넣어줘야하므로 재귀에 대한 개념도 필요하며 두개의 집합으로만 정렬된 데이터를 구현하기위해 여러개의 포인터를 다뤄야하므로 구현이 조금 복잡할수 있다. 처음 알고리즘을 접하게될때 그림을 보고 조금 혼란스러..

알고리즘 문제해결을 하면서 시간초과를 겪고 해결방법을 찾던중 알게되었다. Console.ReadLine() , Console.WriteLine() 으로는 해결할수 없었고 좀더 효율적이며 빠른 입출력 방식을 찾아봐야했다. 그와중에 찾게된 StreamReader 와 StreamWriter 를 알게되었고 Reader 와 Writer 는 어떠한 역할을 하는지 대충 감이 오긴한다. Stream 은 요즘 많이 보이는 스트리밍 , 인터넷 방송의 송출과 관련된 용어라고 생각해왔다. Stream 정확히 어떤 뜻을 의미하는지, 프로그래밍의 스트림 이란게 뭘까 해서 찾아보게 되었다. 뭔가 줄줄이 이어지는 듯한 의미로 연속성의 의미를 갖는것같다. 데이터의 관점으로는 " 데이터를 추상화하여 연속적으로 처리할수 있게 하는 메커니..

피벗을 정하고 좌 , 우측 포인터를 가리키며 기준값보다 작다면 왼쪽 , 보다 크다면 오른쪽으로 정렬하는 알고리즘 한번의 탐색이 완료되면 피벗으로 정한 값은 정렬이 완료된다. 이후 다시 피벗을 정한뒤 재귀 함수를 사용해 반복시킨뒤 더이상 정렬할 데이터가 없을때까지 반복한다. 평균적인 시간 복잡도는 O(nlogn) 이지만 최악의 상황엔 O(N²)가 된다. 또한 기존의 정렬 방식과는 달리 분할된 데이터들을 다시 함수로 다뤄줘야하므로 재귀에 대한 개념도 필요하다. 문제 https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정..

현재 선택한(정렬되지않은) 데이터를 기존 정렬된 데이터의 적절한 위치에 삽입시켜 정렬하는 방식 시간 복잡도는 O(n²) 이고 구현하기 쉬운편 문제 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 풀이 int count = int.Parse(Console.ReadLine()); int[] arr = Array.ConvertAll(Console.ReadLine().Split(' '),int.Parse); for (int i = 1; i < count; i++) { int sel..