백트래킹(Backtracking) 이란 백트래킹 이란 모든 경우의 수를 전부 고려하는 알고리즘 이다. 조금 더 자세하게 말하자면 현재 상태에서 가능한 모든 후보군을 따라가며 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되면 즉시 후보를 포기하면서 정답을 찾아가는 범용적 알고리즘이라고 한다. 상태 공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다. 백트래킹을 사용해 해결할 수 있는 문제는 주로 검색, 의사 결정, 최적화, 열거하기 등의 문제가 있다. 사실 백트래킹은 사용 가능한 경우가 많지만 시간복잡도가 보통 $2^n$ 이기 때문에 대부분의 문제는 동적 프로그래밍 또는 그리디 알고리즘 등으로 더 빠르게 해결할 수 있다. 그렇다고해서 백트래킹을 사용하..

피보나치 수 (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 피보나치 수 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 피보..

4주차 심화 과정에 대해서 내가 작성한 코드를 정리해보았다. 📌 문제 1 우선 문제를 풀기 위해서 애너그램 대해서 이해해야 했다. 애너그램이란 문자를 재배열하여 다른 뜻을 가진 단어로 바꾸는 것을 말하는데 예를 정말 잘 들어주셔서 쉽게 이해할 수 있었다. 예를 들어, 영어의 'tea'와 'eat'와 같이 각 단어를 구성하는 알파벳은 같은데 뜻이 다른 두 단어 그리고 우리말에서 '문전박대' 와 '대박전문' 과 같이 같은 네 글자를 사용하지만 순서를 바꾸어 다른 뜻으로 사용할 수 있는 것을 애너그램이라고 한다. 문제를 풀기 위해서 강의를 통해 배운 알고리즘을 사용해야 했고 함수를 효율적으로 사용하고 싶어 함수를 사용하는 부분에 더 많은 고민을 했던 것 같다. 그리고 코딩 컨벤션을 통해 코드 스타일을 적용해 ..

CS50 1주차 컴퓨팅 사고 - 알고리즘에 대한 강의를 듣고 정리하고 또 추가적으로 공부한 내용을 정리하려고 한다. 컴퓨터에 정보를 입력하고 어떻게 정보를 표현하는지 배웠다. 그러면 컴퓨터는 어떻게 입력한 정보를 처리해서 출력을 하는 것인지 궁금해진다. 컴퓨터가 처리하는 과정은 우리가 일상 생활에서 다양한 문제를 처리하는 방식과 비슷하다고 한다. 컴퓨터는 순서대로 필요한 동작을 하며 문제를 처리하는 데, 이를 알고리즘이라고 한다. 알고리즘 | Algorithm 그럼 알고리즘에 대해서 알아보자. 컴퓨팅은 입력을 받아 그 입력을 처리한 후 출력하는 과정이다. 알고리즘은 입력에서 받은 자료를 출력 형태로 만드는 처리 과정을 뜻한다. 입력(Input) → 알고리즘(Algorithms) → 출력(Output) 따..

알고리즘 공부를 하다가 시간복잡도에 대해서 잘 몰랐었는데 이 유튜뷰 영상을 통해 더 확실하게 알게 되었던 것 같다. 나중에 따로 정리해봐야 겠다. 너무 설명을 잘해주셔서 아래에 영상을 가져와봤다. 빅오 표기법을 모르는 사람이 있다면 이 영상을 보고 한번에 이해할 것 같다. 좋은 강의 너무 감사합니다!