반응형 알고리즘&코딩테스트24 [Algorithm] 그리디 알고리즘(Greedy Algorithm)이란? 이 글은 '이것이 코딩테스트다'를 요약하여 그리디 알고리즘에 대하여 설명합니다. 학습 목표 · 그리디 알고리즘이란? · 예시 - 거스름돈 문제 · 그리디 알고리즘의 정당성 그리디 알고리즘이란? · 탐욕적으로 문제를 푸는 알고리즘 - 탐욕적이라는 말은 ‘매 순간 가장 좋아 보이는 것만 선택하고 나중에 미칠 영향은 고려하지 않는’ 방식을 의미한다. · 코딩 테스트에서 만나게 될 그리디 알고리즘 문제 유형의 특징: - 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형이다. - 문제 유형이 매우 다양하여 암기한다고 항상 잘 풀 수 있는 알고리즘 유형이 아니다. 때문에 많은 유형을 접해보고 문제를 풀어보며 훈련 해야 한다. - 일반적으로 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 .. 2021. 11. 4. [Algorithm] 그래프 이론: 트리, 서로소, 신장 트리, 크루스칼 알고리즘, 위상 정렬 학습 목표 · 그래프(Graph)란? · 트리(Tree)란? · 서로소 집합 - 서로소 집합 자료구조 - 문제점 - find 함수 개선: 경로 압축 기법 - 서로소 집합을 활용한 사이클 판별 · 신장 트리(Spanning Tree) - 최소 신장 트리 알고리즘 - 크루스칼 알고리즘 · 위상 정렬 · DFS/BFS, 최단 경로 알고리즘은 그래프 알고리즘의 한 유형 · 크루스칼 알고리즘 - 그리디 알고리즘, 위상 정렬 알고리즘 - 큐 자료 구조 or 스택 자료구조를 활용하여 구현 그래프(Graph)란? · 노드(Node)와 노드 사이에 연결된 간선(Edge)의 정보를 가지고 있는 자료구조 · 그래프를 구현하는 2가지 방식: 1. 인접 행렬(Adjacency Matrix): 2차원 배열을 사용하는 방식 ex).. 2021. 11. 3. [Algorithm] 최단 경로를 찾는 알고리즘 (다익스트라, 플로이드 워셜) 학습 목표 · 최단 경로(Shortest Path) 알고리즘이란? · 다익스트라 알고리즘 - 간단한 다익스트라 알고리즘 - 개선된 다익스트라 알고리즘 · 플로이드 워셜 알고리즘 최단 경로(Shortest Path) 알고리즘이란? · 가장 짧은 경로를 찾는 알고리즘, '길 찾기' 문제로 불린다. · 문제를 그래프로 표현하고 각 지점을 노드, 지점간 연결된 도로는 간선이라한다. · 최단 경로 알고리즘에는 그리디 알고리즘과 다이나믹 프로그래밍이 그대로 적용된다. · 다양한 사례가 존재하며, 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있다. ex) 한 지점에서 다른 특정 지점까지 최단 경로 구하기, 모든 지점에서 다른 모든 지점까지 최단 경로 구하기 등 다익스트라 알고리즘 · 그래프에 여러 노드가 있을 때,.. 2021. 10. 17. [Algorithm] 이것이 코딩테스트다 - 이진탐색 문제풀이(with 자바) 부품찾기 public class 부품찾기 { public static void main(String [] args){ Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); int[] parts = new int[N]; for(int i=0; i target){ start = mid+1; } else { end = mid-1; } } } } 2021. 9. 13. [Algorithm] 순차 탐색과 이진 탐색 순차 탐색 (Sequential Search) · N개의 데이터가 있을 때, 해당 데이터를 차례대로 하나씩 확인하여 처리하는 방법 · 정렬 여부와 상관없이 가장 앞에 있는 원소부터 하나씩 확인 · 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요 -> 최악의 경우 시간 복잡도: O(N) ▶ 예시 - 순차 탐색으로 특정 문자열의 위치 찾기 public class SequentialSerach { public static void main(String[] args){ String[] strings = {"a","b","c","d","e"}; String target = "d"; for(int i=0; i< strings.length; i++) if(strings[i].equals(target)) Sy.. 2021. 9. 6. [Algorithm] 정렬 알고리즘 (with 자바코드) '이것이 취업을 위한 코딩 테스트다 with 파이썬' 이라는 책을 공부 중입니다. 이 글은 해당 책의 내용 중 정렬 알고리즘 부분을 요약, 정리한 글입니다. 학습 목표 · 선택 정렬(Selection Sort) · 삽입 정렬(Insertion Sort) · 퀵 정렬(Quick Sort) · 계수 정렬(Count Sort) ✍ ,정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것이다. 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색(Binary Search)이 가능해진다. 즉, 정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하다. 선택 정렬(Selection Sort) 선택 정렬 알고리즘은 가장 원시적인 방법이다. ✍ 데이터가 무작위로 여러 개 있다고 가정하자. 가장 작은 데이터를 선택해 맨 앞에 .. 2021. 2. 26. 이전 1 2 3 4 다음 반응형
