거대한 그래프에서 특정 조건을 만족하는 노드를 찾는 가장 효율적인 방법은 무엇일까? 본 포스팅에서는 그래프의 노드를 탐색 혹은 방문하는 유명한 알고리즘인 DFS(Depth-First Search)와 BFS(Breadth-First Search)에 대해 소개하고자 한다. DFS(Depth-First Search)DFS는 그래프의 한 경로를 끝까지 탐색한 후, 다른 경로를 탐색하는 방법이다. 깊이를 우선으로 탐색하는 방식이다. DFS는 아래와 같은 특징을 가진다.구현 방식: 재귀나 스택 자료구조를 사용하여 구현한다.완전 탐색: 한 경로의 끝까지 가고, 더 이상 진행할 수 없으면 이전 노드로 돌아와 다른 경로를 탐색한다.메모리 사용량: 경로의 깊이에 비례하여 메모리를 사용한다.예를 들어, 아래와 같은 완전 이..

스택/큐같은 숫자는 싫어문제 설명배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 예를 들면,- arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다.- arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다.배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.제한사항배열 arr의 크기 : 1,000,000 이하의 자연수배열 arr의 원소의 크기 ..

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 1부터 N까지의 수가 한 줄로 무작위 순서로 서 있다. 이들을 크기 순서로 세우는 최적의 알고리즘은 무엇일까? 본 포스팅에서는 각종 정렬 알고리즘을 교재를 바탕으로 정리해보고자 한다. 정렬 알고리즘의 성능은 비교의 횟수와 이동의 횟수가 결정한다. 그리고 이를 기준으로 Big-O notation을 정한다. 1. 버블 정렬(Bubble Sorting) 버블 정렬은 연속한 두 개의 항을 비교하여, 앞의 것이 크기가 크면 순서를 바꾸고, 뒤의 것이 크면 순서를 유지하는 방법이다. 앞에서부터 뒤로 훑는 이 과정을 모든 수가 정렬될 때까지 반복한다. 버블 정렬의 코드는 아래와 같다. #include void Bu..

1764번: 듣보잡 김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오. 입력: 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다. 듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다. 출력: 듣보잡의 수와 그 명단을 사전순으로 출력한다. 문제를 보자마자 "교집합->set을 이용하자" 를 떠올렸다. Intersection..

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 재귀는 자료구조와 알고리즘에서 매우 중요한 요소이다. 재귀함수의 기본적 이해 void Recursive(){ printf("Recursive Call\n"); Recursive(); } 재귀함수는 위와 같이 함수 안에서 함수를 다시 호출하는 형태이다. 그러나 Recursive의 정의 부분에서 Recursive를 호출하고 있는데, 정의가 끝나지 않은 함수를 다시 호출하는 것이 가능한가? 재귀함수가 작동할 때 아래와 같이 메모리상에서 함수의 복사본을 여러 개 만들고 다시 호출한다. 즉, 함수의 명령문을 실행할 때 CPU로 불러와서 사용하는데, 명령문을 실행하는 중간에 재귀 조건이 등장한다면 CPU로 하나 ..