![]()
문제 https://school.programmers.co.kr/learn/courses/30/lessons/64064 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 전형적인 백트래킹 문제이다. 우선 응모자아이디를 이용해서 조합을 만들고, 만들어진 조합의 크기가 불량 사용자 아이디 목록의 크기와 동일해질 경우 매핑을 시작한다. 매핑은 다음과 같은 과정으로 이루어진다. 후보 아이디 목록과 불량 사용자 아이디 목록은 1:1로 매칭한다. 만약 길이가 다를 경우 매핑은 실패한다. *을 제외한 글자가 다를 경우 매핑은 실패한다. 매핑이 성공했다면, 결과..
![]()
문제 https://school.programmers.co.kr/learn/courses/30/lessons/12952 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 전형적인 백트래킹 문제이다. 2차원 배열을 사용해서 풀기보다는 조금 특별하게 풀고 싶었다. 따라서 Queen이라는 데이터클래스를 가지는 배열을 통해서 각자의 위치에 따라 공격할 수 있는 여부를 따지고 싶었다. 그래서 n만큼의 depth를 탐색하는 재귀함수를 작성해서, Queen의 column위치를 계속해서 조정했다. 배열에 Queen을 넣고, 해당 퀸의 추가가 적절한 추가인지 검사..
![]()
되추적 알고리즘을 이용한 0-1 배낭 채우기를 앞에서 해보았다. 이번에는 분기한정을 이용한 0-1 배낭 채우기를 해보겠다. 되추적 알고리즘과 어떤 차이가 있는지를 중점으로 보면 될 것이다. -앞선 문제와 동일하게 n= 보석의 개수 W= 배낭의 용량 n=4, W=13 p(profit)=[40,30,50,10], w(weight)=[2,5,10,5], p/w(단위 무게별 이익)=[20,6,5,2] 1. 앞선 0-1 배낭 채우기 문제와 같이 무게별 이익이 큰 순서대로 재 정렬한다. 2. 되추적 알고리즘과 상태 공간 트리를 구성한다. 3. 트리는 (profit, totweight, bound)로 이루어진다. profit은 내가 가방에 담은 이익 totweight은 내가 가방에 담은 무게 bound는 내가 탐색한..
![]()
문제 n * m 체스보드에서 기사의 여행 문제를 해결하는 백트래킹 알고리즘을 구현하시오. Knight's Tour 문제는 해밀턴 경로(path)와 해밀턴 회로(circuit, cycle)를 찾는 문제로 구분할 수 있다. 해밀턴 회로는 출발 정점과 무관하게 회로의 수를 구할 수 있고, 해밀턴 경로는 출발 정점에 따라 가능한 경로의 수가 달라짐에 유의하시오. 입력 첫 번째 줄에 체스보드의 크기 n(행의 크기)과 m(열의 크기)이 주어진다. 두 번째 줄에 출발 정점의 개수 T가 주어진다. 이후로 T개의 출발정점이 i(row), j(col)의 쌍으로 주어진다. 출력 첫 번째 줄에 해밀턴 회로의 개수를 출력한다. 두 번째 줄부터 입력에서 주어진 출발정점 각각에 대해 해밀턴 경로의 수를 한 줄에 하나씩 출력한다. ..
![]()
문제 주어진 무방향 무가 중치 그래프 G = (V, E)에서 해밀턴 회로의 개수를 출력하시오. Algorithm 5.6을 구현할 때, 출발 정점은 1로 간주한다는 것을 주의하시오. 입력 첫째 줄에 정점의 개수 n과 간선의 개수 m이 주어진다. 둘째 줄부터 m개의 간선이 주어진다. 출력 첫째 줄에 해밀턴 회로의 개수를 출력한다. 문제 해석 이 문제를 풀기 위해서는 해밀턴 회로와 해밀턴 경로의 차이를 알아야 한다. 해밀턴 회로 VS 해밀턴 경로 해밀턴 회로 한 정점에서 출발을 해 모든 정점을 딱 한 번씩 방문하고 다시 출발 정점으로 돌아와야 한다. 출발 정점과 해밀턴 회로는 무관하다. 해밀턴 경로 해밀턴 경로는 해밀턴 회로와 다르게 출발 정점에 따라 값이 다르다. 한 정점에서 출발해서 모든 정점을 한 번씩 ..
![]()
문제 주어진 평면 그래프 G = (V, E)에 대해서 인접한 지역을 서로 다른 색으로 색칠하기 위해 필요한 최소 색의 수 m의 값과 해당하는 m의 값으로 색칠할 수 있는 경우의 수를 출력하시오. 단, 그래프의 입력은 간선의 집합으로 주어지고, 주어진 그래프는 평면 그래프라고 가정해도 된다. 입력 첫 줄에 정점의 수 n과 간선의 수 k가 주어진다. 둘째 줄부터 k개의 간선이 주어진다. 출력 첫째 줄에 색칠 가능한 최소의 m값을 출력한다. 둘째 줄에 해당 m값으로 색칠할 수 있는 경우의 수를 출력한다. 문제 해석 그림과 같이 인접해 있는 영역끼리는 서로 다른 색을 칠해야 한다. 여기서 인접한다의 의미는 영역들끼리 가로 세로중 하나라도 맞닿아있어야 한다. v1과 v3, v2는 가로 세로 중 한 영역이 맞닿아있..
![]()
문제 n개의 원소를 가진 정수의 집합 S가 주어지고, 임의의 정수 W가 주어졌을 때, 합이 W가 되는 부분집합의 개수와 각 부분집합을 출력하도록 하시오. 입력 첫 줄에 원소의 개수 n과 임의의 정수 W가 주어진다. 둘째 줄에 n개의 정수가 주어진다. 출력 첫 줄에 원소의 합이 W가 되는 부분집합의 개수를 출력한다. 둘째 줄부터 원소의 합이 W가 되는 모든 부분집합을 한 줄에 하나씩 출력한다. 단, 부분집합에서의 원소 출력 순서는 주어진 S의 원소 순서와 동일해야 한다. (백트래킹 순서대로) ※처음 문제를 보고 떠오른 생각 주어진 집합 S의 원소들을 더해서 W를 만들어야 한다. Backtracking을 이용해서 모든 경우의 수를 구한다. 유망성검사를 통해서 가지치기를 함. 만약 뽑은 원소들의 합이 W면 종..
![]()
Backtracking 되추적 알고리즘이라고 한다. 결과를 찾는 도중 막히면 다시 되돌아가서 다시 결과를 찾음. 모든 노드를 탐색해서 만드는 DFS와 비슷하다. DFS vs Backtracking DFS는 모든 노드를 탐색한다. Backtracking은 모든 노드를 탐색하지만, 특정 조건을 설정해서 이 경로가 해가 안될 거라고 판단이 되면 경로를 이탈하고 다시 되돌아간다. --> 이것을 가지치기라고 한다. 가지치기를 통해서 불필요한 경로를 차단해서 효율성을 높일 수 있다. Promising 유망성 검사 - 이 경로가 특정조건을 걸어서 해가 될 것인지 안될 것인지 판단함. nonpromising 하다면, 그 경로는 끝까지 갈 필요가 없으므로, 다시 되돌아감. promising 하다면 계속 진행함. Prun..
