CodeDrive

문제:

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.

체스판의 가로 세로의 길이 n이 매개변수로 주어질 때 , n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution 함수를 완성해주세요.

풀이 방법:

 되추적 방법을 사용하는 대표적인 예시인 문제이다. 따라서 queens에서는 각 col별로 queen을 배치하는데 우선 promising이라는 함수에서 이전에 배치한 col을 기준으로 해당 인덱스에 queen을 배치할 수 있는지 판단해준다. 모든 방법을 다 판별해주는 방법도 생각할 수 있지만 그럴 경우 n이 커짐에 따라 많은 시간이 발생할 것이다. 따라서 promising이라는 되추적 판단을 해주는 함수로 인해서 많은 시간을 단축 할 수 있었다.

문제 링크:

https://programmers.co.kr/learn/courses/30/lessons/12952

문제:

풀이 방법:

 입출력 예시를 통해서 살펴 보면 2번선수의 경우에는 모든 경기기록이 있어서 순위를 알 수 있지만 5번 선수는 2번 선수와의 기록이 있지만 순위를 유추할 수 있다. 왜냐하면 2번이 1,3,4번 선수한테 졌는데 5번이 2번한테 졌으므로 5번은 당연히 1,3,4번 선수한테 진다는 것을 알 수 있다.(1,3,4 > 2 > 5) 또한 2번이 5번을 이겼기 때문에 5번이 이긴 사람도 당연히 이길 수 있다. (이 문제에서는 이러한 케이스가 없긴 하다.)

 처음에는 리스트로 했더니 시간초과가 발생해서 이를 set으로 바꿔서 했더니 시간초과가 발생하지 않았다.

문제 링크:

문제:

풀이 방법:

문제 링크:

문제:

문제 풀이:

문제:

문제 풀이:

문제:

문제 풀이:

문제 설명:

문제 풀이:

먼저 표의 현황을 깔끔하게 정리를 하기 위해서 tickets을 반복문으로 돌아가면서 이를 딕셔너리 타입(해시) 방식으로 정렬을 하였다. 매번 추가하면서 정렬을 한 이유는 만약 가능한 경로가 여러개라면 알파벳 순서가 앞서는 경로를 우선으로 해야하기 때문이다.

티켓을 정리한 뒤에 재귀적으로 탐색을 하는 함수인 travel에 ticket의 정보를 담고 있는 answer_set, 실제 경로인 answer, 출발하는 공항의 이름인 start, 그리고 모든 항공권을 사용했는지 탐색해야하므로 티켓의 갯수인 K 와 몇 개를 사용했는지 알려주는 count를 사용하였다.

처음에는 무조건 ICN에서 시작을 한다는 조건이 있었으므로 초기값은 ICN으로 시작한다. travel 함수에는 세 가지 조건이 존재한다. 

1. count == K 일 때

종료 조건으로 모든 티켓을 다 사용한 경우에 해당한다. 따라서 True를 반환한다.

2. 잘못 경로를 탐색해서 들어갔을 경우

해시 구조를 통해서 티켓을 정리했다보니 B 공항으로 도착을 하긴 했지만 B 공항에서 출발을 하는 티켓이 없을 수도 있다. 따라서 이 경우에 이 값을 찾으려 하면 error가 발생하기 때문에 예외처리구문을 사용해서 이 case를 탐지했다. 이 경우가 발생한거면 잘못된 경로를 온 것이기 때문에 answer의 마지막 값을 빼주고 잘못된 경로이므로 False를 반환한다.

3. 위 두 경우가 아닐 때

해시로 정리한 티켓을 기준으로 하나씩 경로를 늘려가면서 탐색해본다. 

위 과정을 거치다보면 answer를 구할 수 있게 된다.

문제 설명:

문제 풀이: