코딩테스트 준비하기
1.[알고리즘] 그리디(Greedy) / 구현(Implementation)
"이것은 취업을 위한 코딩테스트다 with 파이썬" 을 정리한 글 입니다.'현재 상황에서 지금 당장 좋은 것만 고르는 방법'사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형.'가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해
2.[알고리즘] DFS/BFS - 그래프 탐색
탐색: 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정DFS와 BFS를 제대로 이해하려면 기본 자료구조인 스택과 큐에 대한 이해가 전제 되어야 한다. 삽입(Push) : 데이터를 삽입한다.삭제(Pop) : 데이터를 삭제한다.오버플로 : 자료구조가 수용할 수 있는 데
3.[알고리즘] 정렬(Sorting) - 연속된 데이터를 기준에 따라 정렬한다
정렬 : 데이터를 특정한 기준에 따라서 순서대로 나열데이터를 정렬하면 이진 탐색이 가능해진다.정렬 알고리즘은 다양하지만 여기서는 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 만 설명한다.또한 오름차순 정렬을 수행한다고 가정한다. 내림차순 정렬은 오름차순 정렬을 수행한
4.[알고리즘] 다이나믹 프로그래밍(Dynamic Programming) - 한 번 계산한 문제는 다시 계산하지 않는다
다이나믹 프로그래밍(동적 계획법) > 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 알고리즘이다. 조건 및 필수 개념 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제들이 반복돼 나타나고 사용되며
5.[알고리즘] 이진 탐색(Binary Search) - 탐색 범위를 반으로 좁혀가며 빠르게 탐색
순차 탐색 이진 탐색에 대해 알아보기 전에 가장 기본 탐색 방법인 순차 탐색에 대해 먼저 이해할 필요가 있다. > 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 시간복잡도: O(n) 보통 정렬되지 않은 리스트에서
6.[알고리즘] 최단 경로(Shortest Path) - 다익스트라(Dijkstra) 알고리즘
최단 경로(Shortest Path) > 가장 짧은 경로를 찾는 알고리즘이다. 그리디 알고리즘 및 다이나믹 프로그래밍 알고리즘의 한 유형으로 볼 수 있다. 최단 경로 출력 문제 보다는 단순히 최단 거리 출력하는 문제가 많이 출제된다. 최단 거리 알고리즘 중 다
7.[알고리즘] 최단 경로(Shortest Path) - 벨만포드(Bellman-Ford) 알고리즘
다익스트라(Dijkstra)벨만-포드(Bellman-Ford)플로이드-와샬(Floyd-Wrasahll)벨만-포드 알고리즘은 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이다. 다익스트라와 달리 간선의 가중치가 음수인 경우에도 최단 거리를 구할 수 있다.
8.[알고리즘] 최단 경로(Shortest Path) - 플로이드 워셜(Floyd-Warshall) 알고리즘
모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용하는 알고리즘이다.시간 복잡도: O(n3)2차원 리스트에 '최단 거리' 정보를 저장 (다익스트라는 1차원 리스트 활용)플로이드 워셜 알고리즘은 다이나믹 프로그래밍 (다익스트라는 그리디 알고리즘
9.[BOJ] 1753번: 최단경로 - JAVA(자바)
\[ 1753번: 최단경로 ] 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.첫 번째 아이디어: 다익스트라 알고리즘을 사용하여 최단 경로를 구한다.다익스트라 알
10.[자료구조] HashMap 함수
Map 인터페이스의 한 종류로써 key와 Value 값으로 데이터를 저장하는 형태이다. 또한, 해싱(Hashing)이란 검색방법을 사용하여 많은 양의 데이터를 검색하는데 있어 뛰어난 성능을 보인다.HashMap에서 주의할점이 있다면 map 데이터를 등록할 떄, key
11.[알고리즘] 크루스칼 알고리즘(Kruskal Algorithm)
크루스칼 알고리즘은 그래프에서 최소 비용 신장 부분 트리(최소 신장 트리: Minimum Spanning Tree)를 찾는 알고리즘이다.크루스칼 알고리즘은 기본적으로 그리디한 선택을 바탕으로 알고리즘을 진행한다.주어진 그래프의 모든 간선에 대해, 간선의 연결비용을 낮은