pinevienna blog

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 문제. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다. (즉, 하나의 수가 여러번 등장할 수 있다.) N=3, K=3인 경우로 예시를 들어보자면 1. N=1일때 K=1인경우 : 1가지 (1) K=2인경우 : 2가지 (1+0, 0+1) K=3인경우 : 3가지 (0+1+1, 1+0+1, 1+1+0) 2. N=2일때 K=1인경우 : 1가지 (2) K=2인경우 : 3가지 (2+0, 0+2, 1+1) K=3인경우 : 6가지 (2+0+0, 0+2+0, 0+0+2, 0+1+1, 1+0+1, 1+1+0) 2. N=3일때 K=1인경우 : 1가지 (3) K=2인경우 : 4가지 (2+1, 1+2, 3+0, 0+3) K=3인경우 : 10가지 (3+0+0..

그래프가 주어졌을 때, 이분 그래프인지 아닌지 판별하는 문제!! 이분 그래프가 뭔지부터 알아야 한다. 이분 그래프는 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있는 그래프이다. 음 뭔소리야~ 싶어서 찾아보니까 화려하면서 심플한 기능이다.. 구체적인 설명은 당장 어려울 것 같고 문제를 풀기 위해 저렴하게 이해/설명 해보자면 이렇게 서로 연결된 정점이 같은 색을..^^ 가지면..^^ 안된당..ㅎ 설명 너무 저렴해서 너무 부끄럽긴 한데 나중에 또 까먹을 날 위해 남긴다.. 코드는 아래 블로그를 참고해서 짰다!! bfs를 이용해서 풀었고, 연결된 노드가 같은 숫자(색)이면 NO를 출력한다. [백준 1707] 이분 그래프 (자바) https://www.acmicpc...

모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. - 단 한명만 선택 가능 - 자기 자신 선택 가능 (혼자서 팀) 1번~7번 학생들이 각자 팀을 이루고싶은 학생들을 선택한다고 가정하자. 위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다. 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 문제!! 싸이클을 형성하지 못하는 노드를 찾으면 되는데 시간초과가 발생한다.. 이 때 '단 한명만 선택 가능' 이라는 조건을 이용하면 된다. 1->3->3 2->1->3->3 3->3 이 경우엔 1만 탐색한다면 2, 3은 할 필요가 없다!!!! 기존 dfs에서 쓰던 visited 배열로는 부족하고 하나 더 만들어줘야 한다. visited가 방..

입력받은 2진수를 8진수로 변환하여 출력하는 문제 2진수를 8진수로 변환할 땐 뒤에서부터 3개씩 끊어서 계산해야 한다. 각각 1, 2, 4를 곱해서 더하고 어쩌구 저쩌구...는 다 알거라고 생각한다. 중요한 포인트는 3개씩 끊고 남은 제일 앞 숫자인데 하나 또는 두개가 남을 수 있으므로 따로 계산해주면 된다. 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 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class BOJ_1373 { public static void main(String[] args)..

수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 문제. C++로 풀었을 땐 그냥 아무렇게나 정렬해도 됐다... 자바는 아니다..^^ 정렬 알고리즘 - 퀵 정렬 (Quick Sort) 퀵 정렬은 분할 정복 알고리즘 중 하나이며 이름처럼 정렬 속도가 매우 빠르다. 최선, 평균 = O(N log N) / 최악 = O(N^2)의 시간복잡도를 가진다. 1) 배열의 정 가운데 요소를 '피벗'으로 정한다. 2) 왼 pinevienna.tistory.com 퀵 정렬로 정렬해야 시간초과를 면할 수 있었다,, 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..