백트래킹(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으로 구현해 보기 사실 자카드 유사도의 공식을..
Strings - Alphabet Rangoli (Python)
2023. 1. 23. 17:24
알고리즘/HackerRank
Summary 이 문제를 보자마자 문자열의 인덱스에 대한 이해와 join() 함수 그리고 center() 함수를 사용해서 풀면 되지 않을까 하는 생각이 들었다. 문제를 풀기 전에 Rangoli 가 궁금해서 무엇인지 찾아봤다. 인도의 전통 문양이라고 하고 아래와 같은 패턴을 가지고 있어서 이 문제의 이름을 Rangoli 라고 지은게 아닌가 싶었다. 다시 돌아와 우선 알파벳을 가져와 문자열로 저장해주었다. import string alpha = string.ascii_lowercase 알파벳 소문자를 가져오는 방법에는 여러가지가 있어서 생각나는 대로 가져오면 된다. 나는 구글링을 통해 string 라이브러리를 사용해서 알파벳 소문자를 가져왔다. 그리고 알파벳을 문제가 원하는 순서에 맞게 출력을 하려고 반복문..
Strings - Find a string (Python)
2023. 1. 12. 20:01
알고리즘/HackerRank
Summary string 관련 함수를 사용해서 푸는 문제였다. 나는 어떤 함수를 사용해야하는지 몰라 for 반복문으로 열심히 풀어보고 있다가 잘 안되서 찾아보니 startswith() 라는 함수가 있었다. startswith() 함수 를 사용해서 문자열이 특정 문자열로 시작하는지 확인할 수 있다. 따라서, 이 함수를 사용해서 문제를 풀 수 있었다. 코드를 보면 string 의 각 문자만큼 반복문을 돌려주었다. for i in range(0, len(string)): 그리고 앞의 문자 하나씩 제외하면서 sub_string 의 문자열을 포함하고 있는지 찾아주었다. if string[i:].startswith(sub_string): cnt = cnt + 1 만약 포함하는 문자열이 있다면 카운트를 증가시켜주었..
HackerRank Python 문제 풀이 참고 사이트
2023. 1. 11. 18:41
알고리즘/HackerRank
HankerRank Python 문제를 풀때 참고할만한 사이트가 있어 가져와봤다. 같은 문제지만 푸는 방법은 여러개라서 사이트에 적혀있는 답이 무조건 맞는 답이라고 생각하지말고 자기만의 방법으로 문제를 풀어보고 안 풀리면 그때 찾아보면 좋을 것 같다. 도움이 될만한 사이트들을 정리해서 모아놔야겠다. HackerRank Python 풀이 사이트!! https://www.artofcse.com/learning/problem/python Python Problem Solution of HackerRank • Art of CSE In this series, I will share the code of HackerRank's Python problems. I will suggest you to not to cop..