.

문제https://www.acmicpc.net/problem/11866 문제 탐색하기요세푸스 : 1부터 시작하여 K-1개의 수를 건너뛰고 그 다음 K번째 수를 제거, 이 과정이 N명의 사람이 모두 제거될 때까지 반복순서대로 삽입/삭제가 일어나므로 Queue를 활용하여 구현K-1 만큼 건너뛰고 K번째 사람을 삭제하기 위해서 큐에 있는 데이터를 K-1만큼 꺼내서 뒤로 보내고 K번째 사람을 제거코드 설계하기사람의 수 N과 매번 제거될 사람의 위치 K를 입력받는다큐를 이용해서 사람들을 순서대로 입력K-1만큼 건너뛰고 K번째 사람을 제거맨 앞에 있는 사람을 제거하고 다시 큐의 맨 뒤에 추가이 과정으로 K-1번째까지의 사람을 뒤로 보내고 K번째 사람 제거K번째 사람 제거 될 때 StringBuilder 객체에 추가..

문제https://www.acmicpc.net/problem/2193문제 탐색하기N자리 이친수의 개수 구하기N = 1인 경우, 이친수 개수 1개 (1)N = 2인 경우, 이친수 개수 1개 (10)N = 3인 경우, 이친수 개수 2개 (100, 101)N = 4인 경우, 이친수 개수 3개 (1000, 1001, 1010)위의 결과를 보면, N자리는 N-1의 마지막 끝자리에 따라 결정난다.뒷자리가 0으로 끝나는 경우뒤에 0, 1 붙이기뒷자리가 1로 끝나는 경우뒤에 0 붙이기DP 설계하기dp[i][0] : 숫자 N을 만드는 경우의 수 중 끝자리가 0인 경우의 수dp[i][1] : 숫자 N을 만드는 경우의 수 중 끝자리가 1인 경우의 수초기값dp[1][0] = 0dp[1][1] = 1i 자리의 끝자리가 0으로 ..

문제https://www.acmicpc.net/problem/2303문제 탐색하기5장의 카드 중 3장을 더한 합의 일의 자리 수가 큰 사람의 번호 출력하기 일의 자리 수가 같은 경우, 번호가 큰 사람을 출력 가능한 시간복잡도입력 범위 ( 2 ≤ N ≤ 1000)가장 큰 일의 자리 수 구하기5장 중 3장을 고르는 조합 5*4*3 = 60각 사람에 대해 최대 60번의 연산 수행 시간 복잡도 O(N*60) N명의 사람 중 가장 큰 수를 가지고 있는 사람 탐색 시간 복잡도 O(N)전체 시간 복잡도 시간 복잡도 O(60*N ) + O(N)코드 설계하기각 사람 당 입력 받은 카드 값 저장카드 조합각 사람에게 주어진 5장의 카드 중 3장을 선택하는 조합 계산 일의 자리 계산그 조합의 합을 계산하고 그 합의 일의 자리..

문제https://www.acmicpc.net/problem/5567 문제 탐색하기n : 상근이 동기의 수m : 친구 관계 수a, b : 관계를 나타내는 값 상근이의 친구와 그 친구의 친구까지 초대하기 위해 depth 확인을 위해 DFS 이용그래프는 인접리스트로 구현 / 인접리스트로 구현 시 양방향 그래프로 구현상근이  depth = 0, 상근이 친구 depth = 1, 상근이 친구의 친구 depth = 2 가능한 시간복잡도입력 범위 ( 2 ≤ n ≤ 500, 1≤ m ≤ 10000)인접리스트 초기화 : 시간 복잡도 O(n) 그래프 생성 n : 상근이 동기의 수 (그래프의 노드 수)m : 친구 관계 개수 (그래프의 간선 수)관계를 입력받고 그래프를 구성할 때, m개의 간선을 입력받으므로 시간 복잡도 O(..

문제https://www.acmicpc.net/problem/2204문제 탐색하기n : 단어 개수 입력 : 알파벳 대소문자로 이루어진 단어 n개출력 : 대소문자 구분없이 사전순으로 나열 후 가장 첫 번쨰 단어 출력가능한 시간복잡도거의 모든 정렬 함수는 N개의 원소를 정렬할 때 O(NlogN)의 시간복잡도 가짐 코드 설계하기단어 개수 N를  입력받는다.단어를  Array로 저장한다.사전 순에 따라 정렬한다.정렬된 배열 중 가장 첫 번째 단어를 출력한다. 풀이 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.Compara..

문제https://www.acmicpc.net/problem/2644 문제 탐색하기n : 전체 사람의 수start, end : 촌수를 계산해야하는 서로 다른 두 사람m : 부모 자식들 간 관계 개수x, y : 관계를 나타내는 수 (x는 y의 부모)촌수를 계산하는 것은 이어진 그래프에서 깊이 차이 구하기이므로 DFS 이용어떤 사람부터 탐색을 시작해도 깊이를 구할 수 있도록 양방향 간선으로 입력받음 DFS 탐색start 부터 탐색 시작탐색 중 end를 만나는지 확인만났을 경우 깊이 값 출력 가능한 시간복잡도입력 범위 ( 1 ≤ n ≤ 100)그래프 생성 n : 전체 사람의 수 (그래프의 노드 수)m : 부모-자식 간의 관계 개수 (그래프의 간선 수)부모-자식 관계를 입력받고, 그래프를 구성할 때, m개의 간..

문제문제 탐색하기이 문제는 조합과 DP 두 가지 방법으로 풀 수 있다. 여기서는 DP 방법으로 풀어보도록 하겠다. N : 서쪽 사이트M : 동쪽 사이트DP 설계하기1. N = 1 일 때N = 1 일 때, 총 다리를 놓을 수 있는 경우의 수는 M개 이다. 서쪽 N개 사이트, 동쪽 M개 사이트 일 때 놓을 수 있는 다리의 경우의 수를 F(N,M) 라 표시하면 →  F(1,M) = M2. N = 2 일 때M = 2 일 때, F(2,2) = F(1,1) M = 3 일 때, F(2,3) = F(1,2) + F(1,1,) M = 4 일 때, F(2,4) = F(1,3) + F(1,2) + F(1,1)3. N = 3 일 때M = 3 일 때, F(3,3) = F(2,2)M = 4 일 때, F(3,4) = F(2,3) ..