[algorithm] 백준 - 이전 순열
이전 순열 이전 순열은 다음 순열과 비슷한 방식으로 푼다. 순열을 나열했을 때 주어진 순열 이전 순열을 출력하는 문제이다. 1, 3, 2을 예시로 들어본다면, 이전 순열은 1, 2, 3이 된다. 1, 2, 4, 3를 예시로 들어본다면, 이전 순열은 1, 2, 3, 4가 된다. 1, 3, 2, 4의 이전 순열은 1, 2, 4, 3이 된다. 1, 2, 3, 4의 이전 순열은 없으므로 -1을 출력한다. 이전 순열이 존재할 수 있는 조건은 arr[i - 1] > arr[i]가 존재해야한다. 뒤에서 앞으로 반복문을 수행 후, 이 조건에 만족하는 수를 기준으로 양쪽으로 나눈다. 이후 arr[i - 1]보다 작은 수를 arr[i] 쪽 순열을 뒤에서 앞으로 조회 후 swap한다. 그 후 arr[i] 쪽 순열을 내림차순..
2020. 10. 29.
[algorithm] 테트로미노
테트로미노 회전과 대칭이 가능하다. 테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램 dfs를 이용하여 depth 4를 거쳤을 때 테르로미노 형태로 접근할 수 있다. 회전과 대칭했을 때도 동일하다. 하지만 예외에 대해서는 하드코딩으로 접근해야 한다. dfs로 구할 수 없는 경우이기 때문이다. #include using namespace std; int directx[] = {0,0,1,-1}; int directy[] = {1,-1,0,0}; int termino[4][4][2] = { {{0,0},{0,1},{0,2},{1,1}}, {{1,0},{0,1},{1,1},{2,1}}, {{0,0},{1,0},{1,1},{2,0}}, {{0,1},{1,0},{..
2020. 10. 28.
[algorithm] 백준 - 다음 순열
순열을 나열했을 때 주어진 순열 다음 순열을 출력하는 문제이다. 1, 2, 3을 예시로 들어본다면, 다음 순열은 1, 3, 2가 된다. 1, 2, 3, 4를 예시로 들어본다면, 다음 순열은 1, 2, 4, 3이 된다. 1, 2, 4, 3의 다음 순열은 1, 3, 2, 4가 된다. 4, 3, 2, 1의 다음 순열은 없으므로 -1을 출력한다. 다음 순열이 존재할 수 있는 조건은 arr[i - 1] < arr[i]가 존재해야한다. 뒤에서 앞으로 반복문을 수행 후, 이 조건에 만족하는 수를 기준으로 양쪽으로 나눈다. 이후 arr[i - 1]보다 큰 수를 arr[i] 쪽 순열을 뒤에서 앞으로 조회 후 swap한다. 그 후 arr[i] 쪽 순열을 오름차순 sort하면 다음 순열이다. 자세히 살펴보자면, arr[0]..
2020. 10. 28.
