코딩테스트 챌린지 (15) 썸네일형 리스트형 [코딩테스트 챌린지] 백준 5567 결혼식 (java) 문제 문제 탐색하기1. 문제 유형 파악하기친구 관계가 주어지는 것을 보았을 때 a와 b는 친구라는 뜻은 b와 a도 친구라는 뜻입니다. 이를 통해서 인접행렬을 통해서 친구관계를 나타낼 수 있었습니다. 또 문제 조건 중에서 결혼식에 초대하는 사람은 상근이의 친구와 친구의 친구까지만 초대하는 조건이 있었습니다. 이를 통해서 dfs 를 구현하되 depth를 2로 제한을 두어 결혼식에 초대하는 동기의 수를 구할 수 있을 것 입니다. 2. 인접 행렬 구현하기입력받는 친구관계를 통해 친구관계 배열인 connect에 친구일 경우 1을 삽입해줍니다.connect[a][b] = connect[b][a] = 1 3. DFS 구현하기dfs를 재귀적으로 호출할때 거치는 친구를 True로 저장하는 배열을 선언합니다.dfs는 상근.. [코딩테스트 챌린지] 백준 2204 도비의 난독증 테스트 문제문제 탐색하기 1. 문제 유형 파악하기해당 문제는 문자열을 오름차순으로 정렬한 뒤 그 문자열을 출력하면 되는 문제입니다. java의 정렬 알고리즘은 여러가지가 있지만 문자열을 정렬해야하기에 사용하기 간단한 Collections.sort() 를 사용하도록 하겠습니다.2. 정렬 설계하기문자열을 모두 소문자 또는 대문자로 치환하면 어떤 문자열이 사전순으로 젤 앞쪽에 위치하는지는 빠르게 구할 수 있습니다. 하지만 여기서 고려해야할 부분은 다시 그 문자열의 원래 형태를 알아야한다는 것입니다.따라서 처음에 문자열을 입력받을때 HashMap을 사용하여 입력받은 문자열을 소문자로 치환하여 키로 저장하고 본래의 문자열을 value로 저장합니다.Collections.sort를 사용해서 hashmap의 keyset을 정.. [코딩테스트 챌린지] 백준 11724 연결 요소의 개수 (java) 문제 문제 탐색하기1. 연결 요소의 개수란?연결 요소란 그래프 내에서 연결되어 있는 정점들을 한 그룹으로 묶는 것을 말합니다.한 정점에서 시작해서 연결된 모든 정점들을 순차적으로 탐색한 후에 한 그룹으로 묶는 과정은 DFS로 탐색할 수 있습니다. N의 길이를 가진 배열을 선언하여 연결요소로 탐색된 곳을 true로 표기하는 boolean 배열을 선언합니다.입력받은 input 값을 체크할 2차원 배열도 선언합니다. 각 노드 쌍 (a,b)가 입력되었다면 양방향 간선이므로 arr[a][b], arr[b][a] 를 1로 선언합니다. 2. DFS 를 통해 연결 요소 찾기1번 노드부터 n번 노드까지 visit[] 배열을 확인하고, 방문하지 않은 노드를 발견할 때마다 dfs() 메소드를 호출합니다.dfs() 메소드는 .. [코딩테스트 챌린지] 백준 17204 죽음의 게임 (java) 문제 문제 탐색하기1. 영기가 말해야하는 번호 보성이가 게임에서 걸리게 하기 위해서는 영기부터 시작해서 보성이의 번호를 부르는 과정까지 총 몇번의 차례가 진행되는 지 알아내서 영기가 그 번호를 말하면 됩니다. 게임의 규칙에 따라 보성이가 걸리지 않을 수 있으므로 그 때에는 -1를 리턴하는 것을 고려해야 합니다. 즉, 한 곳에서 시작해서 결과값이 나올때까지 탐색하며 결과값이 나오지 않을 경우에는 -1을 리턴하면 되는 문제입니다. 2. 시간복잡도 탐색보성이가 걸리지 않을 경우가 최대 탐색하는 경우이기 때문에 N회의 탐색 즉, O(N)의 시간복잡도를 가지게 됩니다. 코드 설계하기게임 참가 수, 보성이의 번호를 각각의 변수에 저장i번째 사람이 지목하는 사람의 번호를 ArrayList에 저장초기값 세팅 : lis.. [코딩테스트 챌린지] 백준 10451 순열 사이클 (java) 문제 문제 탐색하기1. 순열 사이클 규칙 파악하기 문제에 예시로 보여주는 문제를 통해서 규칙을 파악해보도록 하겠습니다. 문제의 순열 배열을 아래의 그림으로 나타냈습니다. 1은 3을 가르키고 3은 7을 가르키며 7은 5, 5는 다시 1을 가르키고 있습니다. 순열 배열의 첫번째 인덱스인 1부터 시작해서 가르키는 순열을 그림으로 나타내보면 다음과 같습니다.5가 다시 1을 가르켰을 때 순열 사이클 1개가 완성됩니다.순열 배열의 주황색 박스를 key, 초록색 박사를 순열, 즉 value로 생각해보면순열 사이클이 시작되는 첫번째 key 값이 마지막 value가 될 때 순열 사이클이 1개 완성된다는 규칙이 있다는 것을 알 수 있었습니다. 따라서, 순서를 보장하는 LinkedHashMap에 key값은 순열 배열의 인.. [코딩테스크 챌린지] 백준 1463 1로 만들기 (java) 문제 문제 탐색하기1. 최소 연산 개수 구하는 규칙 찾기X를 1부터 7까지 나열하여 최소 연산 개수를 구하는 규칙을 찾아보도록 하겠습니다. 1) X = 1 일때정수가 주어졌을 때 그 정수를 1로 만들려하는 과정에 사용되는 연산의 횟수의 최소값을 구하는 것이다 보니 연산횟수가 0 입니다.배열로 생각해보면 arr[0] = 1 로 지정할 수 있습니다. 2) X = 2 일때 X는 2로 나누어 떨어진다면 2로 나누라는 조건에 따라 2로 나눴을 때 1 이됩니다. 연산 횟수는 1, arr[2] = 1 3) X = 3 일때X는 3으로 나누어 떨어진다면 3으로 나누라는 조건에 따라 3으로 나눴을 때 1이 됩니다. 연산 횟수는 1 , arr[3] = 1 4) X = 4 일때4를 1로 만드는 경우의 수는 조건에 따라 2가.. [코딩테스트 챌린지] 백준 1010 다리 놓기 (java) 문제 문제 탐색하기1. 다리를 지을 수 있는 조건 이해하기2가지 조건이 있습니다. 한 사이트에는 한 개의 다리만 지을 수 있다는 것과 서로 다른 다리가 겹치면 안된다는 조건이 있습니다.입력받는 N과 M 값을 통해서 M개 중에서 N개를 선택해서 다리를 지어야한다는 것을 통해 조합공식을 활용하면 된다는 것을 알 수 있습니다. 조합이란? 서로 다른 n개에서 순서에 상관없이 r개를 고르는 것을 말합니다. 다리가 겹치면 안된다는 조건을 조합의 개념을 통해 만족시킬 수 있습니다.1 1 1) 1 -> 3 / 2 -> 2 (3,2)2 2 2) 1 -> 2 / 2 -> 3 (2,3) 3 위 처럼 N=2, M=3 인 것을 예시로 들면 첫번째 케이스는 다리가 겹치게 되고 두번째 케이스는 겹치지 않지만 결국 M 중 .. [코딩테스트 챌린지] 백준 2775 부녀회장이 될테야 (java) 문제 문제 탐색하기1. DP 설계하기DP 알고리즘을 구현하는 방식은 Top-Down(하향식) 방식과 Bottom-Up(상향식) 방식이 존재합니다. 이 전 게시글인 피보나치 수2 문제를 풀때는 상향식 방식으로 반복문을 활용하여 문제를 풀었습니다. 이 문제는 Top-Down 방식으로 재귀함수를 구현하여 문제를 풀어보려 합니다. * 백준 2748번 피보나치 수2 풀이 게시글https://coding-babo.tistory.com/139 [코딩테스트 챌린지] 백준 2748 피보나치 수 2문제 문제 탐색하기1. 동적 계획법이란Dynamic Programing, 줄여서 DP라고 하며, DP 알고리즘 기법은 이미 계산된 결과(하위 문제)는 별도의 메모리 영역에 저장해서 다시 계산하지 않도록 설계함으coding-ba.. 이전 1 2 다음
