동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 작은 하위 문제로 나누어 푸는 알고리즘입니다.각 하위 문제는 한 번만 계산하고 그 결과를 저장하여, 동일한 하위 문제가 다시 나타날 때 재계산하지 않고 저장된 결과를 사용하는 것이 핵심입니다. 이로 인해 중복된 계산을 피할 수 있다는 장점을 가지고 있다!동적 계획법의 기본 아이디어 분할 정복: 문제를 여러 하위 문제로 나눈다.중복된 하위 문제: 여러 하위 문제가 여러 번 등장하는 경우가 많다.최적 부분 구조: 문제의 최적해는 하위 문제의 최적해로 구성된다.메모이제이션: 이미 계산한 하위 문제의 결과를 저장해 둔다. 동적 계획법의 구현 방식동적 계획법은 크게 두 가지 방식으로 구현할 수 있습니다.탑 다운(Top-Down)바텀 업(Bo..

다익스트라 알고리즘은 음수 가중치가 없는 그래프에서 동작하는 최단 경로 탐색 알고리즘으로 프림의 MST 알고리즘을 약간 변경한 형태이다. 다익스트라 알고리즘이 프림 알고리즘과 다른 두 가지 차이점은 다음과 같다. 프림 알고리즘은 경계로부터 최소 거리를 정점의 거리 값으로 설정하지만, 다익스트라 알고리즘은 시작 정점으로부터 각 정점까지의 전체 거리를 사용한다.다익스트라 알고리즘은 목적 정점이 나타나면 종료하지만 프림 알고리즘은 모든 정점을 방문해야 종료한다.그래프를 예시로 다익스트라 알고리즘의 동작에 대해 설명해 보겠습니다. 가중치가 부여된 그래프가 있습니다. 1를 시작 정점으로 잡고 퍼져나가는 것을 알아보겠습니다. 구현 (1) : 순차 탐색을 이용한 방법으로 노드의 개수가 N이라고 할 때 각 노드마다 최..

너비 우선 탐색이 시작 정점에서 시작하여 점차 탐색 범위를 넓혀 나가는 방식이라면, 깊이 우선 탐색은 시작 정점에서 시작하여 특정 경로를 따라 가능한 멀리 있는 정점을 재귀적으로 먼저 방문하는 방식이다.깊이 우선 탐색 깊이 우선 탐색은 시작 정점을 경계에 추가하는 것으로 시작한다. 너비 우선 탐색의 그림 예를 변형해서 가져왔다. 하나의 지점에서 시작하여 가능한 멀리 있는 정점에 도달하고 재귀하는 방식을 가진다.구현 깊이 우선 탐색은 두 가지의 코드를 사용할 수 있다. 1. Stack를 이용한 깊이 우선 탐색 2. 재귀 함수를 이용한 깊이 우선 탐색 이 두 가지가 있다. (1) #include #include #include using namespace std; bool visited[9]; vector ..

그래프 순회 문제란 특정 정점에서 시작하여 나머지 모든 정점을 방문하는 문제를 그래프 문제라고 한다.그래프 순회 문제는 그래프에서 특정 정점을 찾기 위한 용도로 사용할 수 있기 때문에 그래프 탐색 문제(graph search problem)라고 부르기도 한다. 오늘 알아볼 것은 여러 그래프 탐색 알고리즘 중 하나인 너비 우선 탐색에 대한 내용이다.너비 우선 탐색 너비 우선 탐색(BFS)은 시작 정점을 경계에 추가하는 것으로 시작한다.(1)의 검정 동그라미가 시작정점이라고 했을 때 퍼져나가는 모습을 표현했다. 그림 예 (1) (2) (3) (4) (5) 즉 이렇게 시작 지점에서 경계에 인접한 정점을 반복적으로 탐색하는 방법을 가진다.이렇게 되면 전체 그래프를 순회할 수 있게 된다.구현 #include #i..

탐욕 알고리즘이라고도 불리는 그리디 알고리즘이 있다.그리디 알고리즘은 항상 각 단계에 있어서 가장 좋을 거라 생각되는 선택을 한다. 다시 말해 이 선택이 전체적으로 최적해로 안내하게 될 거라는 바람을 가지고 부분적으로 최적인 선택을 한다. 그리디 알고리즘의 접근 과정selection procedure: 현재 상태에서 가장 greedy한 선택으로 해를 결정feasibility check: 결정한 해의 적절성 검사solution check: 해의 최적성 검사https://ko.wikipedia.org/wiki/%ED%83%90%EC%9A%95_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 탐욕 알고리즘 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 탐욕 알고리즘(Gr..

소수(Prime Number)란 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수다.https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98_(%EC%88%98%EB%A1%A0) 소수 (수론) - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 각각의 자리에 놓인 숫자와 소수점을 통해 나타낸 실수(小數)에 대해서는 소수 (기수법) 문서를 참고하십시오. 좌측은 소수, 우측은 합성수. ...소수란 1보다 큰ko.wikipedia.org소수만 구하는 알고리즘 풀이12부터 n까지 나눠보고 나머지가 0이 안나오게 되면 소수가 되는 방법이다. 이 경우에는 시간 복잡도가 O(n)이 된다.bool isPrime(int n) { for (int i = 2; i..

스택(stack) : 후입선출(LIFO:Last-In First-Out)의 방식(가장 최근에 들어온 데이터가 가장 먼저 나간다)을 이용한다. 스택에서 입출력이 이루어지는 부분을 스택 상단(stack top)이라 하고, 반대쪽인 바닥부분을 스택 하단(stack bottom)이라고 한다. 스택에 저장되는 것을 요소(element) 또는 항목이라고 한다. 스택에 요소가 하나도 없는 경우를 공백(empty) 상태라 하고 꽉 차서 더 이상 요소를 넣을 수 없는 상태를 포화(full) 상태라 한다.배열을 이용한 스택의 구현1차원 배열 stack[ ]스택의 크기 : 배열의 크기스택에 저장된 원소의 순서 : 배열 원소의 인덱스인덱스 0번 : 스택의 첫번째 원소인덱스 n-1번 : 스택의 n번째 원소변수 top: 가장 최..

이번 장에서는 디지털 컴퓨터 이전의 언어에 대해 알아볼 것이다. ℓ 디지털 컴퓨터 이전의 언어 주요 고급 언어의 계보의 그림이다. 10년 주기로 프로그래밍 언어의 발전사를 설명할 것이다. ℓ 1950년대 : 최초의 프로그래밍 언어 1950년 초반 당시의 프로그래밍은 주로 기계어로 작성되었으나, 뒤이어 어셈블리 언어가 탄생하였다. 어셈블리 언어는 기계어 코드를 대신할 기호나 연상기호를 사용할 수 있었다. 하지만 어셈블리 언어 역시 기계 의존적이며 자연언어와는 차이가 큰 구문을 사용했기에 때때로 저급 언어라 불린다. 이후 최초의 고급 언어는 1954년에서 1957년 사이에 IBM의 John Backus가 중심이 되어 만든 Fortran이다. Fortran 컴파일러는 효율적인 기계어 코드를 생성하여서 오랫동안..

ℓ 프로그래밍 언어란 무엇인가? 프로그래밍 언어에 대한 정의로 "기계가 읽을 수 있고 사람이 읽을 수 있는 형식으로 계산을 서술하기 위한 표기 체계이다." 이 정의에서 나타난 세 가지 주요 개념은 다음과 같다. ● 계산(computation) 튜링 머신이라는 수학적 개념을 가지고 형식적으로 정의할 수 있다. 컴퓨터가 수행할 수 있는 작업으로 간주한다. ● 기계가 읽을 수 있는(machine-readable) 단순한 구조를 가지고 있어야 한다. 제한된 시간 내에 번역이 가능하다. 프로그래밍 언어의 구조를 문맥 자유 언어로 제한한다. ● 사람이 읽을 수 있는(human-readable) 추상성을 제공해야 된다. 그래서 자연어를 닮게 된다. 소프트웨어 설계 기법을 지원하는 소프트웨어 개발 환경의 한부분이 되었..