본문 바로가기

Problem Solving

 (5)
백준 BOJ 15591 풀이 (JAVA) https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 오랜만에 백준 문제를 풀어보았습니다. 문제 설명은 아래와 같습니다. 입력 예시는 아래와 같고, 친절하게 힌트까지 있습니다. N개의 동영상이 있는데, N-1개의 쌍으로 네트워크를 만들었다는 것에서 트리 구조로 데이터를 표현해야 함을 알았습니다. 매 Question 마다 동영상 v에 대해 k이상인 경우에만 BFS 나 DFS로 간선을 탐색하면 될 것 ..
백준 16236 아기상어 C++ 풀이 www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 오랜만에 백준 문제를 풀었습니다. 저는 BFS를 이용하여 AC를 받았고 minimum_distance의 초깃값을 20*20인 400보다 큰 값으로 설정해야 하는데 습관적으로 100이라고 하는 바람에 WA를 3번이나 받았습니다. 메인 함수의 로직은 아래와 같습니다. 아기 상어의 먹잇감을 찾는 find_prey() 함수를 구현하여 먹이를 못 찾을 때까지 무한루프를 돌면서 먹이를 찾습니다. while(true..
[백준] 2644 촌수계산 C++ 풀이 백준 2664 촌수계산 C++ 풀이 문제 링크 촌수 관계는 트리 형태이지만, 이를 양방향 그래프로 치환하여 dfs로 풀 수 있다. 만약 p와 c가 같다면, 그래프가 연결되어 있는 것이므로, ans 전역변수에 정답을 저장한다. 한번 dfs가 호출될 때 마다 노드 p에 연결된 미리 방문하지 않은 인접한 노드와, cnt를 1증가한 값을 인자로 dfs를 호출한다. ans를 -1로 초기화 해주었기 때문에, 한번도 업데이트가 되지 않은 경우 가족이 아니기 때문에 초기값 -1을 그대로를 출력하게 된다. 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 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #includ..
[백준] 14889:스타트와 링크 C++ 풀이 14889: 스타트와 링크 문제 링크 해결 방법 combination을 함수를 작성하여 n명의 사람을 n/2명의 두 팀으로 나누어 준다. (이 때 permutation으로 작성하면 안된다.) 예를 들어 permutation은 team1: (1,2), team2: (3,4) 뿐만 아니라 team1:(2,1), team2:(3,4) 또는 team1:(2,1), team2:(4,3) 처럼 팀원을 팀안에서도 분할하게 되는데, 이 경우가 이번 문제에서는 결과적으로 같은 능력치를 갖기 때문이다. 순서를 주어서 조합으로 구현해야 한다. cnt가 n/2가 되었다면 정확하게 visited배열의 절반 만이 true가 되었기 때문에 이 배열을 이용해 팀간의 능력치를 구해서 최솟값을 갱신해주면 된다. 능력치를 구할 때는, 2..
[백준] 1003번: 피보나치 함수 풀이 처음에는 아래와 같은 피보나치 함수의 재귀적 정의를 이용해서 종료 조건인 fibonacci(0) 과 fibonacci(1)이 호출 될 때마다 각각 a와 b의 값을 증가시켜서 호출 횟수를 새려고 하였다. 그러나 n이 커짐에 따라 0과 1의 호출 횟수가 기하급수적으로 증가하여 시간초과가 났다. 그래서 아래와 같은 방법으로는 n이 조금만 커지더라도 사용할 수 없다. int a; int b; int fibonacci(int n) { if (n == 0) { a++; return 0; } else if (n == 1) { b++; return 1; } else { return fibonacci(n-1) + fibonacci(n-2); } } 피보나치 수를 계산할 때, 중복되는 호출을 제한하기 위해 동적계획법을 이..

티스토리툴바