알고리즘 (8) 썸네일형 리스트형 에라토스테네스의 체 ( 소수 [Prime Number] 판별 알고리즘 ) 예제 에라토스테네스의 체 알고리즘이란? 여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표 알고리즘이다. 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다. 알고리즘 순서는 다음과 같다. 2부터 N까지의 모든 자연수를 나열한다. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다. 남은 수 중에서 i의 배수를 모두 제거한다 (i는 제거하지 않는다). 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다. 예를 들어 N = 1000 일 때를 확인해보자. [step1] 먼저 2부터 N(26)까지 모든 자연수를 나열한다. (1은 소수가 아니다) [step2] 남은 수 중에서 아직 처리하지 않은 가장 작은 수를 찾은 다음, 그 수를 제외한 배수를 제거한다. 따러.. 탐색 알고리즘 이진 탐색 [코딩 테스트, 코딩 면접 준비] 예제 이진 탐색 (Binary Search) 이란? 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다는 특징이 있다. 이진 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색한다. 이진 탐색은 위치를 나타내는 변수 3개를 사용하는데 탐색하고자 하는 범위의 시작점, 끝점, 중간점이다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 과정이다. 이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾은 예시를 보자. [step1] 시작점과 끝점을 확인한 다음 둘 사이에 중간점을 정한다. 중간점이 실수일 때는 소수점 이하를 버린다. 그림에서 각각의 인덱스는 시.. [탐색 알고리즘 BFS 너비 우선 탐색] 예제 자바 코드 (코딩 테스트, 코딩 면접 준비) 탐색 알고리즘 BFS 너비 우선 탐색 개념 정리는 아래 링크 참조 https://developercc.tistory.com/13 탐색 알고리즘 BFS 너비 우선 탐색 [코딩 테스트, 코딩 면접 준비] BFS(Breath First Search)란? 너비 우선 탐색이라고도 부르며, 가까운 노드부터 탐색하는 알고리즘이다. DFS(Depth First Search)는 최대한 멀리 있는 노드를 우선으로 탐색하는 방식으로 BFS는 그 반대이다. BF developercc.tistory.com BFS 알고리즘 예제 [문제] 유정이는 N * M 크기의 작사각형 형태의 미로에 갇혀 있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 유정이의 위치는 (1,1)이고 미로의 출구는 (N,M)의 위치에 존재하.. 탐색 알고리즘 BFS 너비 우선 탐색 [코딩 테스트, 코딩 면접 준비] BFS(Breath First Search)란? 너비 우선 탐색이라고도 부르며, 가까운 노드부터 탐색하는 알고리즘이다. DFS(Depth First Search)는 최대한 멀리 있는 노드를 우선으로 탐색하는 방식으로 BFS는 그 반대이다. BFS 구현에서는 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다. 인접한 노드를 반복으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리 한다. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 아래와 같은 그래프를 예를 들어 노드 .. [탐색 알고리즘 DFS 깊이 우선 탐색] 예제 자바 코드 (코딩 테스트, 코딩 면접 준비) 탐색 알고리즘 DFS 깊이 우선 탐색 개념 정리는 아래 링크 참조 https://developercc.tistory.com/10 탐색 알고리즘 DFS 깊이 우선 탐색 [코딩 테스트, 코딩 면접 준비] DFS(Depth-First Search)란? 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS 알고리즘은 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들 developercc.tistory.com DFS 알고리즘 예제 [문제] N * M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 .. 탐색 알고리즘 DFS 깊이 우선 탐색 [코딩 테스트, 코딩 면접 준비] DFS(Depth-First Search)란? 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS 알고리즘은 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘이다. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다. '방문 처리'는 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미한다. 방문 처리를 함으로써 각 노드를 한 번씩만 처리할.. 탐욕 (그리디) 알고리즘 [코딩 테스트, 코딩 면접 준비] 탐욕 (Greedy) 알고리즘이란? 단순하지만 강력한 문제 해결 방법이다. 어떠한 문제가 있을 떄 단순 무식하게, 탐욕적으로 문제를 해결하는 알고리즘이다. 즉 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 탐욕 알고리즘 예제 [문제] 당신은 음식점의 계산을 도와주는 점원이다. 카운터에서 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일때 거슬러줘야 할 동전의 최소 개수를 구하라, 단, 거슬러 줘야 할 돈은 N의 항상 10의 배수이다. [문제 해설] 그리디 알고리즘을 이용해 해결 할 수 있는 대표적인 문제이다. 가장 큰 화폐 단위부터 돈을 거슬러 주.. 알고리즘 시간 복잡도(Complexity) 쉽게 이해하기 복잡도란? 알고리즘의 성능을 나타내는 척도입니다. 복잡도는 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)로 나눌 수 있습니다. 시간 복잡도 알고리즘 문제를 해결할 때 단순히 '복잡도'라고 하면 보통 시간 복잡도를 의미합니다. 시간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미하며, 알고리즘을 위해 필요한 연산의 횟수 또한 의미합니다. 시간 복잡도를 표현할 떄는 빅오(Big-O) 표기법을 사용합니다. 간단히 정의하자면 가장 빠르게 증가하는 항만을 고려하는 표기법입니다. 다음 아래 빅오 표기법 표는 위쪽에 있을수록 더 빠릅니다. 빅오 표기법 명칭 설명 O(1) 상수 시간(Constant time) 문제를 해결하는데 오직 한 단계 처리 .. 이전 1 다음
