Algorithm

수학 공부 시작!

인턴을 하면서 NLP의 원리들을 완전히 이해하기 위해서 수학적 지식이 필요하다고 판단했다. 이전에는 논문을 읽으면서 수식이 아무리 등장해도 수식을 이해하려고 노력을 하다가 포기하고 대략적인 개념만 이해하고 넘어갔다. 근본적인 원리를 알지 못한 채 대략적인 아이디어만 이해하는 것이 나 스스로 한계점을 만들어놓는 것 같다는 생각이 들었다. 앞으로 ML, NLP를 하면서 수많은 수식과 수학적 개념을 만나게 될텐데, 지금이 아니면 수학적 기반을 다져놓을 시간이 없다고 생각했다. 그래서 수학 스터디를 만들어서 미적분학, 수리통계학, 공학 통계를 공부하려고 한다. 개인적으로 ML의 대가라고 생각하는 교수님께서 정말 감사하게도 ML 연구를 하기 위한 수학 커리큘럼을 봐주셔서 이를 바탕으로 빠르게 수학적 기반을 다져보..

[BFS] 1697번 숨바꼭질

1. 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력) 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다. 출력) 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 2. 풀이 사고 과정 1. 방문한 위치를 또 방문하게 될 경..

[Algorithm] 에라토스테네스의 체

1. 에라토스테네스의 체란? 소수를 찾는 알고리즘이다. 알아두면 알고리즘 문제를 풀 때 간간이 쓸모 있게 쓰이므로 숙지하도록 하자!! 2. 알고리즘 설명 1. 소수를 구하고자 하는 구간의 모든 수를 2부터 나열한다. 2. 2는 소수이므로 소수 리스트에 추가한다. 3. 자기 자신을 제외한 2의 배수를 모두 지운다. (빨간색) 4. 남아있는 수 가운데 3은 소수이므로 소수리스트에 추가한다. 5. 자기 자신을 제외한 3의 배수를 모두 지운다. (연두색) 6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. 7. 자기 자신을 제외한 5의 배수를 모두 지운다. (파란색) 8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. 9. 자기 자신을 제외한 7의 배수를 모두 지운다. (노란색) 10. 위..

[완전탐색] 백준 1476번: 날짜 계산

1. 문제 설명 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19) 우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1년이 지날 때마다, 세 수는 모두 1씩 증가한다. 만약, 어떤 수가 범위를 넘어가는 경우에는 1이 된다. 예를 들어, 15년은 15 15 15로 나타낼 수 있다. 하지만, 1년이 지나서 16년이 되면 16 16 16이 아니라 1 16 16..

[선택] 백준 11004번 K번째 수 시간초과 에러

신찬수 교수님의 알고리즘 유투브 영상으로 quick selection 알고리즘과 median of median 알고리즘을 배웠습니다. 배운 내용을 적용하고 싶어서 백준에서 quick selection 알고리즘으로 풀 수 있는 K 번째 수 문제를 도전해보았습니다! 11004번: K번째 수 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 예제 테스트 케이스의 경우에는 정상적으로 출력되고, quick selection 알고리즘을 구현하여 문제를 풀었는데 시간 초과 에러가 발생했어요ㅠㅠ 혼자 끙끙거리다가 구글에 이 문제를 푼 사람들의 코드를 보았는데, 대부분의 사람들이 sort 함수를 사용해서 ..

[분할정복] 백준 11729번 출력초과 에러 해결방법

처음에 코드를 제출했을 때 이렇게 출력 초과 에러가 나와서 당황했습니다... 출력 초과 에러가 뭐지? 하고 검색해보니까, 백준 출력초과 에러는 출력결과가 기존 정답보다 많이 나오게 될 때 나오게되는 에러라고 합니다. 따라서 통과하지 못한 테스트 케이스가 있는 말이겠죠?! 그래서 문제를 다시 읽어보니까, 조건에 원반의 갯수는 1

[분할정복] 백준 11729번 하노이탑 파이썬 풀이

1. 백준 11729번 문제 설명 입력) 첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다. 출력) 첫째 줄에 옮긴 횟수 K를 출력한다. 두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다. 2. 문제 풀이 하노이탑 알고리즘에 대한 설명과 pseudo 코드는 이전 포스팅에 있으니 참고하시길 바랍니다. 이전 포스팅에서 추가된 부분은 출력 결과 첫 번째 줄에 옮긴 횟수 K를 출력해야된다는 점입니다. 하노이탑의 최소 이동 횟수는 고1 때 배운 점화식을 활용해서 구할 수 있습니다. 하지만 점화식을 까먹은 문과생은....(나ㅎㅎ) ..

[분할정복] 하노이탑 알고리즘

1. 들어가며 재귀 알고리즘 중에 유명한 하노이탑 알고리즘을 이해해보겠습니다. 혼자서 오랜 고민 끝에 이해가 잘 되지 않아 유투브 영상과 블로그를 참고하여 이해했습니다! 2. 문제 소개 하노이 탑은 프랑스의 수학자 에두아르 뤼카가 1883년 소개한 유명한 문제로, 아래 그림을 보시면 익숙할 것이라고 생각이 듭니다. 옮기는 과정에서 작은 원반 위에 큰 원반이 놓일 수 없으며, tower 1에 있던 모든 원반이 tower 3으로 이동을 시키는 문제입니다. 3. 아이디어 어떻게 정의해야할지 잘 떠오르지 않아서 실제로 원반을 하나씩 옮겨보았습니다. 문제를 작게 만드어 해결하고 이후에 확대하는 방법이 알고리즘 문제를 푸는데 도움이 될 수 있습니다. 일단 3개의 원반을 A에서 C로 이동을 한다고 가정합니다. 세개을..