Algorithm/Intermediate (20) 썸네일형 리스트형 브루트포스[3]:백트레킹(backtracking) 알고리즘 중 하나인 백트레킹 설명과 문제풀이. 백트레킹(backtracking, 퇴각검샘) 백트레킹은 유망성 검사를 만족하는 경우 모든 조합의 수를 살펴보는 것이다. 유망성 검사를 만족하지 않은 경우 많은 부분 조합들을 배제할 수 있고 모든 경우의 수를 모두 찾는 것보다 훨씬 빠르고 풀이 시간이 단축된다. 구현방법은 DFS와 같은 구조이지만 유망성 점검을 하냐 안하냐로 구분된다. 어떤 노드의 유망성 점검후, 유망하지 않으면 그 노드의 부모노드로 되돌아간 후 다른 자손노드를 검색한다. 브루트포스는 모든 방법을 만드는 것이나, 백트레킹은 아무리 해봤자 의미가 없다 싶을 때 호출을 중단하는 것. 백트레킹 알고리즘의 설명에 관해서 매우 설명이 잘되있는 블로그가 있기 때문에 참고하면 좋을 것 같다! idea-sk.. 비트마스크(BitMask) 비트마스크를 활용한 테크닉과 기법 비트마스크 자체는 알고리즘이 아니지만 다른 알고리즘과 같이 사용되어 어렵게 느껴질 수가 있다. 비트마스크(BitMask) 정수를 이진수 형태로 표현하여 비트연산을 활용하는 방법 이를 활용하면 비트연산을 통해 삽입,삭제,조회 등이 간단해짐 시간복잡도 O(1)으로 더 빠른 연산이 가능 메모리를 적게 사용함 비트 연산 AND (&) OR (|) XOR (^) SHIFT (>>,> n; for (int i = 0; i > a[i]; } for (int i = 0; i < (1 maps[i][j]; if (maps[i][j] == 'R') { r.first = i; r.second = j; } if (maps[i][j] == 'B') { b.firs.. 브루트 포스[1]:순열 (Brute Force[1]:Permutation) 암호학에서의 브루트 포스(brute force attack)가 아닌알고리즘의 브루트 포스(brute force search)에 관한 것을 작성한다. 브루트 포스(brute force)brute: 무식한, force: 힘 무식한 힘으로 해석되며 즉, 무식하게 다해보는 것이다. 완전탐색 알고리즘: 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다. 이러한 브루트 포스방법 중에서 순열에 관해서 소개를 하려고 한다. 순열(permutation) 수학에서, 순열 또는 치환은 서로 다른 n개의 원소에서 r(≤n)개를 뽑아 한 줄로 세우는 경우의 수이며, nPr로 나타낸다. 순서가 부여된 임의의 집합을 다른 순서.. 깊이 우선 탐색(DFS, Depth-First Search) ● 1. 깊이 우선 탐색의 개념● 2. 깊이 우선 탐색의 특징● 3. 깊이 우선 탐색의 구현그래프 탐색이란그래프 안에 어떤 버텍스들이 있는지 알고 싶을 때 사용한다.DFS는 버텍스의 자식들을 먼저 탐색하고, BFS는 버텍스의 형제들을 먼저 탐색한다.ex) 미로 탈출, 최단거리 탐색, 특정 지점에서 다른 점으로 갈 수 있는지 등의 문제를 해결할때 사용하는 알고리즘 1. 깊이 우선 탐색의 개념 깊이우선 탐색 (Depth First Search) : 탐색 트리의 특정 노드를 방문하여 확인한 후 그 노드와 연결된 자식노드 중에서 우선 순위가 가장 빠른 하나를 선택해 방문하며 그후 더 이상 방문할 곳이 없으면 이전 상태로 되돌아가는 탐색 방법이다.이때 탐색 과정이 한없이 깊이 진행되는 것을 막기 위해 깊이 .. 이전 1 2 3 다음
