투투

www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 접근 처음에 DFS로 탐색을 하여 관계의 합을 구하려고 했다. 하지만 스택을 이용해 풀면 관계의 합이 최소가 되지 않는다는 것을 알게되었다. 따라서 근접한 이웃 먼저 탐색을 하는 BFS로 풀어 통과가 되었다. 로직은 똑같은데 스택을 큐로만 바꿔주었다. 구현 사람의 수와 관계의 수를 입력받아 트리를 구성하였다. N, M = map(int, input().split(..

문제 루트 없는 트리가 주어진다. 이때 트리의 루트를 1이라고 정했을 때 각 노드의 부모 노드를 구하라 입력 첫째 줄에 노드의 개수가 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 입력된다. 출력 2번 노드부터 부모 노드 번호를 출력한다. 접근 트리를 이해하고자 문제를 풀었다. 기본적으로 트리는 데이터를 삽입, 삭제하는 기능보다 계층적 관계를 표현하기 위한 자료구조이다. 이러한 계층적 관계를 파이썬으로 어떻게 구현해야 할지 익혔다. 이 문제에서는 2차원 리스트를 활용하였다. 바깥의 큰 리스트에 포함되어있는 1차원 리스트는 자신의 자식노드 번호를 담고있다. 문제에서 1번이 루트노드라고 정했기 때문에 1번에 들어있는 자식노드부터 탐색을 진행하여 각각의 부모노드를 구하도록 하였다. 탐색..

문제 단어 수학 문제는 N개의 단어로 이루어져 있으며 각 단어는 알파벳 대문자로만 이루어져있다. 이때 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합한다. 이때 합이 최대가 되도록 만들어라. 입력 첫째 줄에 단어의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 입력된 모든 단어에 포함되어 있는 알파벳은 최대 10개이며 수의 최대 길이는 8이다. 출력 첫째 줄에 최대값을 출력한다. 접근 처음에 접근했던 방식은 문자열의 길이가 큰 것의 앞자리부터 숫자를 매기는 것이었다. 하지만 어떻게 구현을 해야할지 감이 잡히지 않았다 그래서 구글링을 해본 결과 아래의 풀이가 흥미로웠다. suri78.tistory.com/183 [백준알고리즘] 1339번: 단어 ..

문제 길이가 64cm인 막대가 있다. 이 막대기를 잘르고 붙여서 Xcm인 막대를 만들려고한다. 막대를 자르는 가장 쉬운 방법은 절반으로 자르는 것이다. 막대는 다음과 같은 과정을 거쳐서 자른다. 1. 가지고있는 막대의 합이 X보다 크면 아래와 같은 과정을 반복한다. 1-1 가지고있는 막대 중 길이가 가장 짧은 것을 절반으로 자른다. 1-2 위에서 자른 막대 중 하나가 X보다 크거나 가타면 자른 것중 하나를 버린다. 2. 남아있는 모든 막대를 풀로붙여서 Xcm를 만든다. 몇 개의 막대로 Xcm를 만들 수 있는지 구하라. 입력 첫째 줄에 64이하의 자연수 X가 입력된다. 출력 Xcm 만들기위해 몇 개의 막대가 필요한지 출력한다. 비트연산자를 활용하는 방법을 공부하였다. 이를 어떻게 활용할 수 있을지 알고리즘..

문제 정육점에서 N개의 덩어리 중 무게 M만큼 사려고한다. 정육점은 이미 무게와 가격이 정해져있는데 어떤 덩어리를 샀을 때 그 덩어리보다 싼 고기들은 추가지불없이 얻을 수 있다. 정확히 M만큼의 무게가 되지 않는다면 그 이상을 살 수도 있다. 이때 M만큼의 고기를 사기위해 필요한 최소비용을 구하라 입력 첫째 줄에 N과 M이 주어진다. 이후 N개의 줄에 고기의 무게와 가격이 입력된다. 출력 최소비용을 출력하고 만약 구할 수 없다면 -1을 출력한다. 접근 가장 적은 비용으로 M의 고기를 사야한다. 고기의 무게와 가격이 입력되었을 때 가격은 오름차순으로 정렬, 무게는 내림차순으로 정렬한다. 즉 가장 싼 가격을 갖는 고기의 무게를 더해나간다. 왜냐하면 비싼 가격은 그 미만의 가격을 갖는 고기를 꽁짜로 얻을 수 ..

문제 어떠한 문장이 있을 때 괄호들이 균형이 잡혀있는지 검사한다. 소괄호는 소괄호끼리 대괄호는 대괄호끼리 짝을 이뤄야한다. 균형잡힌 문자열이라면 yes를 아니라면 no를 출력한다. 입력 여러 줄에 걸쳐서 문자열이 입력될 때 각 문자열이 균형이 잡혔는지 검사한다. 만약 "."이 들어온다면 문자 입력을 종료한다. 출력 각 문자열에 yes 또는 no를 출력한다. 접근 괄호에 대해 관심을 가져야한다. 균형이 잡혔다면 현재의 닫는괄호가 가장 최근에 나온 여는괄호와 짝이 맞아야한다. 스택은 가장 마지막에 넣은 데이터가 가장 위에 쌓이기 때문에 괄호를 스택에 넣어보도록 한다. 구현 기본적으로 while문안에서 실행이 된다. 괄호를 넣을 스택을 생성하고 string형의 input에 getline으로 문자열을 입력받는다..

문제 일직선 위에 N개의 높이가 서로 다른 탑을 왼쪽부터 세운다. 각 탑의 꼭대기에 송신기를 설치하였고 송신기는 일직선과 평행하게 왼쪽으로 발사한다. 그리고 모든 탑의 기둥에는 수신기가 설치되어있어서 다른 탑의 신호를 받을 수 있다. 이때 각 탑들이 신호를 보낼 때 몇 번째의 탑이 수신을 하는지 구하라. 6 9 5 7이라면 7은 9가, 5도 9가 수신을 하게된다. 입력 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. (1이상 500,000이하) 두 번째 줄에 탑의 높이가 N개 주어진다. 출력 각 자리의 탑이 송신한 신호를 수신하는 탑의 위치를 출력한다. 접근 처음에 두 개의 FOR문으로 현재 탑을 기준으로 인덱스를 줄여가면서 왼쪽으로 탐색하도록 설계를 하였다. 하지만 시간초과가 발생하였는데 O(500..

import sys input = sys.stdin.readline N, K = map(int, input().split()) q = [n+1 for n in range(N)] answer = [] idx = 0 while q: idx = (idx + (K-1)) % len(q) answer.append(q.pop(idx)) print("".format(answer[-1])) 문제 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K가 주어진다. 이제 순서대로 K번째 사람을 제거할 때 제거되는 순서대로 출력하시오 입력 첫째 줄에 N과 K가 빈 칸을 사이에두고 순서대로 입력된다. 출력 안에 제거되는 순서대로 출력한다. 접근 처음에 사람들이 원모양으로 앉아있는 것을 어떻게 표현할까?라는 생..

문제 인쇄 대기목록의 가장 앞에있는 문서를 꺼내고 나머지 인쇄 대기목록에서 중요도가 높은 문서가 있다면 맨 뒤에넣고 중요도가 높은 문서를 출력한다. 만약 중요도가 높은 문서가 없다면 그대로 출력한다. 이때 내가 원하는 문서가 몇 번째로 출력되는지 구하라 입력 문서의 중요도가 담긴 배열과 내가 뽑고자 하는 문서가 몇 번째에 있는지 입력된다. 출력 내가 출력하고자 하는 문서가 몇 번째로 출력되는지 구하라. 접근 각 문서에는 중요도가 있고 중요도가 높은 문서가 먼저 출력이된다. 여기서 본인이 원하는 문서가 몇 번째로 출력되는지 구해야한다. 그래서 출력되는 문서들이 몇 번째 있던 문서인지 알아야했다. 그리고 출력되는 문서가 현재 대기목록 중 가장 큰 문서인지도 확인해야했다. 따라서 큐에 문서의 중요도와 몇 번째..

문제 트럭 여러 대가 다리를 지나려고 한다. 다리는 길이와 한 번에 견딜 수 있는 무게를 갖고있다. 트럭은 1초에 1만큼 이동을 하고 다리가 견딜 수 있는 무게를 초과해서 트럭이 들어올 수 없다. 다리의 길이, 무게와 트럭들의 무게가 입력으로 들어올 때 모든 트럭이 순서대로 다리를 건너는 최소시간을 출력하라. 입력 다리길이, 다리무게, 트럭들의 무게가 입력된다. 출력 트럭이 다리를 모두 건너는 최소시간을 출력한다. 접근 트럭을 이동할 때마다 현재 다리 위에있는 트럭들의 무게와 트럭을 다리 길이만큼 이동시켜야 했다. 현재 무게를 측정하는 것은 어렵지 않았지만 트럭의 이동을 어떻게 모델링할지 많은 고민을 하였다. 그러던 중 다리를 큐로 모델링하여 트럭이 이동하는 것이 아니라 트럭이 들어오면 큐가 움직이는 생..