순열
-
[백준]9662: N-Queen - JAVA문제풀이/백준 2021. 5. 2. 15:32
[백준]9662: N-Queen www.acmicpc.net/problem/96639663번: N-QueenN-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.www.acmicpc.net풀이프로그래머스에 있는 N-QUEEN문제와 동일한 문제이다. DP문제의 대표가 하노이의 탑이 있다면 순열 문제의 대표라고 할 수 있는 문제이다. 이전에 풀었던 적이 있지만 오래되어 다시 한번 풀어보았다. 다시 풀자니 역시 조금 헤메이는 부분이 있었다. 게다가 백준의 문제 설명이 부족한 것도 있다. 프로그래머스에는 문제 설명이 자세히 잘 되어 있으니 N-QUEEN문제는 프로그래머스에 푸는 것을 추천한다...
-
[백준]1339: 단어 수학 - JAVA문제풀이/백준 2021. 4. 24. 13:54
[백준]1339: 단어 수학 www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 풀이 백트랙킹을 사용하여 풀었다. 먼저 알파벳을 리스트에 중복 없이 저장한 다음, 0부터 숫자를 하나씩 올리며 알파벳에 숫자를 할당(?)해 주었다. 리스트의 길이만큼 숫자를 다 뽑았다면 원래의 문자열과 비교하여 자리수에 맞게 숫자 연산을 하여 MAX값을 찾아주었다. 풀이 코드의 구조를 보면 전형적인 백트랙킹 순열 문제와 같다. 이번 문제에서 어려웠던 부분은 문자열을 자리수에 맞..
-
[프로그래머스]여행경로 - JAVA문제풀이/프로그래머스 2021. 3. 2. 13:27
[프로그래머스]여행경로 programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 풀이 백트랙킹 + 순열을 사용해서 풀었다. 뽑는 순서에 따라 결과가 달라지기 때문이다. 또한 백트랙킹으로 조건에 맞는 모든 경우를 탐색하도록 하였다. 이때 중요한 점은 뽑을 수 있는 순서가 여러개가 될 수 있으며, 이 중에서 알파벳 순서가 앞서는 경로만을 return해야 한다. 아래 예제 2를 읽어보면 이해가 될 것이다..
-
[프로그래머스]N-Queen - JAVA문제풀이/프로그래머스 2021. 2. 14. 13:51
[프로그래머스]N-Queen programmers.co.kr/learn/courses/30/lessons/12952 코딩테스트 연습 - N-Queen 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 programmers.co.kr 풀이 순열을 사용하여 풀었다. 순열로 퀸의 순서를 뽑아준 후, 뽑은 퀸을 이전의 뽑았던 퀸의 위치와 비교하여 뽑을 수 있는 위치라면 재귀함수를 사용해 순환적으로 호출해주었고, 뽑을 수 없는 위치라면(행이 같거나 대각선 위치에 존재하거나) 퀸을 뽑지 않았다. 뽑을 때는 1차원 배열을 이용해 각 인덱스가 하나의 열을 나타내도록 하였다. ..
-
[백준]1759: 암호 만들기 - JAVA문제풀이/백준 2021. 2. 11. 20:55
[백준]1759: 암호 만들기 www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 순열을 사용한 백트랙킹문제! 결과가 사전 순서대로 저장되어야 하므로 sort를 해주었다. 그리고 값을 뽑을때 알파벳이 증가하는 순서대로만 뽑아야 하므로 compareTo 메소드를 사용하여 이전의 뽑은 값과 비교해 주었다. 또한 모음인지 체크하는 함수를 만들어 주었고 조건에 모든 문자를 다 뽑은 후에는 모음의 수, 자음의 수가 조건에 맞는지 확인한 후 맞다면 출력하도록 해주었다. 별..
-
[백준]17406: 배열 돌리기4 - JAVA문제풀이/백준 2021. 2. 9. 15:19
[백준]17406:배열 돌리기4 www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 풀이 회전 순서에 따라 결과가 바뀌므로 순열을 사용하였다. 순열로 K의 회전 순서를 뽑은 후 회전시켰고, 회전이 끝난 후 각 배열의 행의 최솟값을 계산해주었다. 순열은 어렵지 않았지만 회전하는 부분이 생각해주어야 할 조건이 많아서 시간이 오래걸렸다. 회전을 하기 위해 한 자리씩 이동할 때 회전 방향에 존재하는 가장 마지막 값들이 지위져 이 값들을 따..