문제 https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 다이나믹 프로그래밍 알고리즘 문제이다. 코드 #include using namespace std; int N = 0; int M = 0; int str[1000][1000] = { 0, }; int main(){ cin >> N >> M; for (int i = 0; i str[i][j]; } } int sum[3] = { 0, }; for (int i = 0; i = sum[..
Koala - 12기/코딩테스트 준비 스터디
https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 알고리즘 분류 구현 시뮬레이션 문제 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기를 크기가 N×N인 격자에서 연습하려고 한다. 격자의 각 칸에는 바구니가 하나 있고, 바구니는 칸 전체를 차지한다. 바구니에 저장할 수 있는 물의 양에는 제한이 없다. (r..
https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 코드 A=input() B=input() dp=[[0]*1001 for _ in range(1001)] ans=0 for i in range(1, len(A)+1): for j in range(1, len(B)+1): if A[i-1]==B[j-1]: dp[i][j]=dp[i-1][j-1]+1 else: dp[i][j]=max(dp[i-1][j],..
문제 https://www.acmicpc.net/problem/15486 풀이 퇴사날 얻을 수 있는 가장 큰 이익은 다이나믹 프로그래밍을 활용하여 각 날짜까지 얻을 수 있는 최대 이익을 구하면 된다. 각 날까지 얻을 수 있는 이익을 0으로 초기화 시킨 배열 dp를 생성한다. 첫 날부터 일정 상담 시간 이후에 얻을 수 있는 금액을 구한다. 상담 종료 일정에 맞춰 그날 얻을 수 있는 총 금액을 구한다. 상담 시작일 이전까지 얻을 수 있는 최대 이익에 현재 상담 이익을 더하여 업데이트 한다. 가장 큰 이익을 출력한다. 코드 N = int(input()) chart = [list(map(int, input().split())) for _ in range(N)] dp = [0 for _ in range(N+1)]..
문제 https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 풀이 최대 상자의 개수를 구하려면 다이나믹 프로그래밍을 활용한 최장 증가 부분 순열을 구현하면 된다. 전체 상자의 개수만큼 1로 이루어진 배열 dp를 생성한다. 두 번째 수부터 검사를 시작한다. 자신(i)보다 앞에 있는 수들(j) 중 작은 것이 있다면, 자신(i)의 dp와 해당 수(j)의 위치에 저장된 dp값 + 1을 비교하여 더 큰 값으로 갱신한다. 이중 반복문을 모두 돌면 dp에 저장된 값들 중 ..
https://school.programmers.co.kr/learn/courses/30/lessons/150368 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 할인율을 적용할때, Dfs을 이용하여 풀 수 있습니다. 또한 Comparable을 이용해 리턴할 리스트의 1번째값들이 정답이 되도록 정렬하였습니다. import java.util.*; class Solution { static class Service implements Comparable{ int num; int price; public Service(int num, int price) { t..
https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지이다. 1. X가 3으로 나누어 떨어지면, 3으로 나눈다. 2. X가 2로 나누어 떨어지면, 2로 나눈다. 3. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 예제 풀이 n의 크기가 그다..
https://www.acmicpc.net/problem/25706 문제 코드 #include #include using namespace std; int main() { int N = 0; cin >> N; vector v1; vector ans(N); int num = 0; for (int i = 0; i > num; v1.push_back(num); } for (int i = N-1; i >=0; i--) { if (i == N - 1) { ans[i] = 1; } else { if (v1[i] == 0) { ans[i] = ans[i + 1] + 1; } else { if (i + v1[i] + 1 >= N) { ans[i] = 1; } else { ans[i] = ans[i + v1[i] + 1..
https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 예제 입력 1 2 예제 출력 1 1 예제 입력 2 10 예제 출력 2 3 힌..
문제 풀이 두 수열의 부분 수열 중 가장 긴 공통 부분 수열을 찾는 문제이다. 2차원 배열의 행과 열을 각각의 수열로 생각하고 배열을 읽어 나간다. 문자열1[i]와 문자열2[j]가 같다면 i와 j 모두 증가시키고, LCS의 길이를 1 증가 시킨다. 다르다면 지금까지 가장 큰 LCS의 길이를 가져온다. 배열의 인덱스를 벗어나는걸 방지하려고 i와 j를 1부터 시작했고, 그래서 A[i] == B[j]가 아닌 A[i - 1] == B[j -1]이라고 작성하였다. 코드 #include #include #include #include #include using namespace std; string A, B; int arr[1001][1001]; int main() { cin >> A >> B; for (int i..
https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 문제 문제 해석 처음에는 순열을 이용하여 해결하면 된다 생각했지만 자기 자신과 같은 조합을 허용하여 나타내야 하기 때문에 백트래킹을 사용하여 해결해야한다. 코드 def go(start): if len(tmp) == m: print(*tmp) return for i in range(start, n): tmp.append(Str[i]) go(i) tmp.pop() n, m = map(int,..
문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 입력받은 도시의 정보에서 치킨집과 집의 위치를 찾아 리스트에 저장한다. itertools의 combinations함수를 이용하여 전체 치킨집 중 m개의 치킨집을 선택한 조합을 comb에 저장한다. 각 집마다 m개의 치킨집 중 치킨 거리가 가장 작은 값을 dist에 더해준다. 모든 집을 확인한 후 새로운 리스트에 dist를 넣어준다. (dist = 도시의 치킨 거리)..
