김미썸코딩

2. 플로이드 워셜 알고리즘 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. 플로이드 워셜(Floyd-Warshall) 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다. 다만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다. 플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장한다. 플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형에 속한다. 각단계마다 특정한 노드 k를 거쳐 가는 경우를 확인한다. a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사한다.점화식은 다음과 같다. $$D_{ab} = min(D_{ab}, D_{ak} + D_{kb})$$ #include..

최단경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미한다. 다양한 문제 상황이 있다. 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현한다. 지점 간 연결된 도로는 그래프에서 간선으로 표현한다. 1. 다익스트라 알고리즘 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다. 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다. (현실 세계의 도로(간선)은 음의 간선으로 표현되지 않음) 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류된다. 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복하기 때문. 알고리즘의 동작과정 출발 ..

다이나믹 프로그래밍은 중복되는 연산을 줄이기 위한 방법이다. 대표적인 예로 피보나치 수열이 있다. 탑다운 방식과 보텀업 방식이 있다. 탑다운 방식은 재귀를 사용하고, 보텀업 방식은 반복문을 사용한다. [어떤 문제에 적용이 될까?] 알고리즘 문제를 풀때, 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요하다. 가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토할 수 있다. 다른 알고리즘으로 풀이 방법이 떠오르지 않으면 다이나믹 프로그래밍을 고려해보자. 일단 재귀함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 (탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 코드를 개선하는 방법을 사용할 수 있다. 일반적인 코딩 테스트 수준에서는 기본..

이렇듯 DFS는 스택(또는 재귀), BFS는 큐를 사용한다는 차이점이 있다.

[출처] c++ new의 사용법, malloc과의 차이(free, delete) (tistory.com) c++ new의 사용법, malloc과의 차이(free, delete) ※컴퓨터의 메모리 구조를 알고 보시면 더 쉽게 이해할 수 있습니다. 메모리 구조 보러가기(클릭) 프로그램을 만들다 보면 상황에 따라 추가적인 메모리 공간을 실시간으로 확보해야 할 경우 hwan-shell.tistory.com 프로그램을 만들다 보면 상황에 따라 추가적인 메모리 공간을 실시간으로 확보해야 할 경우가 많습니다. 예를 들자면 채팅 대화방에 2명이 접속해 있는데 3명이 더 추가 접속을 했다거나 컴퓨터에 자료를 추가적으로 입력해 저장해야 하거나 등.... 여러가지 경우가 있습니다. 이것은 컴퓨터의 소프트웨어 사용시 변화가 ..

1. 시간 복잡도 : 알고리즘 실행 속도 2. 공간 복잡도 : 알고리즘이 사용하는 메모리 사이즈 (요즘은 잘안함) 알고리즘의 시간복잡도 주요요소는? 반복문! 알고리즘 성능 표기법 Big O (빅-오) 표기법 : O(N) 알고리즘 최악의 실행시간을 표기 가장 많이/일반적으로 사용함 아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미이기 때문 Ω (오메가) 표기법 : Ω(N) 오메가 표기법은 알고리즘 최상의 실행시간을 표기 Θ (세타) 표기법 : Θ(N) 오메가 표기법은 알고리즘 평균 실행 시간을 표기 시간 복잡도 계산은 반복문이 핵심 요소임을 인지하고, 계산 표기는 최상, 평균, 최악 중, 최악의 시간인 Big-O 표기법을 중심으로 익히면 됨 대문자 O 표기법 입력 n에 따라 결정되는 시간 복잡도 ..