모눈종이에 사각사각

🍎 [백준 2294] 동전2 문제 링크 https://www.acmicpc.net/problem/2294 ⚾ 코드 코드 1 n, k = map(int, input().split()) dp = [100001]*100001 coins = [int(input()) for _ in range(n)] coins.sort() for coin in coins: for now in range(1, k+1): if now % coin != 0: dp[now] = min(dp[now], dp[now-coin]+1) else: dp[now] = min(dp[now], now//coin) if dp[k] == 100001: print(-1) else: print(dp[k]) 코드 2 n, k = map(int, input()..

🍎 [백준 11727] 2×n 타일링 2 문제링크 https://www.acmicpc.net/problem/11727 ⚾ 코드 n = int(input()) dp = [0]*(n+1) dp[1] = 1 dp[2] = 3 for i in range(3, n+1): dp[i] = (dp[i-1]+(dp[i-2]*2)) % 10007 print(dp[n]) 🔔 해결 과정 & 깨달은 점 - 다음은 내가 문제를 풀면서 생각한 아이디어 이다. - 각 N은 (이전(N-1)의 경우의 수 + 2*1 타일 추가한 것) + (전전(N-2)의 경우의 수 + 2*2 타일 또는 2*1 타일 2개 추가한 것) 으로 이루어져 있다. - 새로 추가하는 타일 이외의 경우의 수는 이전의 N의 경우의 수에 포함되어 있기 때문에 따로 생각하..

🍎AWS EC2 인스턴스에 접속하기 이전 포스팅에서 AWS EC2 인스턴스를 만들었는데, 이번에는 만든 인스턴스에 접속해보고자 한다. 1. WinSCP 설치 - https://winscp.net/eng/download.php에 들어가서 winscp를 다운받는다. winscp란? - Windows용 그래픽 유저 인터페이스 SFTP 및 FTP 클라이언트 프로그램이고 오픈소스 프리소프트웨어 - 레거시 SCP프로토콜도 지원 - 이 프로그램을 사용하여 로컬 컴퓨터와 원격 컴퓨터 간에 안전하게 파일을 복사할 수 있다. 2. WinSCP 설정 2-1. 파일 프로토콜 -> SFTP 2-2. 호스트 이름 : 내 인스턴스의 public ip주소 - EC2에 들어가서 확인할 수 있다. 2-3. 포트번호 : 22 2-4. 사..

🍎 AWS 서버 구축하기 이번 포스팅에서는 AWS 서버를 구축하기 위한 과정을 알아보고자 한다. AWS란? - 아마존닷컴에서 개발한 클라우드 컴퓨팅 플랫폼 - 인터넷에 연결되어 있는 거대한 컴퓨터를 사용하는 것임! 1. AWS 가입하기 - 나의 경우는 이전에 생성해 놓은 계정이 있어서 새로 가입하지 않았다. 2. EC2 인스턴스 생성 시작 EC2란? Amazon Elastic Compute Cloud(Amazon EC2) 안전하고 크기 조정이 가능한 컴퓨팅 용량을 클라우드에서 제공하는 웹 서비스이다. 이용자는 높은 초기 비용, 유지 및 보수 등의 다양한 제약에서 벗어나서 단시간 안에 웹 서비스를 생성할 수 있다. - 검색 창에 EC2라고 치면 찾을 수 있다. 3. 지역 선택 - 지역은 한국이므로 서울(S..

🍎 개미 전사 🏀 문제 (문제 요약) 개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 식량 창고는 일직선으로 이어져 있다. 개미 전사는 식량창고를 선택적으로 약탈할 것이다. 인접한 식량 창고가 공격을 받으면 메뚜기 정찰병들에게 들킨다. 개미 전사는 정찰병에게 들키지 않고 최대한 많은 식량을 얻기를 원한다. ⚾ 코드 n = int(input()) store = list(map(int, input().split())) dp = [0]*n dp[0] = store[0] dp[1] = max(store[0], store[1]) for i in range(2, n): dp[i] = max(dp[i-1], dp[i-2]+store[i]) print(dp[n-1]) 🔔 해결 과정..

🍎 1로 만들기 🏀 문제 정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지 이다. a. X가 5로 나누어 떨어지면, 5로 나눈다. b. X가 3으로 나누어 떨어지면, 3로 나눈다. c. X가 2로 나누어 떨어지면, 2로 나눈다. 정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. ⚾ 코드 num = int(input()) INF = 1e9 dp = [INF] * (num+1) for i in range(2, num+1): if i == 1: dp[i] = 0 elif i == 2 or i == 3 or i == 5: dp[i] = 1 else: if i % 2 == 0: dp[i] = min(dp[i], dp[i..

🍎 Local 서버 구축하기 Bitnami를 활용해서 로컬 서버를 구축해보려고 한다. Bitnami(비트나미)란? 가상 어플라이언스 및 웹 애플리케이션, 개발 스택용 소프트웨어 패키지 및 설치 라이브러리 [Bitnami 다운 및 설치] 먼저 https://bitnami.com/stack/wamp/installer 에 가서 WAMP packaged by Bitnami를 다운받는다. WAMP(Windows/Apache/MySQL/PHP) - 윈도우 환경에서 아파치(Server), MySQL(DB), PHP(서버사이드)와 같은 웹 개발환경을 통합적으로 구축해주는 프로그램 설치가 잘 되었으면 다음과 같은 화면이 뜬다. 다음은 C:\Bitnami\wampstack-8.1.2-0 → manager-windows.e..

🍎 [백준 1260] DFS와 BFS 문제 링크 ⚾ 코드 from collections import deque # 정점의 개수 N(1 ≤ N ≤ 1,000) # 간선의 개수 M(1 ≤ M ≤ 10,000) # 탐색을 시작할 정점의 번호 V N, M, V = map(int, input().split()) graph = [[] for _ in range(N+1)] visited = [False]*(N+1) for _ in range(M): a, b = map(int, input().split()) # 양방향이기 때문에 리스트 두 군데 다 추가해주어야 한다. graph[a].append(b) graph[b].append(a) # 인접 리스트를 사용할 것이기 때문에 정렬이 필요함. for i in range(N..

이번 포스팅에서는 다이나믹 프로그래밍에 대해 다뤄보고자 한다. 다이나믹 프로그래밍은 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀는 알고리즘 기법이다. 특정 조건이 만족되는 문제에서 다이나믹 프로그래밍을 사용하면, 중복되는 연산을 줄일 수 있다. 특정 조건은 다음과 같다. 1. 큰 문제를 작은 문제로 나눌 수 있다. (최적 부분 구조) 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. (중복되는 부분 문제) 다이나믹 프로그래밍을 구현하는 방법은 크게 두 가지가 있다. 첫 번째는 Top-down 방식인 메모이제이션(Memoization) 기법이다. 메모이제이션은 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법이다. 메모..

🍎 Letter Combinations of a Phone Number 문제 링크 💿 문제 Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order. A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters. ⚾ 코드 def solution(digits): # 알파벳 매핑 alpha = [[], [], ['a', 'b', '..