알고리즘 2

[알고리즘] N-Queen

백트래킹(BackTracking) 가능한 모든 방법을 탐색한다. 단, 한정 조건을 통해 유망성을 점검하고 유망하지 않으면 해당 경우의 수를 배제한다. N-Queen N*N 체스판에 N개의 퀸을 서로 공격할 수 없게 배치하는 경우의 수를 출력하는 문제이다. 나의 멍청했던 접근법 단순하게 2차원 배열을 생성하고 모든 값을 0으로 초기화한 후에, 퀸을 하나 두었을 때 공격 가능한 모든 칸을 1로 바꾸고 남아 있는 0 중에 하나에 퀸을 두고 또 1로 바꾸고... 이런식으로 구현을 하였다. 정말 단순하고 무식한 방법이었다. 모든 경우의 수를 보았기 때문에 시간은 엄청나게 소요되었고, 중복된 경우의 수도 횟수에 추가되어서 어마어마한 뻥튀기 결과값을 초래했다. 해답 우선, 2차원 배열을 생성할 필요가 없다. 1차원 ..

NotePad 2020.01.26

[알고리즘] 정렬(Sort)

n개의 숫자가 입력으로 주어졌을 때, 이를 사용자가 지정한 기준에 맞게 정렬하여 출력하는 알고리즘 1. 선택 정렬(Selection Sort) 현재 위치에 들어갈 값을 찾아 정렬하는 배열 현재 위치에 저장 될 값의 크기가 작냐, 크냐에 따라 __최소 선택 정렬(Min-Selection Sort)과 최대 선택 정렬(Max-Selection Sort)로 구분 최소 선택 정렬은 오름차순, 최대 선택 정렬은 내림차순 로직 정렬 되지 않은 인덱스의 맨 앞에서부터, 이를 포함한 그 이후의 배열값 중 가장 작은 값을 찾아간다. C++ STL : sort algorithm 헤더파일에 속해 있다. sort(start, end)를 이용하여 start 이상, end 미만에 있는 인자를 오름차순(default)으로 정렬해주는..

NotePad 2020.01.14
반응형