Coding Test

문제설명입력 & 출력 나의 풀이 이번 문제는 요세푸스 순열에 대한 문제입니다. 요세푸스 순열이란 문제에서 나와있듯이 "원형으로 앉아 있는 N명의 사람들이 순서대로 제거되는 과정 "입니다. 이 때 매번 K번째 사람을 제거하며, 마지막 한 사람이 남을 때까지 이 과정을 반복합니다. 이해를 돕기위해 위 그림을 기준으로 예로 들자면 8명의 사람이 위와 같이 원형으로 앉아 있습니다.1번째 사람부터 제거를 하면 3 ➡️ 6 ➡️  1 ➡️ 5 ➡️ 2 ➡️7➡️4 ➡️ 8 순서로 제거가 됩니다.  초기 상태 1, 2, 3, 4, 5, 6, 7, 8첫 번째 제거 1, 2, 3, 4, 5, 6, 7, 8 (3 제거)두 번째 제거 4, 5, 6, 7, 8, 1, 2 (6 제거)세 번째 제거 7, 8, 1, 2, 4, 5..

문제설명입력 & 출력 나의 풀이 이번 문제는 영화감독 숌은 영화 제목에 '666'이 포함된 숫자를 사용하여 영화 제목을 만들 때 쇼메이 만든 N번째 영화 제목에 사용된 숫자를 구하는 프로그램을 작성하는 문제입니다. 저의 접근 방식은 다음과 같습니다. 숫자를 666부터 시작하여 순차적으로 증가시킵니다.각 숫자에 '666'이 포함되어 있는지 검사합니다.'666'이 포함된 숫자를 찾을 때마다 카운트를 증가시킵니다.N번째로 '666'이 포함된 숫자를 찾으면 그 숫자를 출력합니다. 풀이 설명을 하자면 먼저 빠른 입력을 위해 Buffer를 사용하여 입력을 받아줍니다. 그리고 문제 자체에서 요구하는 사항이 666이 포함된 수를 찾는 것이기 때문에 앞서 접근방식에서 말한 대로 666을 시작 숫자로 지정합니다. 그리고 ..

문제설명입력 & 출력 나의 풀이 이번 문제는 가로는 2로 고정되어 있고 입력받은 N의 세로 크기만큼의 직사각형에 2x1, 1x2크기의 타일을 채워 넣을 수 있는 경우의 수를 구하는 문제입니다.  부분 문제의 중복큰 문제를 작은 부분 문제로 나눌 수 있습니다.위 그림처럼 n-1인 직사각형에 2×1 타일을 세로로 놓는 경우와, 크기가 n-2인 직사각형에 1 ×2 타일 두 개를 가로로 놓는 경우로 나눌 수 있습니다. 이렇게 작은 부분 문제들이 중복되어 나타납니다. 최적 부분 구조 DP 문제는 작은 부분 문제의 최적해를 이용해 전체 문제의 최적해를 구할 수 있는 최적 부분 구조를 가집니다.n이 1~5일때 타일을 배치할 수 있는 경우의 수는 위와 같습니다. 그림을 자세히 보면 n일 때는 n-1의 타일에 2x1타일..

문제설명입력 & 출력 나의 풀이 이번 문제는 N개의 배열에서 M배열의 요소가 존재하는지 판단하는 문제입니다. 문자열에서 숫자를 찾는 방식을 사용할 수도 있지만, 문자열에서 숫자를 찾는 방식은 비효율적입니다. 따라서 이진 탐색을 사용하면 시간 복잡도를 크게 줄일 수 있습니다.  main문에서는 먼저 빠른 입력과 출력을 위해서 Buffer클래스를 사용하여 입력과 출력을 받아줍니다. StringTokenizer를 사용하여 공백을 구분하고 배열에 저장해 주고, 이진탐색에서 선행되어야 하는 정렬을 수행해줍니다. 그리고 이진 탐색함수로 받은 결과를 StringBuilder를 사용하여 결과를 추가해 줍니다. 이진탐색을 수행할 binarySearch 함수에서는 이진 탐색의 동작 방식인 시작점 left와 끝점 right..