Dev_from the Bottom

문제) 숫자 카드 게임 - 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임 1. 숫자가 쓰인 카드들이 N x M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다. 2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다. 3. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다. 4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다. 입력) - 첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. (1 ≤ N, M ≤ 100) - 둘..

그리디 : 당장 좋은 것만 선택하는 알고리즘 어떤 문제가 있을 때 단순하고 '탐욕적으로 문제를 푸는' 알고리즘 탐욕적 : 현재 상황에서 가장 좋은 것만 고르는 방법 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음 매우 다양한 유형이 있기 때문에 안기한다고 잘 풀 수 있는 유형이 아님 많이 접해보고 문제를 풀어보며 훈련을 해야 함 창의력, 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구함 예제 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때, 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러..

문제) 피보나치 수 5 - 피보나치 수는 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번째 피보나치 수를 구하는 프로그램을 작성하시오. 입력) - 첫째 줄에 n이 주어진다. n은 20보다 작거나 같은 자연수 또는 0이다. 출력) - 첫째 줄에 n번째 피보나치 수를 출력한다. 문제 링크) https://www.acmicpc..

BFS : Breadth-First-Search 너비 우선 탐색 가까운 노드부터 탐색하는 알고리즘 선입선출 방식인 Que 자료구조를 이용하는 것이 정석 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행함 알고리즘 동작 방식 1) 탐색 시작 노드를 Que에 삽입하고 방문 처리를 한다. 2) Que에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 Que에 삽입하고 방문 처리를 한다. 3) 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. BFS는 Que 자료구조에 기초한다는 점에서 구현이 간단 파이썬에서는 deque 라이브러리를 사용하는 것이 좋으며 탐색을 수행함에 있어 O(N)의 시간이 소요..