wooHappening

그리디 알고리즘 - 탐욕법현재 상황에서 지금 당장 좋은 것만 고르는 방법 현재 선택이 나중에 미칠 영향은 고려하지 않는다. **그리디 알고리즘은 **기준을 알게 모르게 제시**해준다.**그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다.Ex) 큰 단위의 동전이 항상 작은 단위의 동전의 배수이다. 모든 문제에 적용할 수 없음 **바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적 해결 방법이 존재하는지 고민해봐라 → 다이나믹 프로그래밍, 그래프 알고리즘구현완전탐색, 시뮬레이션 문제완전 탐색 - 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 시뮬레이션 - 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 문제 유형파이썬..

문제상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, ..

내 풀이1. 목적지에서 시작하여 시작 지점까지 재귀 함수를 호출한다.2. 목적지로 올 수 있는 경우에 대해 최대값을 구하고 최대값에 현재 계단의 값을 더해 최대값을 구한다. Ex) 5번째 계단의 경우 3번과 4번에서 올 수 있으므로 둘 중 최대값을 구하고 5번째 계단의 값을 더해 최대값을 구한다. 3. 연속으로 세번 이동하는 경우에 대한 예외 처리를 해주기 위해 cnt 값이 3이 되면 0을 반환하게 한다.4. 목적지에 따라 오는 경우의 수의 최대값이 다르기 때문에 이를 고려하여 dp 테이블을 생성한다. 특정 목적지로 오기 위한 최대값이므로 다름 Ex) 4번에 도착하기 위한 2번의 최대값과 3번에 도착하기 위한 2번의 최대값이 다를 수 있음 몇 번째 계단인지랑, 연속으로 몇 번 이동했는지..

문제n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.입력첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.출력첫째 줄에 답을 출력한다.1차 시도 코드import sysN = int(sys.stdin.readline().rstrip())arr = list(map(int, sys.stdin..

문제세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.아래 그림은 원판이 5개인 경우의 예시이다.입력첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.출력첫째 줄에 옮긴 횟수 K를 출력한다.두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에..

문제재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.**** ****N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.입력첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k 출력첫째 줄부터 N번째 줄까지 별을 출력한다.내 풀이1. 반복문을 사용하여 각 행에 대하여 함수를 실행시킨다. 2. 각 행을 idx로 가정하고 인덱스가 특정..

1차 시도 - 실패from collections import dequeimport sysN = int(sys.stdin.readline().rstrip())# 스택 혹은 큐이므로 dequeue를 사용한다. dequeue = deque([deque() for i in range(N)])# 스택인지 큐인지 typeList = list(map(int, sys.stdin.readline().split()))# 각 자료구조에 어떤 원소가 들어있는지 dataList = list(map(int, sys.stdin.readline().split()))# 넣을 때는 큐나 스택이나 뒤로 들어가기 때문에 조건 검사 필요 없음 for i in range(N) : dequeue[i].append(dataList[i])# ..

문제숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.입력첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,0..

문제알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.1. 길이가 짧은 것부터2. 길이가 같으면 사전 순으로단, 중복된 단어는 하나만 남기고 제거해야 한다.입력첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.출력조건에 따라 정렬하여 단어들을 출력한다.sort 함수를 사용하면 쉽게 풀 수 있다.N = int(input())setA = set()listA = list()for i in range(N) : data = input() setA.add(data)for i in setA : l..