목록BOJ (339)
어흥
문제 링크: https://www.acmicpc.net/problem/15997 15997번: 승부 예측 첫 번째 줄에 조별리그를 진행할 국가명 네 개가 공백으로 구분되어 주어진다. 주어지는 모든 국가명은 알파벳 대문자로만 구성된 길이가 1 이상 10 이하인 문자열이다. 두 번째 줄부터 일곱 번 www.acmicpc.net 1. 주의할 점 - 브루트포스를 통해 구하지만, 3^6 전부를 돌리지 않아도 된다 - 독립 사건 → 확률을 곱하면서 진행 2. 구현 - Map을 통해 각 문자열에 매칭되는 번호를 저장한다 - Matches[idx]를 통해 idx번째 경기에 누가 참가하는지 저장핟나 - WinRate[idx][]를 통해 idx번째 경기의 승무패 확률을 저장한다 - DFS를 수행하여 최대 6번의 경기를 치..
문제 링크: https://www.acmicpc.net/problem/2026 2026번: 소풍 만약 K명의 친구 관계인 학생들이 존재하지 않는다면 -1을 출력한다. 그 외의 경우에는, K개의 줄에 학생들의 번호를 증가하는 순서로 한 줄에 한 개씩 출력한다. 여러 경우가 존재한다면 첫 번째 www.acmicpc.net 1. 주의할 점 - 전체 학생에 대해 DFS를 돌리지 않도록 한다 2. 구현 - Arr[][] 배열을 통해 학생간 친구관계를 저장한다 - 각 학생에 대해 친구가 N-1명 이상인 경우에만 DFS를 수행하도록 하기 위해 Avail에 친구가 N-1명 이상인 학생만 담는다 - DFS()를 통해 N명을 골랐을때 모두 친구면 Fin을 True로 설정하여 더 이상 검사하지 않도록 한다 - 만족하는 경우..
문제 링크: https://www.acmicpc.net/problem/9007 9007번: 카누 선수 이 문제에서는 입력은 표준 입력을 사용한다. 입력의 첫 줄에는 T개의 테스트 케이스가 주어진다. 각 테스트 케이스에는 두 개의 정수 k와 n이 주어지며, k( 1 ≤ k ≤ 40,000,000)는 보트의 특정 값 그 www.acmicpc.net 1. 주의할 점 - 시간복잡도를 줄이려고 노력한다 - TestCase를 시작하기 전, 연산에 사용되는 모든 벡터 및 값을 초기화한다 2. 구현 - 4개의 집합(V[])을 2개씩 묶어서 각 집합의 모든 원소의 합을 twoSum[]에 저장한다 - 두 집합의 합을 구할때: O(N^2) - twoSum을 통해 Weight과 비교할 때(twoSum[0]의 길이를 A(=N^..
문제 링크: https://www.acmicpc.net/problem/3107 3107번: IPv6 첫째 줄에 올바른 IPv6 주소가 주어진다. 이 주소는 최대 39글자이다. 또한, 주소는 숫자 0-9, 알파벳 소문자 a-f, 콜론 :으로만 이루어져 있다. www.acmicpc.net 1. 주의할 점 - : 를 기준으로 어떻게 나눌것인가 - ::를 어떻게 처리할 것인가 2. 구현 - C++의 경우에는 sstream을 통해, Java의 경우에는 split을 통해 세미콜론을 처리했다. 다만, Java의 경우 끝에 ::가 있을 때 처리를 못해서 추가 코딩이 필요하다 - 세미콜론을 기준으로 문자열을 잘랐을 때, 해당 문자의 길이에 따라 조건을 처리하고 V 벡터 or Li 리스트에 추가한다 - 길이가 4면 그대로..
문제 링크: https://www.acmicpc.net/problem/2064 2064번: IP 주소 네트워크에 연결되어 있는 컴퓨터들은 각각 하나의 IP 주소를 갖게 된다. 그리고 이러한 IP 주소를 갖는 컴퓨터들이 여러 개 모여서 하나의 IP 네트워크를 구성하게 된다. IP 네트워크는 ‘네트워 www.acmicpc.net 1. 주의할 점 - 비트마스킹을 이용해도 되지만, 네트워크 주소의 결과가 0.255.255.0이 나왔을때 전부 0으로 바꿔야하는 작업이 필요 2. 구현 - 입력 받는 문자열을 int2string() 함수를 이용하여 전부 2진수로 바꾼다 - 해당 반환값을 Ip[] 배열에 String 형태로 저장한다 - 모든 문자열을 처음부터 비교하여 왼쪽에서부터 Idx-1까지 같다고 할때, Idx를 ..
문제 링크: https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 1. 주의할 점 - 0과 -1을 출력하는 기준을 정확히 알아야 한다 2. 구현 - init() 함수를 통해 Check[][] 배열을 초기화한다. Check[][] 배열은 정답 배열이다 - 지도에 대한 정보를 Arr[][]에 받으며, 목표지점에 대한 정보를 Sx, Sy에 저장한다 - BFS 탐색을 통해 목표지점에서 도달할 수 있는 지점까지의 ..
문제 링크: https://www.acmicpc.net/problem/19538 19538번: 루머 예제 1 0분 : 최초 유포자($1$, $6$번 사람)가 루머를 생성한다. 1분 : $1$번 사람은 $2$, $3$번 사람에게 루머를 퍼뜨린다. $2$번 사람은 주변인 $2$명 중 $1$명이 루머를 믿고 있어 루머를 믿게 된다. $3$ www.acmicpc.net 1. 주의할 점 - 루머를 퍼트리는 일은 동시에 일어난다 2. 구현 - BFS의 방법으로 문제를 해결한다 - Info 객체를 사용하여 현재 사람의 번호, 루머를 들은 시간, 당시에 주변에 루머 믿었던 사람 수 - rumorTime[] 배열을 이용하여 루머를 믿는 시간을 저장한다. 초기에는 init() 함수를 통해 -1로 전부 초기화한다 - nea..
문제 링크: https://www.acmicpc.net/problem/16118 16118번: 달빛 여우 첫 줄에 나무 그루터기의 개수와 오솔길의 개수를 의미하는 정수 N, M(2 ≤ N ≤ 4,000, 1 ≤ M ≤ 100,000)이 주어진다. 두 번째 줄부터 M개의 줄에 걸쳐 각 줄에 세 개의 정수 a, b, d(1 ≤ a, b ≤ N, a ≠ b www.acmicpc.net 1. 주의할 점 - 늑대가 같은 지점에 최단 경로로 도착하는것보다 돌아서 가는게 빠를 수 있다(느릴 때, 빠를 때 적절히 이용) - 1번째 Node까지의 최단시간을 0으로 설정하지 않는다(0을 이용하여 돌아갈 수 있다) - d와 M의 범위가 크므로 Long Long을 이용한다 2. 구현 - Info 객체를 이용한 우선순위 큐를 ..