안녕

0. 문제 링크 https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 1. 풀이 방법 https://pacific-ocean.tistory.com/203 [백준] 2294번(python 파이썬) 문제 링크: https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 ..

0. 문제 링크 https://www.acmicpc.net/problem/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net 1. 풀이 방법 일단 9, 3, 1로 때리는 순서는 순열을 이용해서 풀었다. 점화식을 얘기하자면 scv의 피가 1, 1, 1이라고 가정했을 때, 한 대만 때려도 된다. 그러면 피가 9, 3, 1 일 때는? 이때도 한 대만 때려도 된다. 결론적으로 피 i, j, k가 있을 때는 피가 i - 9, j - 3, k - 1 때보다 한 대만 더 때리면 된다는 뜻! (물론 순열을 이용해서 모든 경우의..

0. 문제 링크 https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 1. 풀이 방법 보통 n * (m + 1)의 배열을 만들어서 처리하는 것 같은데, 나는 그러고 싶지 않았다. BFS와 흡사하지만 DP다. 따라서 m + 1을 n번 반복하는 식으로 풀었다. 최종적으로 n번 반복 후에 dp에 남아있는 값들 중 하나가 결과가 된다. 배열 대신에 check를 사용하여 이미 설정한 볼륨은 넣지 않았고, deque를 사용..

0. 문제 링크 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 1. 풀이 방법 코드에 모든 설명이 있음. 2. 코드 n, k = map(int, input().split()) board = [[b for b in map(int, input().split())] for _ in range(n)] w, v = [0] + [a for a, b in board], [0] + [b fo..

0. 문제 링크 https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 1. 풀이 방법 만약 2~4까지 펠린드롬이라고 가정해보자. 그러면 1~5까지 펠린드롬인지는 어떻게 알 수 있을까? 바로 1번째와 5번째가 맞는지 비교하고, 2~4가 펠린드롬인지 확인하면 되는 것이다. 따라서 n~m까지 펠린드롬인지 확인하기 위해서는, n-1~m-1이 펠린드롬인지 확인하고, n번째와 m번째가 펠린드롬인지 확인하면 된다. 숫자가 하나만 있는 경우는 무조건 펠린드롬이고, 2개가 있는 경우에는 맞는지 확인만 하..

0. 문제 링크 https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 1. 풀이 방법 i에서 j로 가는데, 기존에 점프한 횟수보다 i + 1이 더 적으면 가면 된다. dp 배열은 inf로 초기화 해야 한다. 이런 식으로 모든 i에 대해서, 점프할 수 있는 j를 찾아가며 초기화를 하면 결국 최소 횟수가 나오게 된다. 2. 코드 import sys n = int(sys.stdin.readline().strip()) board = [b for ..

0. 문제 링크 https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 1. 풀이 방법 그냥 전형적인 DP 문제이다. 보통 DP는 점화식만 잘 세우면 끝인데, 이 문제도 그렇다. dp 변수는 1부터 시작하지만, 사탕이 들어있는 맵인 board는 0부터 시작한다. 이거는 맞춰주면 된다. 참고로 대각선으로는 갈 필요가 없다. 왜냐하면 오른쪽 -> 아래로 가는 것이 대각선으로 가는 것인데, 이 방법이 대각선으로 직통으로 가는 것보다 훨씬 사탕..

문제)

문제)

1. BST (Binary Search Tree)란? 아마 자료구조 시간에 다 배웠으실 텐데요. BST는 ordered set (순서 가능한 집합)에 속한 원소(key)로 이루어진 이진 트리이고, 다음의 조건을 만족합니다. 각각의 노드는 하나의 unique한 key를 갖고 있다. node의 left subtree는 node의 key보다 작거나 같다. node의 right subtree는 node의 key보다 크거나 같다. 생각보다 간단하죠? 우리의 목적은 BST에서 검색하는 key와 같은 원소를 찾는 average time을 최소화하는 데 있습니다. 만약에 각 원소가 검색될 확률이 모두 동일하다면, 트리의 높이는 낮을 수록, 그리고 좌우의 높이 차가 덜 클수록 효율적입니다. 하지만 만약에 각 원소가 검색..