BJ S1 1342 행운의 문자열 문제링크 https://www.acmicpc.net/problem/1342 1342번: 행운의 문자열 민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작 www.acmicpc.net * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 동영상 설명 1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다. 더보기 https://youtu.be/LIBUyTyZ-F0 소스보기 동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다. 소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼..

순열은 앞서 살펴봤던 visited를 이용하는 방식이외에도 여러 가지 방식으로 작성이 가능하다. 여기서는 swap 을 이용해서 순열을 구하는 방식에 대해 살펴보자. 기본적인 컨셉은 아래와 같다. - swap: 요소와 요소의 위치를 서로 변경한다. - depth: 선택할 수 있는 요소의 범위를 조절한다. 진행 과정 먼저 최초의 배열 {A, B, C, D}가 있고 depth 0에서 swap 되는 단계는 다음과 같을 것이다. 물론 depth0-1인 BACD는 depth0-0 인 ABCD에 대한 모든 하위 depth가 종료된 후 진행될것이다. 이제 depth0-0의 하위인 depth1의 동작을 살펴보자. 첫 번째 자리는 A로 고정된 상태에서 나머지 요소들이 swap 대상이 된다. 이제 depth1-0이 종료되면..

앞선 포스트에서 살펴봤듯이 순열을 구현하기 위해 필요한 개념은 3가지이다. 1. 순서대로 나열 - 반복문을 통해 순차적으로 접근한다. 2. 중복을 허용하지 않음 - 이미 사용한 요소가 무엇인지 저장해놓는다. 이를 위해 visited라는 이름의 배열을 사용한다. 3. 재귀를 통한 접근 - 선택해야할 요소들을 하나씩 줄여가면서 자신 호출 4개의 원소를 가진 배열을 만들고 여기서 3개를 선택해서 나열하는 경우의 수를 조사해보자. private static char[] src = {'A', 'B', 'C', 'D'}; 기본적인 코드의 흐름은 다음과 같다. 코드에 대한 설명은 주석으로 대체한다. /** * 순열을 만들고 출력하는 메서드 * @param r 선택할 요소의 개수 * @param current 현재 선..

순열의 정의 순열(Permutation)이란 n개의 원소에서 r개를 중복을 허용하지 않고 선택해서 순서대로 늘어놓은 것을 말하며 nPr이라고 표기한다. 순열의 전개 과정 4개의 원소 {1,2,3,4}에서 3개를 선택해서 순서대로 나열하는 방법에 대해 생각해보자. 맨 처음은 4개의 원소가 모두 올 수 있다. 그 다음은 각 경우에 대해 중복을 허용하지 않으므로 1st에서 선택되지 않은 3녀석이 각각 올 수 있다. 즉 4*3 가지가 가능하다. 여기서 1-4와 4-1은 당연히 다르다. 우리는 순서대로 나열하고 있다는 점이 중요하다.(만약 순서가 상관 없이 뽑기만 진행한다면 조합이 된다.) 동일한 절차를 거치면 우리가 원하는 순열을 얻을 수 있다. 드디어 모든 절차가 끝났고 4개의 원소에서 중복 없이 3개를 선택..