ComputerScience/알고리즘, 프로그래머스54 [Algorithm] Greedy (그리디/탐욕) - 그리디 알고리즘은 최적화 문제에서 주로 사용된다. - 단계별로 가장 좋아 보이는 선택을 함으로써 전체적으로 최적의 해답을 찾으려고 시도한다. - 항상 최적의 해를 찾지는 못하지만, 많은 경우에 효율적인 근사치를 찾을 수 있다. Q) 거스름돈을 지불해야 하는 금액이 주어졌을 때, 동전의 개수를 최소로 하려면 어떤 동전을 사용해야 할까? - 동전의 종류가 [25, 10, 5, 1]로 주어진다고 가정한다. A1) 아이디어 - 주어진 금액에서 동전의 개수를 최소로 하려면 가장 금액이 큰 동전부터 차례대로 남은금액에 최대한 개수를 채우면 된다. - 상식적인 아이디어이다. - 이를 구현하면 다음과 같다. - 상식적으로 최적의 해인 것 같은데, 그리디 알고리즘이 항상 최적의 해를 찾지 못하는 이유는? A) 각 단.. 2023. 4. 10. [Algorithm] 완전탐색 (JS) - 3 : 비트마스킹(Bitmasking) - 나올 수 있는 모든 경우의 수가 둘 중 하나로부터 나오는 경우 유용하게 사용할 수 있다 1. 비트마스킹이란 ? - 정수 값을 이진 비트로 표현하여 비트 단위 연산을 사용해 특정한 작업을 수행하는 기법 - 웹에서는 플래그, 설정, 퍼미션 등을 효율적으로 관리할 수 있다. - 일반적으로 비트 연산자(AND, OR, XOR, NOT, SHIFT)를 사용한다. - React에서 비트마스킹을 사용하여 여러 설정 옵션을 관리할 수 있다. - '&' 는 비트 AND 연산자로, 각 정수의 이진표현에서 같은 위치에 있는 비트를 비교하여 두 비트가 모두 1인 경우에만 결과의 해당 위치의 비트를 1로 설정한다. - 예를 들어, 5 & 4 는 0101 과 0100의 비트AND연산을 시행하면 0101 0100 0100 (답.. 2023. 4. 6. [Algorithm] 완전탐색 (JS) - 2 : 백트래킹(Back Tracking) 1. 백트래킹이란 ? : - 완전탐색의 기법으로, 주로 결정문제(경로찾기, 스도쿠, 여덟 퀸 문제 등)를 해결하는 데 사용된다. - 가능한 모든 해(space of states)를 탐색하여 문제의 해결책을 찾는다. - 이 과정에서 현재 해가 문제의 조건을 만족하지 않으면 이전 단계로 돌아가서 다른 선택지를 탐색한다. - 이를 '되돌리기'라는 개념으로 사용한다. - 가지치기(Pruning)를 통해 탐색 공간을 줄일 수 있어, 불필요한 경우의 수를 줄여 시간복잡도를 개선할 수 있다. 2. 구현 : 스도쿠 퍼즐 풀기 - 재귀를 사용하여 9x9 예제의 스도쿠 퍼즐을 백트래킹기법을 사용해 해결하는 예제이다. 천천히 읽어보자(뒤에 시각화 있음) 3. 리액트를 통한 시각화하기 - 코드만 읽으면 이해하기 어려우므로 시.. 2023. 4. 4. [Algorithm] 완전탐색 (JS) - 1 : 브루트 포스(Brute Force) 1. 완전탐색이란 ? - 가능한 모든 경우의 수를 탐색하며 최적의 해결책을 찾는 방법. - 완전탐색 알고리즘은 문제의 가능한 모든 해를 체계적으로 검사하고, 그 중에서 최적의 해를 선택한다. - 상대적으로 구현이 간단하고, 해가 존재하면 항상 찾게 됨. - 경우의 수에 따라 실행 시간이 비례하기 때문에 입력 값의 범위가 작은 경우 유용. 2. 브루트포스 - 브루트 포스는 가장 기본적인 완전탐색 방법으로, 가능한 모든 경우의 수를 탐색한다. 재귀함수를 이용한 구현 반복문을 사용한 구현 - 쉽게 말해 password같은 문자열이 있다면, length가 1인 'a' 부터 length가 8인 'zzzzzzzz' 까지 하나씩 올려가면서 비교하여 맞으면 종료하고 그 값을 반환하는 것. 2023. 4. 4. [Algorithm] 트리 자료형(Tree Data Structure)과 트리 순회 1. 트리자료형이란 ? - 계층적 자료구조. - Node들로 구성되며, Edge(간선)로 연결되어 있다. - 가장 상위에 있는 Node를 루트노드 라고 부르며, 각 노드는 0개 이상의 자식 노트를 가질 수 있다. - 트리에서 노드가 자식 노드를 가지지 않는 경우 그 노드를 리프(leaf)노드라고 부른다. 2. 트리 순회 - 트리의 노드를 시스테마틱한(체계적이고 조직적인) 방식으로 방문하는 과정. - 트리순회의 목표는 트리의 모든 노드를 효과적으로 방문하는 것이다. 1) 전위 순회 (Pre-order Traversal) : 전위 순회에서는 루트 노드를 먼저 방문한 후, 왼쪽 서브트리를 순회하고, 그 다음 오른쪽 서브트리를 순회한다. 루트 -> 왼쪽 -> 오른쪽 2) 중위 순회 (In-order Traver.. 2023. 4. 3. [Algorithm] Graph-Theory - 3 : DFS와 BFS 한방에 이해하기. 1. DFS(깊이우선탐색) : 그래프나 트리를 탐색하는 알고리즘 중 하나. 시작 노드에서 깊이 우선 탐색을 수행하여 가능한 모든 경로를 탐색한다. - 재귀적 방식이나 스택을 사용하여 구현할 수 있다. - 경로 찾기, 연결요소 찾기, 사이클 검출 등의 사례로 사용된다. 2. 구현 dfs알고리즘 함수의 예시(재귀함수를 사용한 예시) - 인접리스트로 표현된 그래프, 시작노드, 목표노드를 매개변수로 받아 시작노드에서 목표노드까지의 경로를 찾아 배열로 반환한다. - 경로를 찾지 못한 경우 null을 반환한다. dfs 알고리즘 함수의 예시(stack) - 재귀 대신 while루프를 사용하여 stack에 있는 모든 노드를 처리한다. - 스택의 강 항목은 현재 노드와 해당 노드까지의 경로를 포함한다. 3. 사용해보기 .. 2023. 4. 3. [Algorithm] Graph-Theory - 2 : JS로 구현과 시각화 1. 그래프 클래스 정의 main.js 2. 예제 그래프 생성 main.js 3. HTML 시각화 index.html 4. 결과 확인 2023. 3. 31. [Algorithm] Graph-Theory Graph-Theory - Graph 자료구조를 기반으로 하는 알고리즘들이다. - Graph는 Node와 이를 연결하는 Edge로 구성되어있으며, 네트워크 토폴로지, 관계데이터, 전산, 수학에서 사용된다. 1. Graph 탐색 알고리즘 - Graph 상의 모든 Node를 방문하여 탐색하는 알고리즘 - DFS와 BFS가 있다. 2. 최단경로 알고리즘 - 두 노드 사이의 최단 경로를 찾는 알고리즘. 가중치가 없는 graph에서는 BFS를 사용할 수 있으며, 가중치가 있는 graph에서는 다익스트라, 벨만-포드, 플로이드-워셜 알고리즘이 사용된다. 3. 최소신장트리 알고리즘 - graph에서 모든 노드를 연결하면서 가중치의 합이 최소가 되는 트리를 찾는 알고리즘. - 크루스칼, 프림 등이 있다. 4. 네트워크.. 2023. 3. 31. 이전 1 2 3 4 ··· 7 다음
