youngseo's TECH blog

0. 문제 https://www.acmicpc.net/problem/22115 22115번: 창영이와 커피 커피는 종류별로 하나씩 준비되어 있기 때문에, 동일한 커피를 여러 개 마실 수 없음에 유의하라. www.acmicpc.net 1. 문제 해설 아래 힌트에 이 문구가 있다. 커피는 종류별로 하나씩 준비되어 있기 때문에, 동일한 커피를 여러 개 마실 수 없음에 유의하라. 그리고 위에도 볼드채로 '하나씩' !! 이라고 쓰여 있는데 이걸 놓치면 틀릴 수 있다. .. ㅠ 2. 문제 풀이 그래서 이 DP+냅색 문제를 두 가지 경우로 바꾸어서 이해해 보았다. 먼저, 만약 커피가 무제한으로 존재한다면? 아래와 같이 풀 수 있을 것이다. N, K = map(int,input().split()) C = list(ma..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/152995 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 생각 임의의 두 수 i, j가 있다. 만약 근무태도 점수[i] < 근무태도 점수 [j] 이고 동료평가 점수[i] < 동료평가 점수 [j] 인 경우가 한 번이라도 있다면 i 는 인센티브를 받지 못한다. 그게 아니라면 두 점수의 합이 높은 순으로 석차를 낸다. N = 10만이라면 → NlogN 알고리즘이 적합하겠다!! 문제 풀이 def solution(scores): wanho = sco..

0. 문제 사칙연산 1. 문제 풀이 백준의 행렬 곱셈 순서 문제와 유사한 문제이다. 처음에는 Greedy라고 생각하였다 . 하지만 DP! - 뒤에는 작은 수가, + 뒤에는 큰 수가 나와야 한다. 또한 순차적인 계산 방식이 아니므로 Greedy로 풀 수 없고, 행렬 곱셈 순서 문제처럼 step별로 계산하며 DP table로 상태를 계속 적어두어야 한다. INF = 987654321 def solution(arr): answer=0 num = (len(arr)+1)//2 DP_max = [[-INF] *(num+1) for _ in range(num+1)] DP_min = [[INF] * (num+1) for _ in range(num+1)] for i in range(num): DP_max[i][i]=in..

0. 문제 Z 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 1. 문제 설명 크기가 2^N X 2^N 모양 배열을 Z 모양으로 탐색하려고 할 때 R행 C열을 몇 번째로 방문하는지 찾아내는 문제이다. 규칙이 보이기 시작했고, 분할정복으로 채워나가며 추적하는 방법을 사용하려고 하였다. 2. 문제 구현 처음 시간초과 코드 N,R,C=map(int,input().split()) turn=1 def divide_and_conquer(x,y,size): global turn if y==R and x==C: p..

0. 문제 설명 궁금한 민호 1507번: 궁금한 민호 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 각각의 도시 사이에 이동하는데 필요한 시간이 주어진다. A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. 또, A와 B www.acmicpc.net 1. 문제 생각 플로이드 워셜의 응용으로, 플로이드 워셜의 완성본을 보고, 어떤 간선들이 실질적으로 쓰이는지에 대해 추적하는 문제이다. 따라서 그림에서 보이는 것처럼 직접적으로 가는 길의 가중치만을 표현하기 위해 '플로이드 워셜을 이용하여 건너 가는 것들'에 대한 값들은 0으로 바꾸어주면 된다. '-1'을 출력하는 것은 플로이드와샬로 더 짧은 거리로 갈 수 있는 거리가 있는데 '완성본'에서 그 짧은 거리가 반영되어..

0. 문제 설명 우체국 2285번: 우체국 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 0 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. 모든 A[i]를 www.acmicpc.net 1. 문제 생각 처음에는 맨허튼 거리와 같은 알고리즘을 생각했다. 각 마을에 포함되는 사람들의 수를 가중치처럼 여긴 후 ∑각 마을의 index * 사람들의 수/ ∑사람들의 수 로 해결하려고 했는데 한 번 틀렸다 😥 아래 데이터를 조금 더 생각해보면 이 아이디어가 통하지 않음을 알 수 있는데 아래 데이터로 한번 생각해보면 좋다! 6 1 8 8 ..

0. 문제 우수 마을 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 1. 문제 생각 트리에서의 DP 문제이다. 트리란 사이클이 없이 모든 정점이 연결되어있는 그래프로, 사이클이 없는 그래프이므로 정점의 개수가 V개이면 간선의 개수는 V-1개라는 특징을 갖는다. DFS+DP 로 트리에서의 DP를 해결할 수 있고 아래처럼 DP 테이블을 채우기 위해 계속해서 인접한 노드를 탐색하는 점에서 DFS가 강력하다! 2. 문제 구현 import sys sys.setrecursionlimit(10**6) def d..

0. 문제 같이 눈사람 만들래? 20366번: 같이 눈사람 만들래? 높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1 다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1 www.acmicpc.net 1. 문제 생각 4개를 뽑아서 대조하는 것으로 먼저 생각해볼 수 있다. 하지만 600C4(5억)는 2초 안에 못 들어오기 때문에 X 일단 N은 600이기 때문에 2초 안에 들어오려면 적어도 N^3까지는 가능하다. 우리가 4개를 뽑아 한 세트를 만든다고 하면 예를 들어 2 3 5 5 일 때 세트는 (1️⃣4️⃣, 2️⃣3️⃣)으로 1번째와 4번째 것이 하나의 세트가 되고 2번째와 3번째 것이 하나의 세트..