본문 바로가기

Algorithm18

[python/백준 2747] 피보나치 수 문제 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그다음 2번째부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오. 접근 피보나치 수열의 1,2 번째 수는 1로 정해져 있으니 배열을 만들어 1, 1을 넣은 후 n-1번째 배열에 도달할 때까지 앞의 두 수를 더하여 배열을 늘려나간다.(인덱스는 0부터 시작하니까!) 코드 n=int(input().. 2024. 1. 6.
동적 계획법(Dynamic Programming, DP) Dynamic Programming의 Programming은 '해답을 구하기 위해 배열(테이블)을 구축한다.'는 뜻이다. 이름에서 알 수 있듯이, 동적계획법은 배열을 이용하여 해답을 구하는, 상향식(bottom-up) 접근방법이다. DP 알고리즘 1. 문제의 입력사례에 대해서 해답을 계산하는 재귀 관계식(recursive property) 세우기. 2. 작은 입력사례부터 먼저 해결하는 상향식 방법으로 전체 입력사례에 대한 해답을 구하기. DP 알고리즘은 위와 같은데, 어려우니 피보나치수열을 예로 들어 설명해 보겠다. 피보나치수열은 첫째 및 둘째 항이 1이고 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. n번째 수열을 구하기 위해 n-1번째, n-2번째 수열을 더하면 되므로, 이를 코딩하면 다음과 .. 2024. 1. 6.
[c++/백준 24511] queuestack 문제 한가롭게 방학에 놀고 있던 도현이는 갑자기 재밌는 자료구조를 생각해 냈다. 그 자료구조의 이름은 queuestack이다. queuestack의 구조는 다음과 같다. 1번, 2번, ... , N번의 자료구조(queue 혹은 stack)가 나열되어 있으며, 각각의 자료구조에는 한 개의 원소가 들어있다. queuestack의 작동은 다음과 같다. x0을 입력받는다. x0을 1번 자료구조에 삽입한 뒤 1번 자료구조에서 원소를 pop한다. 그때 pop 된 원소를 x1이라 한다. x1을 2번 자료구조에 삽입한 뒤 2번 자료구조에서 원소를 pop한다. 그때 pop 된 원소를 x2이라 한다. ... xN−1을 N번 자료구조에 삽입한 뒤 N번 자료구조에서 원소를 pop한다. 그때 pop 된 원소를 xN이라 한다. .. 2023. 1. 20.
[c++/백준 2164] 카드2 문제 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다. N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그.. 2023. 1. 10.
[c++/백준 10828] 스택 문제 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 다섯 가지이다. push X: 정수 X를 스택에 넣는 연산이다. pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 스택에 들어있는 정수의 개수를 출력한다. empty: 스택이 비어있으면 1, 아니면 0을 출력한다. top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. 접근 명령의 수를 입력받아 그만큼 반복문을 돌리며, 조건문을 이용하여 모든 명령에 대해 반응할 수 있도록 코드를 작성한다. 코드 #include #include using namespac.. 2023. 1. 9.
[c++/백준 10845] 큐 문제 정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 여섯 가지이다. push X: 정수 X를 큐에 넣는 연산이다. pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 큐에 들어있는 정수의 개수를 출력한다. empty: 큐가 비어있으면 1, 아니면 0을 출력한다. front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다 접근 명령의 수를 입력받아 그만큼 반복문을 돌리며, 조건문을 이용하여 모든 명령에 대해 반.. 2023. 1. 9.

티스토리툴바