본문 바로가기

알고리즘28

[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] Graph-Theory Graph-Theory - Graph 자료구조를 기반으로 하는 알고리즘들이다. - Graph는 Node와 이를 연결하는 Edge로 구성되어있으며, 네트워크 토폴로지, 관계데이터, 전산, 수학에서 사용된다. 1. Graph 탐색 알고리즘 - Graph 상의 모든 Node를 방문하여 탐색하는 알고리즘 - DFS와 BFS가 있다. 2. 최단경로 알고리즘 - 두 노드 사이의 최단 경로를 찾는 알고리즘. 가중치가 없는 graph에서는 BFS를 사용할 수 있으며, 가중치가 있는 graph에서는 다익스트라, 벨만-포드, 플로이드-워셜 알고리즘이 사용된다. 3. 최소신장트리 알고리즘 - graph에서 모든 노드를 연결하면서 가중치의 합이 최소가 되는 트리를 찾는 알고리즘. - 크루스칼, 프림 등이 있다. 4. 네트워크.. 2023. 3. 31.
[Lv.2] 튜플(카카오 인턴십 코딩테스트) 1. 문제 셀수있는 수량의 순서있는 열거 또는 어떤 순서를 따르는 요소들의 모음을 튜플(tuple)이라고 합니다. n개의 요소를 가진 튜플을 n-튜플(n-tuple)이라고 하며, 다음과 같이 표현할 수 있습니다. (a1, a2, a3, ..., an) 튜플은 다음과 같은 성질을 가지고 있습니다. 중복된 원소가 있을 수 있습니다. ex : (2, 3, 1, 2) 원소에 정해진 순서가 있으며, 원소의 순서가 다르면 서로 다른 튜플입니다. ex : (1, 2, 3) ≠ (1, 3, 2) 튜플의 원소 개수는 유한합니다. 원소의 개수가 n개이고, 중복되는 원소가 없는 튜플 (a1, a2, a3, ..., an)이 주어질 때(단, a1, a2, ..., an은 자연수), 이는 다음과 같이 집합 기호 '{', '}'.. 2023. 2. 20.
[Lv.2] 위장 (Hash와 경우의 수) 1. 문제 스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다. 예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다. 종류 이름 얼굴 동그란 안경, 검정 선글라스 상의 파란색 티셔츠 하의 청바지 겉옷 긴 코트 스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다. 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다. 같은 이름을 가진 의상은 존재하지 않습니다. cloth.. 2023. 2. 20.
[Lv.2] 멀리 뛰기 (피보나치 수열과 경우의 수) 1. 문제 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2칸) 의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다. 제한 사항 n은 1 이상, 2000 이하인 정수입니다. 입출력 예 4 5 3 3 입출력 예 설명 입출력 예 #1 위에서 설명한 내용과 같습니다. 입출력 .. 2023. 2. 14.

티스토리툴바