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번째 것이 하나의 세트..
0. 문제 양팔저울 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 1. 문제 해석 추의 종류와 구슬의 종류가 주어졌을 때 추들로 구슬들의 무게를 판단할 수 있는가 없는가를 물어보는 문제이다. 예를 들어 예제 2를 보면 추 1,4kg으로 알 수 있는 구슬의 무게는 1,4,3,5 kg에 해당한다. 양팔 저울의 양쪽에 놓을 수 있다는 것을 주의하자! 따라서 Knapsack으로 DP를 채워나간다. DP[추의 종류][구슬 무게] = 가능?불가능? 으로 나타낼 수 있고 DP table을 채우는 것은 for문 추의 무게로..
0. 문제 K번째 수 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 1. 문제 생각 일단 "정렬"에 대한 직접적인 언급이 있으나 정렬할 수 없다. N이 최대 10**5인데 NlogN을 수행할 수 없으므로! 그리고 나서는 A에 대한 B를 직접 만들어보았다. B=[1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 8, 8, 8, 8, 9, 9, 9, 10, 10, 10, 10, ...] 여기에서 규칙을 찾을 수 있다! 바로 각 숫자가 자신의 "약..
0. 문제 데이터 체커 22942번: 데이터 체커 데이터가 조건에 맞는다면 YES, 조건에 만족하지 않는다면 NO를 출력한다. www.acmicpc.net 1. 문제 생각 기하 골드 문제로, 처음부터 괄호 문제랑 연관해서 떠올리지는 못했다..🤦 힌트도 오히려 수학 문제처럼 줘서 더 헷갈릴 수 밖에 없었는데, 역시 백준에서 수학 문제가 나오면 자료구조나 알고리즘적 접근을 더 의심해보는 게 좋은 방향인 것 같다. 이 문제는 괄호 문제와 비슷하게 해결할 수 있다. ( ( ) ) 괄호들이 색깔들로 주어진다고 응용해서 생각하면 되고, 주어지는 상황 속에서 같은 모양의 '('이 들어갔다면 같은 모양의 ')'가 들어가 '('를 상쇄시켜주면 된다는 점에서 stack이라는 구조를 사용한다는 걸 떠올릴 수 있다. 2. 문..
0. 문제 공항 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 1. 문제 생각 공항 도킹에 대한 한국어 풀이가 생각보다 이해가 잘 되지 않아 예제를 계속 읽고서야 이해가 되었다. 차라리 밑에 예제를 예제 2 : [2][1][3][?] 로 풀이 방법을 줬으면 더 이해가 잘 되었을텐데 😥 아무튼 이 문제의 핵심은 "i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후..
0. 문제 문자열 화폐 17828번: 문자열 화폐 첫 번째 줄에 문자열의 길이 N(1 ≤ N ≤ 5,000,000)과, 문자열의 가치를 나타내는 정수 X(1 ≤ X ≤ 500,000,000)가 공백으로 구분되어 주어진다. www.acmicpc.net 1. 문제 생각 어떤 문자열을 채워나가는 과정이다. 간단하게 증명하여 AAA 특정 문자열 ZZZ로 그리디 과정을 거친다는 것을 알 수 있다. 아래 테스트케이스를 생각하면서 풀면 도움이 되었다. 6 50 AAAAZZ 6 55 AAAAYZ 6 156 ZZZZZZ 2. 문제 구현 import sys input=sys.stdin.readline N,X=map(int,input().split()) if N*26X: print("!") else: List=['A' fo..
0. 문제 두 로봇 15971번: 두 로봇 2018년 강원도에서 새로운 동굴이 발견되었다. 이 동굴에는 총 N개의 넓은 방이 존재하며 좁은 통로로 서로 연결되어 있는 것으로 밝혀졌다. N개의 방은 1번부터 N번까지의 번호를 붙여 1번 방, 2번 www.acmicpc.net 1. 문제 생각 한점 -> 여러 점의 최단거리를 구현할 수 있는 다익스트라를 사용했다. 다만 다익스트라 q에 넣을 때 (cost, 노드, 지금까지 나온 경로 중 최댓값)으로 가져가면서 풀었다. 입력값으로 받은 start부터 -> 모든 다른 점까지의 최단거리를 구한 후 이렇게 진행하면서 거쳐가게 되는 간선 중 가장 큰 가중치를 가지는 것들을 함께 가져갔다. 이후 start로부터 end까지의 거리인 distance[end]에서 max_di..
0. 문제 트리 4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 1. 문제 생각 전위순회, 중위순회, 후위순회의 핵심은 규칙과 재귀이다. 재귀에서도 사실상 어디에서 재귀로 진입하는가(반환하는가) 가 가장 중요하다. -> 기초 설명 위 문제에서도 전위, 중위 순회일 떄 규칙적으로 왼쪽/오른쪽으로 빠지는 것이 규칙적으로 진행됨을 알 수 있다. 따라서 recursion을 전위, 중위 순회에 따라 root 노드 -> left 노드 -> right 노드로 들어가도록 구현하고 if (currentNode){ ..
0. 문제 후보 추천하기 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대 www.acmicpc.net 1. 문제 생각 1
0. 문제 별 찍기 - 11 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 1. 문제 생각 규칙을 유추해보는 과정, 패턴을 파악하는 것이 그리 어렵지는 않았으나 마음처럼 뭉탱이로 구현할 수 없어 생각을 좀 더 했던 것 같다! 재귀적으로 패턴이 반복되는 것이 보여서 아래 종이에서 보이는 것처럼 12를 채우기 위해 6으로 쪼개서 나아가고 다시 6을 채우기 위해 3으로 쪼개서 나아가는 방법으로 분할정복 재귀를 써야겠다고 생각했다. 평소 그리는 분할정복의 로직은 아래와 같다. def div_conquer(): #가장 밑 분할 노드 도착했을 때 return #분할해서 ..
0. 문제 캠프 준비 16938번: 캠프 준비 난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다. www.acmicpc.net 1. 문제 생각 처음에는 투포인터일까? 싶었다. 하지만 투포인터는 각 요소가 모두 다를 때 효율적인데 입력값에서 배열이 [10, 10, 20, 10, 40] 으로 들어온다면 이는 별 효율이 없을 것 같았다. 이후 입력값이 고작 N= L and sum(List) = X: # print(List) ans+=1 #return하면 안됨 . => 한 번 더 가야할 수도 있으니까 for i in range(node+1, N): # 1 ~ N 까지 if not visited[i]: # 중복 확인 visited[i]=1 backtracking(i, visited,Lis..
0. 문제 스카이라인 쉬운거 1863번: 스카이라인 쉬운거 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫 www.acmicpc.net 1. 문제 생각 처음에는 스카이라인이라고 해서 라인스위핑이겠거니 하고 달려들었다! 하지만 예제를 보면 처참히 깨질 수 있는데.. 하나씩 순차적으로 파악하는 형태의 로직이 아니다. 즉, 앞에서의 상황이 뒤에 의존될 수 있다. 입력값에서 주어지는 것은 '스카이라인의 고도가 바뀌는 지점의 좌표 x와 y' 이다. 즉, 이 곳에서는 무조건! 고도가 바뀌어야 한다. 그렇다면 위 그림의 상황을..
1. 문제 개미 3048번: 개미 T초가 지난 후에 개미의 순서를 출력한다. 첫 번째 개미 그룹은 왼쪽에서 오른쪽으로 움직이고, 두 번째 그룹은 반대 방향으로 움직인다. www.acmicpc.net 2. 문제 생각 처음에는 규칙을 찾으려고 했다. T가 몇 번일 때 바뀌는 것과 바뀌지 않는 것들이 몇 번인지를 기준으로 찾아서 구현하려고 하였다. 이후 다시 보니 아래의 두 힌트가 명시적으로 N1과 N2가 굉장히 작고 T도 50밖에 되지 않아 빡구현이겠구나 하고 생각하였다. 3. 문제 풀이 N,M=map(int,input().split()) A=list(input()) B=list(input()) T=int(input()) start=A[::-1]+B for _ in range(T): flag=False; #..
