youngseo's TECH blog

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; #..