풀스택챌린지

문제 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 영어 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다. 출력 듣보잡의 수와 그 명단을 사전순으로 출력한다. 접근 두 개의 그룹에 모두 속한 이름을 출력하는 것이다. 집합으로 표현했을 때 교집합인 부분을 출력해야하며 파이썬에서 set()을 통해 집합을 표현한다. list 형의 그룹들을 set 형으로 변경하여 &..

문제 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다. 출력 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다. 접근 입력에서 주어진 정보로 그래프를 그리면 방향 그래프가 된다. 먼저 y축의 번호를 기준으로 탐색을 진행한다. 이때 방문 표시를 해서 무한루프가 돌지않도록 해야하는데 ..

문제 크기가 NxN의 각 칸에 R, G, B 색 정보가 담겨져있다. 적록색약인 사람은 R과 G를 구분하지 못하고 하나의 색으로 본다. 이때 각각의 색 구역을 적록색약이 아닌사람과 적록색약인 사람이 몇 개의 구역으로 보는지 구하라. 입력 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100) 둘째 줄부터 N개 줄에는 그림이 주어진다. 출력 적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다. 접근 적록색약인 사람과 아닌 사람에 따라 다른 BFS로 하려고했지만 코드가 너무 길어졌다. 그래서 적록색약이 아닌 사람의 구역을 먼저 구한 다음에 그림판에서 G를 R로 바꿔주어 적록색약인 사람의 구역을 구하도록 하였다. 구현 그림판의 정보를 입력받는다. N =..

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