알고리즘

Big-O 표기법

• 알고리즘의 성능을 시각적으로 표시, 시간, 공간
• 정확한 시간을 파악하는게 아닌 장기적으로 데이터가 늘어남에 따라 처리시간의 증가율을 예측하기 위한 표기법
• 상수는 버린다
  • O(2n) = O(n)
  • O(n^2+n^2) = O(n^2)
• O(1) : 입력데이터의 크기에 상관없이 언제나 일정한 시간과 속도로 결과를 반환한다.
  • 상수 시간 : 문제를 해결하는데 오직 한 단계만 처리함
• O(n) : 입력 데이터의 크기에 비례해서 처리시간이 경과된다.
  • 직선적 시간 : 문제를 해결하기 위한 단계와 수와 입력값 n이 1:1 관계를 가짐
  • n의 범위가 10,000,000 까지를 풀 수 있다.
• O(n^2) : n을 for문돌릴때 for문안에 n의 for문을 또 돌린다. n을 2중으로 돌린다. 데이터가 커지면 커질수록 처리시간이 더 늘어난다. 면적
  • 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱
  • n의 범위가 2000 까지
• O(nm) : m을 n만큼 돌린다. 데이터가 증가할수록 그래프가 수직이 된다.
• O(n^3) : n을 3번 돌린다. 큐빅이 된다.
  • 3차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 세제곱
  • n 범위가 500 까지
• O(2^n) : 피보니치 수열 1부터 시작해서 한면(늘어난 면)을 기준으로 정사각형을 만든다.
  • 1부터 시작해서 1의 다른 한면은 1이니까 1을 하나더 그다음 앞에 두개를 더해서 2 그다음 더해서 3,5,8 ….
  • 코드상으로는 재귀함수로 구현이 되며 함수를 호출할때 마다 바로 전에 숫자와 바로 전전 숫자를 호출 f(n-1,r) + f(n-2,r)
  • 코드가 반복되므로 불필요한 시간을 낭비하지 않기 위해 배열에 저장해서 사용 한번 저장된 배열 값은 재귀함수를 통해 또 호출할 필요 없이 값을 불러오도록 할 수 있다..
• O(m^n) : ..
• O(log n) : 한번 처리가 진행될때마다 검색해야 하는 데이터의 양이 절반씩 떨어진다.
  • 로그 시간 : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬
  • 2진 검색 : 반으로 나눠 중간값을 찾아 찾으려는 값과 비교하고 다시 반으로 나눈다고 비교 … 반복 후 값을 찾음
  • 시작번호는 0 끝 번호는 배열의 마지막으로 지정후 반복 비교후 값을 찾음
• O(sqrt(n)) : 제곱근(루트)
  • 정사각형의 맨위
• O(n log n)
  • 문제를 해결하기 위한 단계의 수가 n*(log2n) 번만큼 수행시간을 가진다.(선형 로그형)
  • n의 범위가 100,000

그리디 알고리즘

• 탐욕법으로도 소개가 되며 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다.
• 코딩 테스트에서는 대부분 최적의 해를 찾는 문제가 출제된다
• 대표 예시는 거스름돈 문제로 여러 종류의 동전을 무한히 가지고 있는 상황에서 거슬러 줘야 할 금액이 주어졌을 떄 거슬러 줘야 하는 동전 개수를 찾는 문제이다.
• 또 다른 전형적인 그리디 알고리즘은 1이 될 때가지 인데 이 문제는 어떠한 자연수 N이 1이 될때까지 1을 빼기 혹은 K로 나누기 연산을 최소 며천 수행해야 되는지 이다.
• 다익스트라 최단 경로 알고리즘, 크루스칼 알고리즘은 모두 그리디 알고리즘에 속한다.
  • 다익스트라 최단 경로 알고리즘은 특정 노드까지의 최단 거리를 계산한 다음 메모리에 저장하고 나중에 필요할때 이를 다시 꺼내 본다는 점에서 다이나믹 프로그래밍으로 분류하기도 한다.
• 코딩 테스트 문제에서 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심, 그리디 알고리즘으로 해결 할 수 없다면 다이나믹 프로그래밍이나 그래프 알고리즘 등으로 확인해본다.
• 최적의 해를 찾아야함 어렵다..

구현

• 다른 알고리즘을 포함 할 수 있으나 구현 내용을 잘 따라간다면 무리없이 구현 할 수 있다.
• 완전 탐색
  • 모든 경우의 수를 빠짐없이 다 계산하는 해결 방법을 의미한다.
  • 모든 경우의 수를 다 계산해야 하기 때문에 반목문 또는 재귀 함수를 적절히 사용해야 하며 예외 케이스를 모두 확인해야 하는 경우가 많아 DFS/BFS 알고리즘을 이용한다.
• 시뮬레이션
  • 문제에서 제시하는 논리나 동작 과정을 그대로 코드로 옮겨야 하는 유형을 의미한다.
  • 문제에서 요구하는 복잡한 구현 요구사항을 그대로 코드로 옮겨야 한다는 점에서 해결 방법이 비슷하다.
• 소스코드를 구현하기 까다롭거나, 까다로운 문자열 처리를 해야 하거나, 구현해야 할 소스코드의 양이 매우 많은 문제도 구현 유형으로 구분된다.

자료 구조

• 데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다. 그중 스택과 큐는 자료구조의 기초 개념으로 삽입(Push), 삭제(Pop) 가 핵심 함수며 사용시에는 오버플로와 언더 플로를 조심해야 한다.
• 오버플로
  • 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행 할때 발생한다.
  • 즉 저장 공간을 벗어나 데이터가 넘쳐흐를 때 발생한다.
• 언더플로
  • 특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행하면 데이터가 전혀 없는 상태이므로 언더플로가 발생한다.
• 스택
  • 선입 후출 구조 또는 후입 선출 구조라고 하며 박스를 쌓듯이 아래에서 부터 차곡차곡 쌓아 가장 위에있는 박스부터 내보낸다.
• 큐
  • 선입선출 구조라고 하며 대기줄에 비유할 수 있고 먼져 들어가면 먼져 나올 수 있어 공정한 자료구조라고 비유된다.

재귀 함수

• 자기 자신을 다시 호출하는 함수로 수행은 스택 자료구조를 이용한다.
• 함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다.
• 컴퓨터의 구조 측면에서 보자면 연속해서 호출되는 함수는 메인 메모리의 스택 공간에 적재되므로 재귀 함수는 스택 자료구조와 같다느 말은 틀린 말이 아니다.
• 팩토리얼
  • 팩토리얼 기호는 느낌표(!)를 사용하며 n! 1 - 2 - 3 - … - (n - 1) - n 을 의미한다. 수학적으로 0!와 1!의 값은 1로 같다는 성질을 이용하여 팩토리얼 함수는 n이 1 이하가 되었을 때 함수를종료하는 재귀 함수의 형태로 구현할수 있다.

탐색

• 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다.

DFS

• 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 이다.
• 그래프는 노드와 간선으로 표현되며 이때 노드를 정점이라고도 말한다. 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 또한 노드가 간선으로 연결되어 있다면 두 노드는 인접하다라고 표현한다.
• 인접 행렬
  • 2차원 배열로 그래프의 연결 관계를 표현하는 방식
  • 각 노드가 연결된 형태를 기록하는 방식으로 연결이 되어 있지 않은 노드끼리는 무한의 비용으로 작성한다. 실제 코드에서는 논리적으로 정답이 될 수 없는 큰 값중에서 9999999,987654321 값으로 초기화 하는 경우가 많다.
• 인접 리스트
  • 리스트로 그래프의 연결 관계를 표현하는 방식
  • 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장한다.
  • 연결 리스트 자료 구조를 이용해 구현하는데 자바에선 링크드 리스트 라이브러리를 사용한다.
• 인접 행렬과 인접 리스트의 차이는 인접 행렬 방식은 모든 관계를 저장하므로 노드 개수가 많아질수록 메모리가 불필요하게 낭비된다. 반면에 인접 리스트 방식은 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용한다.
• 하지만 이와 같은 속성 때문에 인접 리스트 방식은 인접 행렬 방식에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다. 인접 리스트 방식에서는 연결된 데이터를 하나씩 확인해야 하기 때문이다.
• DFS 동작 과적(스택 자료구조 이용)
  • 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
  • 스택 최상단 노드에 방문하지 않는 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
  • 위 과정을 더 이상 수행할 수 없을 때까지 반복한다.
• 방문 처리는 스택에 한번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미한다. 방문 처리를 함으로써 각 노드를 한번씩만 처리할 수 있다.

BFS

• 너비 우선 탐색이라는 의미를 가진다. 쉽게 말해 가까운 노드부터 탐색하는 알고리즘이다.
• 선입 선출 방식인 큐 자료구조를 이용하는 것이 정석이다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스롭게 먼저 들어온 것이 먼저 나가게 되어 가까운 노드부터 탐색을 진행하게 된다.
• BFS 동작박식(큐 자료구조 이용)
  • 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
  • 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
  • 위 과정을 더 이상 수행할 수 없을 때까지 반복한다.
• 너무 우선 탐색 알고리즘인 bFS는 큐 자료구조에 기초한다는 점에서 구현이 간단하다. 실제로 구현함에 있어 deque 라이브러리를 사용하는 것이 좋으며 탐색을 수행하는데 있어 O(N)의 시간이 소요된다.
• 코딩 테스트에서는 보통 DFS보다는 BFS 구현이 조금 더 빠르게 동작한다.

정렬

• 데이터를 특정한 기준에 따라서 순서대로 나열하는 것이다.
• 선택 정렬
  • 가장 작은 데이터를 선택해서 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복한다.
  • 매번 가장 작은 것을 선택한다는 의미에서 선택정렬 알고리즘이다.
  • O(N^2)
• 삽입 정렬
  • 2번째 인덱스부터 시작해서 왼쪽중에 작은 위치에 들어간다.
  • 왼쪽은 이미 정렬되어 있다고 가정한다.
  • 삽입 정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을때 효율적이다.
• 퀵 정렬
  • 기준 데이터(pivot)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다.
  • 위 작업 후 기준 데이터는 이미 정렬되어 있어 기준 데이터의 왼쪽과 오른쪽을 정렬, 반복작업을 통해 정렬을 수행함
  • 이미 정렬되어 있을경우 값 모두가 피벗값이 되면서 속도가 느려진다.
  • O(NlogN)
  • O(N^2) : 최악일때
• 계수 정렬
  • 특정한 조건이 부합할 때만 사용할 수 있다.
  • 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용할 수 있다.
  • 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.
    • 모든 범위를 담을 수 있는 크기의 리스트(배열)를 선언하기 때문이다.
  • O(N+K)
• 순차 탐색
  • 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
• 이진 탐색
  • 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘 이다.
  • 데이터가 무작위 일때는 사용할 수 없지만 정렬되어 있을때는 빠르게 찾을 수 있다.
  • 위치를 나타내는 변수 3개를 사용하는데 하는 범위의 시작점, 끝점, 중간점이다.
  • 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는과정을 말한다.

다이나믹 프로그래밍

• 메모리 공간을 약간 더 사용하면서 연산속도를 비약적으로 증가시킬 수 있는 방법, 동적 계획법
• 피보나치 수열
  • 이전 두 항의 합을 혀재의 항으로 설정하는 특징이 있다.
  • 점화식 : a_n = (a_n-1) + (a_n-2), a_1 = 1 a_2 = 1
  • 첫번째 항과 두번째 하으이 값은 모두 1이기 때문에 위에 점화식으로 표현 할 수 있다.
  • f(4)를 구할떈 f(3), f(2) 이고 f(2)는 1이기 때문에 멈춘다(a_2 = 1), f(3)은 f(1), f(2)
• 메모이제이션 기법
  • 피보나치 수열은 큰 문제를 작은 문제로 나눌 수 있을때, 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일할때 사용 가능하다.
  • 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다.
  • 값을 저장하는 방법이므로 캐싱이라고도 한다.
• 탑다운
  • 재귀 함수를 이요하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을, 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운 방식이라고 말한다.
• 보텀 업
  • 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다 하여 보텀업 방식이라고 한다.

최단 경로

• 가장 짧은 경로를 찾는 알고리즘으로 한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 경우, 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우가 있다.

다익스트라

• 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우다.
• 그래프에서 여러개의 노드가 있을때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다.
• 다익스트라 최단 경로 알고리즘은 음의 간선이 없을때 정상적으로 동작한다.
• 음의 간선이란 0보다 작은 값을 가지는 간선을 의미하며 혀실 세계의 길(간선)은 음의 간선으로 표현되지 않으므로 다익스트라 알고리즘은 실제로 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다.
• 최단 경로를 구하는 과정에서 각 노드에 대한 현재까지의 최단 거리 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신한느 특징이 있다.
• 매번 현재 처리하고 있는 노드를 기준으로 주변 간선을 확인하고 나중에 현재 처리하고 있는 노드와 인접한 노드로 도달하는 더 짧은 경로를 찾으면 갱신한다.
• 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것이다.
• 순서
  • 출발 노드를 설정한다.
  • 최단 거리 테이블을 초기화한다.
  • 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
  • 해당 노드를 거쳐 다른 노드로 가는 비용으 ㄹ계산하여 최단 거리 테이블을 갱신한다.
  • 바로 위과정 2개를 반복한다.

플로이드 워셜 알고리즘

• 모든 지점에서 다른 모든 지점까지의 최단 경로를 구하는 알고리즘이다.
• 2차원 배열로 각 두지점간 이동할수 있는 최단 거리가 저장된다.
• 2차원 배열에서 각 지점을 하나씩 더 거쳐가면서 더 단거리가 있는지 확인 후 갱신한다.

서로소 집합

• 공통 원소가없는 두 집합을 의미한다.
• 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다.
• 서로소 집합 자료구조는 union(합집합)과 find(찾기) 이 2개의 연산으로 조작할 수 있다.

서로소 집합 자료구조

• union(합집합) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다.
  • A와 B의 루트 노드 A’, B’를 각각 찾는다.
  • A’를 B’의 부모 노드로 설정한다.(B’가 A’를 가리키도록 한다.)
• 모든 union(합집합) 연산을 처리할 때까지 위 과정을 반복한다.
• A’와 B’ 중에서 더 번호가 작은 원소가 부모 노드가 되도록 구현하는 경우가 많다.
• 무방향 그래프 내에서의 루트 노드가 같다면 사이클을 판별할 수 있다.

신장 트리

• 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지않는 부분 그래프를 의미한다.
• 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이기다 하다.

크루스칼 알고리즘

• 신장트리를 찾는 알고리즘 중 최소 신장 트리 알고리즘이다
• 가장 적은 비용으로 모든 노드를 연결할 수 있는데 크루스칼 알고리즘은 그리디 알고리즘으로 분류된다.
• 먼저 모든 간선에 대하여 정렬을 수행한 뒤에 가장 거리가 짧은 간선부터 집합에 포함 시키면서 된다.
  • 간선데이터를 비용에 따라 오름차순으로 정렬한다.
  • 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.
    • 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다.
    • 사이클이 발생하는 경우 신장 트리에 포함시키지 않는다.
  • 모든 간선에 대하여 두번째 과정을 반복한다.

위상 정렬

• 정렬 알고리즘의 일종으로 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할떄사용할 수 있는 알고리즘이다.
• 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것이다.
• 실제 위상정렬을 수행하는 전형적인 예시로는 선수과목을 고려한 학습 순서 설정이다.
• 진입 차수
  • 특정한 노드로 들어오는 간선의 개수를 의미한다.
  • 자료구조 - 알고리즘 - 고급 알고리즘
  • 위 같이 정렬되어 있을때 고급 알고리즘은 진입차수가 2개이다.
• 위상 정렬 순서
  • 진입차수가 0인 노드를 큐에 넣는다.
  • 큐가 빌 때까지 다음의 과정을 반복한다.
    • 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
    • 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.