🌱1 Day, 1 Commit Wonseok's Record

https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 해설 : 케빈 베이컨의 6단계 법칙에 의하면 전 세계의 모든 사람은 지인을 6번만 거치면 모두 아는 사람이라고 한다. N명의 사람과, 연결관계가 주어질 때 각 사람들이 나머지 사람들에 총 몇 단계를 거쳐야 아는 사이가 되는지 구하고 거쳐야하는 단계들의 합 중에 최솟값을 가진 사람을 찾는 문제이다. 풀이 : 사람들간의 연결관계가 주어졌으므로 모든 사람..

https://www.acmicpc.net/problem/1343 1343번: 폴리오미노 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. www.acmicpc.net 해설 : X와 "." 으로 이루어진 문자열을 'AAAA'와 'BB'로 치환할 수 있는지 찾는 문제이다. 치환할 수 있다면 사전순으로 가장 앞서는 치환값을 출력하면 된다. 풀이 : 주어진 문자열을 탐색하며 X를 만났을 때 연속되는 X의 개수를 센다. X의 개수가 홀수개라면 -1을 리턴하고 아니라면 AAAA 또는 BB로 치환한다. AAAA가 들어갈 수 있을 때 우선적으로 넣어줘야 사전순으로 앞서는 답을 도출할 수 있다. 소스코드 : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1..

https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 해설 : 알파벳 대문자들로만 이루어진 문자열 N개가 주어진다. 각 알파벳 대문자를 0~9의 숫자로 치환하여 더하였을 때 그 결괏값이 최대가 되는 경우를 구하는 문제이다. 풀이 : 문자열에 존재하는 알파벳별 가중치를 계산하기 위한 배열을 만들고, 이 배열에 문자열에 있는 문자들마다의 가중치를 더해준다 예를 들어 , ABC라는 문자열이 있다면 배열[A]의 가중치는 100이고 배열[B]는 10 배..

https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 해설 : 파란 옷을 입은 병사들과 하얀 옷을 입은 병사들이 뒤엉켜 싸우고 있다. N명의 병사들이 뭉쳐있을 경우 N^2의 힘을 낼 수 있다고 한다. 대각선에 있는 경우는 인접하지 않아 뭉쳐있다고 할 수 없다고 할 때, 파란 병사들와 하얀 병사들의 전투력 총합을 계산하는 문제이다. 풀이 : BFS로 W 또는 B의 병사들을 만났을 때 탐색하고 인접한 병사들의 수를 리턴하여 이 ..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 해설 : 그래프의 노드와 간선정보가 주어질 때, 1번 정점부터 BFS와 DFS로 탐색한 결과를 출력하는 문제이다. 풀이 : 양방향 그래프이므로 0번 노드부터 N-1번 노드까지 연결 관계를 재설정해준 후 이를 BFS와 DFS로 각각 탐색하며 현재 탐색중인 노드를 출력하도록 구현하였다. 소스코드 : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ..

https://www.acmicpc.net/problem/1242 1242번: 소풍 동호와 동호네 반 친구들은 산정호수로 소풍을 갔다. 총 N명이 소풍에 참가했고, KIN 게임을 하려고 한다. 이 게임은 다음과 같이 진행된다. 무대에 올라간 N명은 1번부터 N번까지 시계방향으로 원 www.acmicpc.net 해설 : 요세푸스 순열(https://recordofwonseok.tistory.com/96)과 똑같은 문제인데 내가 몇 번째로 탈락하는지만 추가적으로 찾으면 되는 문제이다. 풀이 : 옛날에 풀었던 문제라 기억이 잘 안난다. 소스를 참고로 해석해보자면 n은 퇴장당한 사람의 수이다. 매 퇴장당하는 경우마다 mod값을 이용하여 다음 퇴장당할 사람을 계산하는 방식인 것 같다. 소스코드 : 1 2 3 4 ..

https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 해설 : N개의 노드로 이루어진 트리가 주어지고, 노드 사이의 거리 M개가 주어질 때, testCase에 대해 노드 사이의 거리를 출력하는 문제이다. 풀이 : 양방향 연결이므로 노드 사이의 거리와 연결 정보를 0번노드부터 N-1번 노드까지 가공한 후 이를 BFS로 탐색하며 원하는 노드가 나왔을 때 거리를 출력한다. 소스코드 : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25..

https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 해설 : 알파벳 소문자로 이루어진 단어 N개가 주어질 때 이를 조건에 맞게 정렬하는 문제이다. 조건 1. 길이가 짧은 것이 앞으로 조건 2., 길이가 같다면 사전순으로 가까운 것이 앞으로 풀이 : 쉬운 정렬 문제이다. 주어진 알파벳들을 list에 넣고 sort 함수를 사용하면 된다. 풀이를 보면 정렬을 2회 진행하였는데 이 때는 Python의 이해도가 조금 낮았던 것 같다. 지금 푼다면..

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 해설 : 트리의 노드와 간선정보가 주어질 때, 임의의 두 노드사이의 최대거리를 구하는 문제이다. 풀이 : BFS의 구현은 쉬웠지만 답을 도출하는 아이디어를 떠올리기 힘든 문제였다. 1. 루트노드에서 BFS로 탐색하여 가장 멀리 떨어진 노드를 찾는다. 2. 루트로부터 가장 멀리 떨어진 노드로부터 가장 멀리 떨어진 노드를 찾는다. BFS를 총 2회 실행해야 찾을 수 있는 문제였다. 소..