CodeClover

[문제링크]https://www.acmicpc.net/problem/18230📌 문제 탐색하기화장실 타일을 새로 교체하는데 2x1 ,2x2크키의 타일을 가지고 입력받은 2xN타일을 채우는데 이때 각각 타일의 예쁨수 ? 가 최대인 경우의 수를 찾아서 출력하는 문제이다. 📌 코드 설계하기1. (2xN) 크기의 안에 들어갈 수 있는 타일의 개수가 최대인 경우를 찾고 2. 타일의 종류에 따라서 - 가장 큰 예쁨값의 타일부터 입력(이 과정에서 예쁨값이 큰 순서대로 정렬처리하는게 필요할거 같음)해서 더하면 예쁨값의 최대값을 구할 수 있지 않을까 ?📌 가능한 시간복잡도 1. 배열을 정렬처리해야하니까 O(Aloga + BlogB)2. n개의 타일을 배치해야하니까 O(N) 따라서, 가능한 시간복잡도는 1,2를 더한..

[문제링크]https://www.acmicpc.net/problem/2529 📌 문제 탐색하기k개의 부동호를 입력받았을때 0-9까지 숫자중에서 입력받은 k개의 부등호 숫자보다 1개 큰 k+1개의 서로 다른 숫자를 골라서 주어진 부등호 조건을 만족하는 숫자 조합들 중에서 가장 큰 숫자와 가장 작은 숫자를 출력하는 문제이다.  예제입력1을 보면 2 가 입력되었을때, 가능한 경우의 수는0 0  ( 숫자 0 중복 사용으로 불가능 )  1 0    ( 가능 )   => 1201 1 ( 숫자 1 중복 사용으로 불가능 )  => 1212 1     ( 가능 )  => 231 2 0     ( 가능 )  => 230 ....8 7     ( 가능 )  => 897이런식으로 숫자조합이 생성되며 이때 조합 ..

[문제링크]https://www.acmicpc.net/problem/2210 📌 문제 탐색하기25칸으로 이루어진 숫자판에서 한번 탐색 시 6개의 숫자열을 만들어내고 , 이 숫자판에서 만들 수 있는 6개 숫자열의 모든 경우의 수를 출력하는 문제이다. ( 중복되는 동일한 숫자열은 제외한다. ) 📌 가능한 시간복잡도 가능한 시간복잡도를 생각해보면 숫자판의 모든 위치에서 시작 가능하기 때문에 25개의 모든 칸 탐색.이때 각각 탐색에서 6개의 숫자를 만들도록 5번 이동한다. 이동시 4가지 방향으로 이동이 가능하다. 정리 ) 각각 칸마다 5번 이동하면서 이동시 4개의 선택지를 가지고 있으므로 한칸에서 최대 4의 5승 즉 1024번의 탐색이 가능하다. 25칸을 가진 숫자판에서 탐색을 시작하므로 가능한 시간복잡도는..

[문제링크]https://www.acmicpc.net/problem/11866 📌 문제 탐색하기1부터 N까지 사람들이 원형으로 앉아있는 상태에서 K번째 사람을 제거하고 그 다음 K번째 사람을 계속 제거한다. 모든 사람이 제거될 때까지 해당 과정을 반복하면서 제거된 순서를 출력하는 문제이다. 📌 가능한 시간복잡도 각각 요소를 제거할때는 최대 k-1번 이동하고 제거하는 과정을 반복하는 상황이기때문에... 따라서 가능한 시간복잡도는 O(N * K) 입니다. 📌 코드 설계하기1. N과 K의 값을 입력받는다.  원형으로 앉아있는 형태에서 특정 순서의 사람을 제거하는 과정을 진행해야하니까... 큐 사용해서 순열처리하는게 깔끔할거같음. 2. 1~N까지 번호를 큐에 추가한다.3. 순열 계산하기 ( 요세푸스 순열...

[문제링크]https://www.acmicpc.net/problem/2193  📌 문제 탐색하기이친수... 특성을 보면 이전 자리의 숫자에 따라서 다음 자리의 숫자가 결정되기 때문에 문제를 재귀적으로 해결하는 방식을 사용해야하는 문제인거 같다.  > 이친수란 ? ( 정리 예정 ) 📌 가능한 시간복잡도 for문이 n번 반복되기 때문에 가능한 시간복잡도는 O(N)입니다. 📌 코드 설계하기DP를 활용해서 해결하는 문제라고 생각함.  이친수에 대해서 공부하는데 시간이 조금 오래걸렸음... 1.입력받기 : N값 입력받고 2. DP사용할거니까 dp[i]으로 i자리 이친수 개수 저장해서 점화식 적용하기3. 출력하기: dp[n]출력해서 n 자리 이친수 개수 구하기 📌 정답 코드import java.util.Sc..

[문제링크]https://www.acmicpc.net/problem/2644 📌 문제 탐색하기그래프 문제로 사람들을 노드라고 생각하고 그래프로 표현이 가능하다. ( 양방향 관계 )두 노드 간 최단 경로를 참색하여 촌수를 계산하는 문제이다. 만약에 노드가 연결되어 있지 않은 경우 -1을 출력한다.📌 가능한 시간복잡도 각각 최대 한번씩만 방문하기 때문에 시간복잡도는 O(N)이다.📌 코드 설계하기탐색하는 방법이 DFS인지 BFS인지에 따라서 풀이가 달라지는데,,, 효율적인 문제풀이 방식이 어떤 방식인지 고민됨. BFS 사용해서 문제 풀이 진행visited[] 배열을 만들어서 방문여부를 저장하는 배열 만들기그리고 큐를 사용해서 현재 탐색하고 있는 노드와 촌수를 저장하기. 📌 정답 코드import java..

[문제링크]https://www.acmicpc.net/problem/1010  📌 문제 탐색하기강의 서쪽에는 N개, 동쪽에는 M의 사이트가 위치한다. 서쪽의 모든 사이트를 동쪽의 사이트와 연결해야하는 문제이다. 서쪽의 사이트 N개와 동쪽의 사이트 M개를 연결하는 조합문제이다.  📌 가능한 시간복잡도 1. 테스트 케이스 입력 값 처리해야하니까 O(test_case)2. 효율성을 위해서 DP사용 => DP배열 사용이므로 C(n,r) 한번 계산이니까 이때 시간 복잡도는 O(n,r)인데,   이때 입력값이 M과 N이니까 O(M,N) ...?따라서 가능한 시간복잡도는 두가지 경우를 모두 포함한 O(test_case ,M,N) 이라는 결론을 내림.   📌 코드 설계하기조합을 사용해서 다리를 지을 수 있는 경우..

[문제링크]https://www.acmicpc.net/problem/2748  📌 문제 탐색하기피보나치 수 문제로서 피보나치 수열을 활용한 방식의 문제이다. 피보나치 수열을 해결하는 가장 기본적인 방법은 재귀를 활용한 방식이므로 재귀적으로 접근할 계획이다.  Fn = Fn-1 + Fn-2 (n ≥ 2) 의 규칙을 가지고 있는 수열으로 입력값 n에 따라서 n번째 피보나치 수를 출력하는 문제이다. 📌 가능한 시간복잡도 & 실수 정리n의 값이 더 크게 입력 받아지는 경우 시간 초과가 발생 주의가 필요하다고 생각함... 이 부분은 조금 더 고민해 볼 필요가 있음. => 실제로 시간 초과로 실패함... 이런 경우 해결 방법을 찾아보니 DP를 활용해서 문제를 풀어야한다고 함... 2회차 다른 풀이 도전 ) 배열..