https://www.acmicpc.net/problem/14495 14495번: 피보나치 비스무리한 수열 피보나치 비스무리한 수열은 f(n) = f(n-1) + f(n-3)인 수열이다. f(1) = f(2) = f(3) = 1이며 피보나치 비스무리한 수열을 나열하면 다음과 같다. 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, ... 자연수 n을 입력받아 n번째 피보 www.acmicpc.net 유형 다이나믹 프로그래밍 문제 피보나치 비스무리한 수열은 f(n) = f(n-1) + f(n-3)인 수열이다. f(1) = f(2) = f(3) = 1이며 피보나치 비스무리한 수열을 나열하면 다음과 같다. 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, ... 자연수 n을 입력받아 n번째 피보..
Koala - 13기/코딩테스트 준비 스터디
https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 문제요약 거스름돈 금액이 입력으로 주어지고, 5원과 3원으로 해당금액을 만들 때, 만들수 있으면 동전의 최소 개수를, 만들 수 없으면 -1을 출력 문제해결 일단 5원을 가장 많이 사용하고 싶다고 생각할 수 있다. 예를 들어 23원을 계산한다고 했을 때, 5x4 + 3이 되는데 이는 안되므로 5x3 + 8이 된다. 이를 좀 더 바꿔서 dynamic programming을 적용시킨다고하면, 23은 5를 일단 하나 사용하고, 나머지 18(=23-5)을 만들수 있는 방법에 1을 더한다고 생각할 수 있다. 따라서 dp[i]를..
https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 코드 #include #include #include #include #include #include #include #include #include #include #include #define LL long long using namespace std; LL arr[500][500]; int main() { int n = 0; int m = 0; LL b = 0; cin >> n >> m >..
문제 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net Algorithm 해당 자연수가 몇 개의 제곱수의 합으로 나타낼 수 있는지 찾는 문제이다. 먼저, 해당 자연수가 제곱수라면 1개의 제곱수의 합으로 나타낼 수 있으므로 제곱수를 판단해야 한다. 따라서 math모듈을 이용하여 제곱수 판별 함수를 만들었다. #제곱수 확인 함수 제곱수면 1을 return. def decide(n): if math.sqrt(n)..
2×n 타일링 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 해결 이 문제는 다이나믹 프로그래밍을 사용해 풀 수 있습니다. 2xn 크기의 직사각형을 채우는 방법을 찾는 것을 큰 문제로 보고, 이를 2x(n-1)과 2x(n-2) 크기의 직사각형을 채우는 방법으로 나눕니다. 우선 입력값 N을 받고 dp 배열을 선언한 후 초기값을 설정하고, 2x1 크기의 직사각형을 채우는 방법은 1가지, 2x2 크기의 직사각형을 채우는 방법은 ..
그리디와 DP 아이디어를 이용해서 풀이한다. 현재위치에서 +n, x2, x3하였을 때 DP 값을 갱신해 나간다. # 그리디 + DP def solution(x, y, n): answer = -1 DP = [float('inf') for _ in range(y+1)] #init DP[x]=0 for i in range(x,y+1): if i+n
문제 설명 N개의 도시를 모두 순회하는 가장 짧은 비용을 찾아내는 TSP문제이다. 같은 도시는 중복으로 가면 안되기에 순열로 모든 조합을 나열하여 완전 탐색으로 풀었다. 1번 도시부터 N번 도시까지 걸리는 비용을 더하고 마지막으로 N번 도시에서 1번 도시로 돌아오는 비용을 더해주었다. Python3로 제출하면 시간초과가 났는데, PyPy3로 제출하니까 통과가 되어서 찾아봤는데, Python3의 실행 시간이 오래 걸려서 개선하고자 만든게 PyPy3인데 모든 경우에 PyPy3가 속도가 우세한 것은 아니라고 한다. 따라서 상황에 맞춰 적철하게 사용하라고 읽었는데, 아직 어떤 상황에 무엇을 적용해야 할 지는 모른다. 구현 from itertools import permutations n = int(input()..
1149번: RGB거리 (acmicpc.net) 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제유형 *다이나믹 프로그래밍 문제 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/258705 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 참조 https://tech.kakao.com/2023/12/27/2024-coding-test-winter-internship/ 2024 카카오 겨울 인턴십 코딩테스트 문제해설 안녕하세요, 카카오에서 계정시스템 개발을 맡고 있는 잭입니다.2024 카카오 채용 연계형 겨울 인턴십 코딩 테스트가 지난 11월 25일(토)에 5시간에 걸쳐 진행되었습니다. 문제를 이해하면 쉽게 해 tech...
문제 https://www.acmicpc.net/problem/5568 풀이 여러가지 방법으로 풀 수 있는데, 그 중에 순열을 사용했다. 주어진 수들을 순열로 조합을 해보고, 겹치는 수를 제외하면 된다. 겹치는 수는 집합(set)을 활용해 없애준다. 이후, 집합 내의 원소 개수(len)을 출력하면 된다. Code from itertools import permutations n = int(input()) k = int(input()) nums = [input() for _ in range(n)] new_nums = set() for c in permutations(nums, k): new_nums.add("".join(c)) print(len(new_nums))
규칙 - 문제 인증, 블로그 포스팅, 모의테스트 참여를 하지 않을시 각각 활동비에서 -1000원씩 차감 - 학회 활동이 끝난 후, 스터디 우수 참여자에게 차감된 활동비를 N분의 1로 나눠서 지급 - 스터디 우수 참여자 기준은 남은 활동비의 내림차순으로 정렬하여 가장 높은 참여자들로 선정 김강연 - kky9525 - kky9525 김경래 - future0610 - future0610 문채영 - mcy325 - 나는 푸딩 박준규 - junju404 - junju404 박해승 - parkhs21 - devhex 오상준 - highjune - en2014 이은석 - lanmecan - 컴공학생1 이해령 - haeryeong - haerr 정종문 - whdans4005 - Langerak 차정은 - jyc0011..
https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 유형 백트래킹 문제 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수 중에서 M개를 고른 수열 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다. 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출..
