MuviSsum

www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 문제: 뱀과 사다리 게임에서 주사위를 최소로 굴려 1부터 100까지 가장 빠르게 도착할 수 있게 하라. 문제 이해하기!! 뱀과 사다리 게임은 예전에 많이 해봤던 추억의 놀이죠. 그래서 문제를 쉽게 이해할 수 있었던 것 같습니다. 1부터 100까지이므로 모든 경우의 수를 다 확인하면 됩니다 ㅎㅎ (완전탐색!!) 다만, 주의할 점은 뱀으로 이동하면 100번까지 더 빨라..

www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 문제: 케빈 베이컨의 수가 최소인 사람의 번호를 출력하라. 문제 이해하기!! 케빈 베이컨이라하면 그래프의 한 노드에서 다른 노드로 최소 몇번을 걸쳐야 거기로 갈 수 있는지를 구하면 되는 문제입니다. 즉, BFS를 쓰면 되는 문제라고 볼 수 있습니다. ※ 다만, DFS를 쓰면 틀리니 주의하세요! DFS를 쓰면 틀리는 이유는 깊이와 너비 우선 방식의 노드 접근법을 생..

www.acmicpc.net/problem/13418 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1≤N≤1,000)과 도로의 개수 M(1≤M≤n*(n-1)/2) 이 주어진다. 입력의 두 번째 줄 www.acmicpc.net 문제: 피로도가 최악인 경로와 최적인 경로의 피로도 차이를 구하라. 문제 이해하기!! 학교의 입구부터 학교 건물을 모두 소개해주는 문제입니다. 모든 경로를 탐방해야하므로 최소 스패닝 트리 문제라고 할 수 있습니다. 그러므로 이제 제일 잘 알려진 프림 알고리즘과 크루스칼 알고리즘 중 하나를 선택하여 풀면됩니다. 음... 혹시나 둘 다 모르는 분은 다익스트라가 익숙하시면 프림으로 하시고..

www.acmicpc.net/problem/9694 9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 맨위 첫 번째 줄에 T(1

www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 문제: 파티에 다녀오는 최단 거리(왕복)를 구하라. 문제 이해하기!! 다익스트라 문제였습니다. 하지만 다익스트라를 한 번만에 푸는 것이 아닌 단 방향 길을 양 방향으로 생각해야 되는 문제에요. 시작하는 지점이 여러 개라고 모두 생각하다가는 시간초과가 날 수 있습니다. 제가 푼 방식을 설명하자면, 1. 먼저 도착지점에서 각 마을 파티사람들의 오는 최소거리를 다익스트라로 찾습니다. 2..

www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 문제: 로봇 청소기가 청소하는 칸의 개수를 출력하라. 문제 이해하기!! 전형적인 구현 문제입니다. 문제에 주어진대로 따라하면 코드를 작성하면 풀 수 있는데, 다만 얼마나 효율적으로 짜냐, 어떤 방식으로 짜냐가 중요하죠!! 저는 밑의 방식으로 풀게 되었습니다. 그 방식을 설명하자면!! 1. 각 방향으로 한 칸 전진하는 것을 함수로 만들어 줍니다. 2. 주어진 행동을 계속 반복하기 위해 while True로 반복..

www.acmicpc.net/problem/15482 15482번: 한글 LCS 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 최대 1000글자이고, 유니코드 U+AC00(가)부터 U+D7A3(힣)까지로만 이루어져 있으며, UTF-8로 인코딩 되어 있다. www.acmicpc.net www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제: 문자열 2개에서 최장 공통 부분 수열을 찾아라. 문제 이해하기!! LC..

www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 문제: 수열이 주어지면 가장 긴 증가하는 부분 수열의 크기를 찾아라. 문제 이해하기!..

www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 문제: 사이클이 생긴다면 그 즉시, 해당 번호를 출력하라. 문제 이해하기!! 처음에는 이게 무슨 문젠가 싶었어요. 일단 그래프 문젠데... 연결해서 사이클이면 어떻게 해야하지 라고 생각했었는데 아니;; 그래프 문젠줄알고 들어가서 풀었는데 분리집합이더라구요. 들어오는 것들 union으로 싹 다 넣어서 부분 집합을 통일시키면 되는데, 들어오기 전에 둘의 부모가 같아서 이미 해당 부분집합에 들어가 있는 두 숫자..

www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 문제: 0이면 해당 수가 들어가 있는 집합 둘을 합치고 1이면 둘이 같은 집합인지 확인해라. 문제 이해하기!! 이 문제는 그냥 유니온 파인드라고 광고를 하고 만든 문제인 것 같습니다. 0일 때, 두 집합을 합치고, 1일 때, find() 함수로 둘의 부모를 확인하면 됩니다. 문제를 풀 때, 한 번 틀렸는데... 최대재귀깊이를 생각 못 해서 ㅠㅠ 근데 요즘 백준에서 왜 틀..