🖥️ Computer Science/Algorithm8 [알고리즘] 그래프 알고리즘 그래프(Graph) 노드(Node)와 노드 사이에 연결된 간선(Edge)의 정보를 가지고 있는 자료구조 서로 다른 개체(혹은 객체)(Object)가 연결되어 있다는 문제는 그래프 알고리즘 떠올리기 그래프 구현 방법 인접 행렬(Adjacency Matrix) : 2차원 배열 사용 메모리 공간이 많이 필요하지만 특정 노드 간 간선의 비용을 O(1) 시간으로 즉시 알 수 있음 인접 리스트 (Adjacency List) : 리스트 사용 간선의 개수인 O(E) 만큼만 메모리 공간이 필요하지만 O(V) 시간 소요 그래프 트리 방향성 방향 그래프 혹은 무방향 그래프 방향 그래프 순환성 순환 및 비순환 비순환 루트 노드 존재 여부 루트 노드가 없음 루트 노드가 존재 노드간 관계성 부모와 자식 관계 없음 부모 자식 관계.. 2022. 4. 14. [알고리즘] 최단 경로(Shortest Path) 최단 경로(Shortest Path) 알고리즘 가장 짧은 경로를 찾는 알고리즘 길 찾기 문제라고도 불림 그래프를 이용하여 표현 각 지점은 노드로 표현 지점과 연결된 도로는 간선으로 표현 최단 경로 문제의 종류 단일 출발(single-source) 최단 경로 어떤 하나의 정점에서 출발하여 나머지 모든 정점까지의 최단 경로를 찾는 문제 단일 도착(single-destination) 최단 경로 모든 정점에서 출발하여 어떤 하나의 정점까지의 최단 경로를 찾는 문제 그래프 내의 간선을 뒤집으면 단일 출발 최단거리 문제로 바뀔 수 있음 단일 쌍(single-pair) 최단 경로 모든 정점 쌍들 사이의 최단 경로를 찾는 문제 주요 알고리즘 다익스트라(Dijkstra) 알고리즘 벨만-포드(Bellman-Ford-Moo.. 2022. 3. 31. [알고리즘] 다이나믹 프로그래밍(Dynamic Programming) 컴퓨터를 활용해도 어려운 문제 최적의 해를 구하기에 시간이 매우 많이 필요한 문제 최적의 해를 구하기에 메모리 공간이 매우 많이 필요한 문제 컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이라 많은 제약 발생 ☞ 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘 작성 필요 다이나믹 프로그래밍(Dynamic Programming) 동적 계획법 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법 다이나믹 프로그래밍은 다음 조건을 만족할 때만 사용 가능 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 .. 2022. 3. 30. [알고리즘] 이진 탐색(Binary Search) 순차 탐색(Sequential Search) 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 하나씩 차례대로 확인하는 방법 정렬 여부와 상관없이 가장 앞에서부터 하나씩 확인 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 데이터를 찾을 수 있음 시간 복잡도 → O(N) 이진 탐색(Binary Search) 탐색 범위를 절반씩 좁혀가며 데이터를 탐색 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하여 원하는 데이터 탐색 위치를 나타내는 시작점, 끝점, 중간점 3개의 변수 사용 배열 내부의 데이터가 정렬되어 있어야만 사용 가능 시간 복잡도 → O(logN) 트리 자료구조 더보기 트리(Tree) 구조 노드와 노드의 연.. 2022. 3. 25. [알고리즘] 정렬(Sorting) 정렬(Sorting) 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다. 선택 정렬(Selection Sort) 정렬되지 않은 데이터 중에서 가장 작은 것을 선택해 맨 앞으로 보낸다. 다른 정렬 알고리즘들에 비해 비효율적이다. → 시간 복잡도: O(N^2) 삽입 정렬(Insertion Sort) 데이터를 하니씩 확인하며, 각 데이터를 적절한 위치에 삽입한다. 데이터가 거의 정렬되어 있을 때 효율적이다. → 시간 복잡도: O(N^2) 퀵 정렬(Quick Sort) 기준 데이터를 설정하고, 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다. 피벗(Pivot): 기준 데이터 → 평균 시간 복잡도: O(NlogN) 계수 정렬(Count Sort) 가장 작은 데이터부터 가장 큰 데이터까지 모두 담길 .. 2022. 3. 24. [알고리즘] DFS/ BFS 탐색(Search): 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 그래프, 트리 등의 자료구조 안에서 탐색하는 문제를 주로 다룬다. 대표적인 탐색 알고리즘으로 DFS와 BFS가 있다. 두 알고리즘을 이해하기 위해 필요한 자료구조 더보기 자료구조(Data Struture): 데이터를 표현하고 관리하고 처리하기 위한 구조 스택과 큐는 자료구조의 기초 개념으로 다음 두 핵심 함수로 구성된다. 삽입(Push): 데이터를 삽입 삭제(Pop): 데이터를 삭제 오버플로우(Overflow): 특정 자료구조가 수용할 수 있는 데이터의 크기를 넘은 상태에서 삽입 연산을 수행할 때 발생 언더플로우(Underflow): 특정 자료구조에 데이터가 들어있지 않은 상태에서 삭제 연산 수행 시 발생 스택(Stack): 데이터.. 2022. 3. 23. [알고리즘] 구현(Implementation) 구현(Implementation)이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다. 구현 유형의 문제는 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제이다. 알고리즘은 간단한데 코드가 지나치게 길어지는 문제 특정 소수점 자리까지 출력해야 하는 문제 문자열이 주어졌을 때 파싱 해야 하는 문제 구현 시 고려해야 할 메모리 제약 사항 변수의 표현 범위 리스트(배열) 크기 완전 탐색: 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행 구현 알고리즘 문제 상하좌우 여행가 A는 N x N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 x 1 크기의.. 2022. 3. 22. [알고리즘] 그리디(Greedy) 그리디(Greedy) 탐욕법 알고리즘 현재 상황에서 가장 좋은 것을 고르는 알고리즘 그리디 알고리즘 문제를 해결하는 방법 선택 절차(Selection Procedure): 현재 상태에서 최적의 해답 선택 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사, 해결되지 않았다면 선택 절차로 돌아와 위의 과정 반복 그리디 알고리즘 조건 탐욕스러운 선택 조건(Greedy Choice Property): 앞의 선택이 이후의 선택에 영향을 주지 않는다 최적 부분 구조(Optimal Substructure): 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법이다. 그리디 알고리즘 문제 .. 2022. 3. 8. 이전 1 다음 반응형