컴퓨터 공학/알고리즘 (14) 썸네일형 리스트형 BFS (Breath First Search) 너비우선탐색, DFS (Depth First Search) 깊이우선탐색 이번 글에서는 코딩테스트 출제 빈도가 아주 높은 알고리즘은 BFS 너비우선탐색과 DFS 깊이우선탐색 에 대해 소개하겠습니다. 이번 정리 역시 프로그래머스에서 코딩테스트 연습을 하다가 BFS/DFS 영역의 문제를 풀기전 개념을 다시 한 번 정확히 정리해보고자 정리한 글입니다. BFS와 DFS는 그래프 자료구조를 탐색할 때 사용되는 기법입니다. 두 기법 모두 그래프에 속한 모든 노드를 방문하는 것을 목적으로 하는데, 탐색 우선 순위를 어떤 것으로 두는 지에 따라 두 기법의 차이가 있습니다. 너비 우선 탐색 BFS (Breath First Search) BFS의 개념 BFS는 이름에서 알 수 있듯이, 너비 Breath를 우선으로 탐색하는 기법입니다. 그래프 탐색의 시작점 (루트 또는 특정 노드) 과 같은 거리.. 완전 탐색 Exhaustive Search 이번 글에서는 완전 탐색에 대한 내용을 다루겠습니다. 프로그래머스에서 코딩 테스트 연습에 완전 탐색 카테고리가 있는데 문제를 풀기 전에 개념을 확실히 짚고 넘어가는게 좋을 것 같아 정리했습니다. 재귀함수 Recursion Function 완전 탐색 알고리즘에서는 재귀 함수가 주로 사용되기 때문에 먼저 알아보았습니다. 재귀란, 컴퓨터 과학에서 자기 자신을 재참조하는 방법을 의미합니다. 재귀 함수는 함수 내에서 자기 자신을 다시 호출하는 함수를 말합니다. 즉, 자신이 수행할 작업이 일정한 패턴을 가지고 반복된다면, 패턴의 한 조각을 수행하는 함수를 만들고, 그 함수가 다시 자기 자신을 호출해서 해당 함수를 반복 실행할 수 있도록 하는 것입니다. base case 그렇다면 이렇게 무한히 자기 자신을 호출하는 .. 정렬 알고리즘 (3) : 합병 정렬, 퀵 정렬 지난 시간에 이어 이번 글에서도 정렬 알고리즘에 대해 이어 설명하겠습니다. 이번 글에서는 합병 정렬과 퀵 정렬에 대해 소개하겠습니다. 합병 정렬 Merge Sort 합병 정렬의 개념 합병 정렬은 분할 정복 (Divide and Conquer) 방식으로 큰 문제를 반으로 쪼개가며 작은 문제로 만든 후, 작은 문제를 해결한 결과를 합쳐 전체를 정렬하는 방식의 알고리즘 입니다. 여기서 등장하는 분할 정복이라는 개념을 아주 중요한 개념이기 때문에 다음 번에 하나의 큰 주제로 자세히 설명하도록 하겠습니다. 합병 정렬의 기본 로직 합병 정렬은 크게 분할과 합병 과정으로 이루어집니다. 분할 Divide 현재 배열의 ( 시작 인덱스 + 종료 인덱스 ) / 2 한 값을 기준으로 현재 배열을 받으로 쪼갠다. 쪼갠 배열의 .. 정렬 알고리즘 (2) : 삽입 정렬, 버블 정렬 지난 시간에 이어 이번 글에서도 정렬 알고리즘에 대해 이어 설명하겠습니다. 이번 글에서는 삽입 정렬과 버블 정렬에 대해 소개하겠습니다. 삽입 정렬 Insertion Sort 삽입 정렬의 개념 삽입 정렬은 현재 인덱스와 해당 인덱스보다 작은(왼쪽) 인덱스에 있는 원소들을 비교하여 자신이 들어갈 위치를 찾아 삽입하는 정렬 알고리즘 입니다. 삽입 정렬의 기본 로직 0번째 인덱스는 가장 왼쪽에 위치해 있기 때문에 비교 대상이 없으므로 삽입 정렬은 1번재 인덱스부터 시작합니다. 삽입할 대상이 되는 현재 인덱스는 별도의 변수에 저장해 두고, 현재 인덱스에서 -1 한 인덱스의 원소들을 비교합니다. 현재 인덱스의 원소 값이 비교 인덱스의 원소 값보다 큰 원소를 만날때까지 비교 인덱스를 -1 씩 해주며 왼쪽으로 이동합니.. 정렬 알고리즘 (1) : 선택 정렬 이전 글에서 알고리즘이 무엇인지, 왜 배워야 하는지에 대한 이야기를 간단히 나눴습니다. 이번 글부터는 알고리즘의 기본, 정렬 알고리즘에 대해 공부해보겠습니다. 정렬 알고리즘이 무엇인지 그리고 정렬 알고리즘의 종류에는 무엇이 있는지 이야기하고, 이번 글에서는 정렬 알고리즘 중 선택 정렬에 대해 설명하겠습니다. 정렬 알고리즘 Sorting Algorithm 정렬 알고리즘의 개념 n개의 데이터가 입력(input)으로 주어졌을 때, 이를 사용자가 지정한 기준(내림차순, 오름차순 등)에 맞게 데이터를 정렬하여 출력(output)하는 알고리즘을 말합니다. 정렬 알고리즘은 다른 알고리즘을 최적화하는데 중요한, 아주 기본적인 알고리즘입니다. 따라서 다양한 정렬 알고리즘이 발명되었고, 계속해서 더 효율적인 정렬 알고리즘.. 알고리즘 공부를 시작하며 알고리즘 공부를 시작하기에 앞서 알고리즘이 무엇이고, 그 필요성에 대해 알아보겠습니다. 알고리즘이란 위키백과에서는 알고리즘을 계산을 수행하거나 일련의 문제를 해결하기 위해 사용되며, 컴퓨터로 구현 가능한, 잘 정의된 명령어의 유한한 집합 이라고 정의합니다. 간단하게는 컴퓨터 공학에서 알고리즘이란 컴퓨터 프로그램 성능과 자원 활용에 대한 이론적인 연구를 의미합니다. 알고리즘 공부의 필요성 한정된 자원을 가지고 최고의 성능을 내기 위해서는 최적의 알고리즘을 선택하는 것이 중요합니다. 적절한 알고리즘을 선택하기 위해서는 어떤 알고리즘이 존재하고, 각 알고리즘의 실행 시간 및 자원 활용 정도를 계산할 수 있어야 합니다. 그래서 다음 글부터 다양한 알고리즘의 성능과 자원 활용에 초점을 맞추어 알고리즘 이론을 공부.. 이전 1 2 다음
