백트래킹(Backtracking)
2023. 3. 18. 17:52
알고리즘/개념정리
백트래킹(Backtracking) 이란 백트래킹 이란 모든 경우의 수를 전부 고려하는 알고리즘 이다. 조금 더 자세하게 말하자면 현재 상태에서 가능한 모든 후보군을 따라가며 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되면 즉시 후보를 포기하면서 정답을 찾아가는 범용적 알고리즘이라고 한다. 상태 공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다. 백트래킹을 사용해 해결할 수 있는 문제는 주로 검색, 의사 결정, 최적화, 열거하기 등의 문제가 있다. 사실 백트래킹은 사용 가능한 경우가 많지만 시간복잡도가 보통 $2^n$ 이기 때문에 대부분의 문제는 동적 프로그래밍 또는 그리디 알고리즘 등으로 더 빠르게 해결할 수 있다. 그렇다고해서 백트래킹을 사용하..
피보나치 수 (Fibonacci numbers)
2023. 3. 17. 10:59
알고리즘/개념정리
피보나치 수 (Fibonacci numbers) 아마도 예전에 수학 시간에 배울 만큼 잘 알고 있는 수라서 모르는 사람이 많지 않을 것이라고 생각한다. 위키에서 정의한 피보나치 수는 다음과 같다. 첫 번째 숫자와 두 번째 숫자가 주어지고 세 번째 숫자 부터는 앞의 두 숫자의 합으로 구할 수 있다. 예를 들어, F(1) = 1 , F(2) = 1 일 때 F(3) = F(1) + F(2) 가 된다. 반복하게 되면 1, 1, 2, 3, 5, 8, ... 의 수열이 만들어진다. 참고 사이트 https://ko.wikipedia.org/wiki/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98_%EC%88%98 피보나치 수 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 피보..
유클리드 호제법 (Euclidean algorithm)
2023. 3. 17. 10:55
알고리즘/개념정리
유클리드 호제법 2개의 자연수 또는 정수의 최대공약수 를 구하는 알고리즘의 하나이다. 호제법 이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘이다. 2개의 자연수 a, b 가 있다고 했을 때 a 를 b 로 나눈 나머지 를 r 이라고 하면 (단, a>b ) a 와 b 의 최대공약수 는 b 와 r 의 최대공약수 와 같다. b 를 r 로 나눈 나머지 를 r’ → r 을 r’ 로 나눈 나머지 위의 과정을 반복해서 나머지가 0이 되었을 때의 수가 a 와 b 의 최대공약수 이다. 이런 과정을 거쳐 다음 정리를 이용해서 유클리드 호제법 이 성립하게 된다. 정리 a, b 는 정수, a 를 b 로 나눈 나머지가 r 이라고 하자. ( a ≥ b , r은 0 ≤ r < b 인 정수) a 와 b ..
그리디(Greedy) 알고리즘, 탐욕법
2023. 2. 28. 11:03
알고리즘/개념정리
그리디(Greedy) 알고리즘이란 그리디 알고리즘 은 단순하지만 강력한 문제 해결 방법이다. 국내에서는 그리디 알고리즘 을 탐욕법 으로 소개된다. 따라서, 그리디 알고리즘 이란 현재 상황에서 지금 당장 좋은 것만 고르는 방법 을 의미한다. 그리디 알고리즘은 주로 정렬 알고리즘과 짝을 이뤄 출제된다. 그리디 알고리즘 예제 그리디 알고리즘 을 설명하기 위해 간단한 예를 들어본다. 음식점의 계산을 도와주는 점원이 있다. 이때 거스름돈을 거스러줘야 하는데 500원, 100원, 50원, 10원 짜리 동전이 무한히 존재한다고 가정하자. 손님에게 거슬러줘야 하는 돈이 N 원일 때 거슬러줘야 할 동전의 최소 개수를 구하라. 이 문제는 그리디 알고리즘을 풀 수 있는 대표적인 문제라고 한다. 바로 가장 큰 화폐단위부터 돈..
자카드 유사도 (Jaccard Similarity) 이해하기
2023. 1. 23. 20:00
알고리즘/개념정리
자카드 유사도를 검색했을 때 자카드 유사도라는 단어보다는 자카드 인덱스(Jaccard Index), 자카드 거리(Jaccard Distance)와 같은 개념으로 된 설명이 더 많이 나오는 것 같았다. 먼저 자카드 유사도에 대해서 이해하기 전에 유사도에 대해서 알아봤다. 유사도 유사도란 A 와 B 가 얼마나 유사한지에 대해서 수치로 표현한 값을 말한다. 유사도를 측정하는 방법에는 아래와 같이 다양한 방법이 있다. 유클리디안 거리 맨해튼 거리 피어슨 상관계수 코사인 유사도 자카드 유사도 자카드 유사도 자카드 유사도에 대해서 간단하게 설명하자면 합집합을 교집합으로 나누면 된다. 따라서, 자카드 유사도의 공식은 다음과 같이 접을 수 있다. 자카드 유사도를 Python으로 구현해 보기 사실 자카드 유사도의 공식을..
XOR 연산
2022. 2. 2. 19:36
알고리즘/개념정리
알고리즘 문제풀 때 XOR 연산을 사용한다면 3가지만 기억하자. ^ 기호는 XOR 연산을 말한다. 1. XOR 연산은 순서에 상관없음 a ^ ( b ^ c ) = ( a ^ b ) ^ c 2. 자기 자신을 XOR 연산하면 0 이 나옴 a ^ a = 0 3. 0 과 XOR 연산하면 자기 자신이 나옴 a ^ 0 = a 문제 예시 3개의 점이 주어지고 정사각형을 만들기 위한 나머지 점을 구해라. 예시) (x1, y1), (x2, y2), (x3, y3) 의 3개의 점과 나머지 하나의 점을 통해 정사각형을 만들려고 한다. 나머지 점을 구해라. x1 ^ x2 ^ x3 을 했을 때 나오는 수가 나머지 한 점의 x 좌표가 된다. y1 ^ y2 ^ y3 을 했을 때 나오는 수가 나머지 한 점의 y 좌표가 된다. 따라서..
모듈러 연산 관련 블로그 메모
2019. 8. 27. 05:57
알고리즘/개념정리
https://www.crocus.co.kr/1231 모듈러 연산(Modular Arithmetic) 목차 1. 모듈러 연산 2. 모듈러 합동 3. 모듈러 연산의 속성 4. 모듈러 인버스 5. 확장 유클리드 알고리즘을 이용한 곱셈 역수(역원) 구하기 1. 모듈러 연산 몇 가지 중요한 암호 시스템은 계산 결과가 항상 0 - (.. www.crocus.co.kr https://johngrib.github.io/wiki/discrete-math-modular/ 모듈러 연산(나머지 연산) Modular Arithmetic johngrib.github.io
알고리즘 사이트 정리
2019. 7. 24. 11:00
알고리즘/개념정리
백준 알고리즘 온라인 저지 (BOJ) Baekjoon Online Judge Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다. www.acmicpc.net 프로그래머스 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! www.swexpertacademy.com LeetCode LeetCode - The World's Leading Online Programming Lea..