알고리즘5 [ 알고리즘 ] Next Permutation ( with 백준 10972 ) Next Permutation → 현 순열에서 사전 순으로 다음 순열 생성 → 입력 받은 배열을 오름차순으로 정렬 후 구한다. → 주로 do-while문이 사용 next permutation이 필요한 상황 데이터가 537으로 들어왔을 때 사전순으로 순열을 만들면 4개밖에 나오지않는다. 실제 나와야하는 값은 6개가 나와야한다. next permutation을 사용해 다음 순열 구하는 방법 - 오름차순에서 내림차순으로 순열을 모두 뽑아내고 싶으면 처음엔 꼭 미리 오름차순 정렬하기 - 예시) 10 3 9 8 7 6 5 2 1 의 다음 순열 찾기 [ 해당 데이터는 배열에 들어있다고 가정 ] 1. 꼭대기 인덱스 찾기 - 해당 예시에선 9가 꼭대기 - [ top = N(데이터 개수)-1 = 배열의 끝]로 초기화 후.. 2024. 2. 26. [ 알고리즘 ] 순열, 조합, 부분집합 순열 → 서로 다른 n개의 원소 중 r개를 뽑아 나열하는 것 → 순서가 존재한다. 구현방법 예시) 1,2,3,4 숫자카드가 있을 때 숫자카드를 중복으로 사용하지않고 만들 수 있는 3자리 수를 모두 출력하시오 1. 반복문 public static void main(String[] args) { for (int i = 1; i < 5; i++) { for (int k = 1; k < 5; k++) { if (i != k) { // 각 자리 숫자는 서로 달라야한다. for (int j = 1; j < 5; j++) { if (k != j && i != j) { // 각 자리 숫자는 서로 달라야한다. System.out.println(i + "" + k + "" + j); } } } } } } 2. 재귀 - 숫.. 2024. 2. 25. [ 알고리즘 ] 너비우선탐색 BFS - JAVA [ 특징 ] 그래프 완전 탐색 시작노드에서 출발해 시작노드를 기준으로 가장 가까운 노드를 먼저 방문한다. 그렇기에 목표노드까지 경로가 여러 개일 경우 최단경로를 보장한다. 큐 or FIFO를 이용해 구현한다. [ 시간복잡도 ] O(V+E) [ 구현시 고려해야 하는 점 ] DFS와 동일하게 방문했던 노드는 다시 방문하지않는다. [ 큐로 알아보는 탐색 순서 ] 탐색순서 1 - 2 - 3 - 5 - 6 - 4 2024. 2. 16. [ 알고리즘 ] 깊이우선탐색 DFS - JAVA [ 특징 ] 그래프 완전 탐색 기법으로 모든 노드를 검색한다. 시작노드에서 탐색할 쪽의 분기를 정해 최대깊이까지 탐색 후 다른 쪽 분기로 이동해 다시 탐색 = 넓게 탐색 전 깊이 탐색 재귀함수 or 스택을 이용하여 구현 - 순환 알고리즘의 형태 [ 시간복잡도 ] 인접리스트로 표현된 경우 O(V+E) [ V : 노드 수 , E : 에지 수 ] 인접행렬로 표현된 경우 O(N^2) 장점 : 단지 현 경로상의 노드만을 기억하면 되므로 저장공간의 수요가 비교적 적다. : 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. 단점 : 단순 검색 속도는 BFS에 비하면 느리다. : 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 DFS는 해에 다다르면 탐색을 끝내버.. 2023. 11. 4. [ 알고리즘 ] 브루트 포스 ( brute force ) 알고리즘 브루트 포스 (brute : 무식한) 이름이 무식한 힘인데 이름답게 완전 탐색 알고리즘으로 컴퓨터의 빠른 연산능력을 이용해 나올 수 있는 모든 경우의 수를 탐색하여 조건에 충족하는 결과만을 추출한다. → 고등학교 때 확률에서 경우의 수 배울 때 답을 잘 모르겠어서 모든 경우의 수를 구해 답을 구하는 우리의 노가다를 생각하면 이해가 쉽다 ദ്ദി ´•ᴗ•ก)՞ ՞ 선형구조를 전체적으로 탐색하는 순차 탐색, 비선현 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 기본적인 도구들이다. 브루트 포스 알고리즘의 장단점 장점 - 해답을 못 찾아낼 확률이 낮고 문제해결(설계)는 빠르게 할 수 있다. → 모든 경우의 수를 탐색하기에 충족조건만 틀리지 않았다면 예외가 발생하지 않는다. 단.. 2023. 2. 21. 이전 1 다음
