본문 바로가기

알고리즘3

프로그래머스 - 당구 연습(js) 어제 프로그래머스에서 자바스크립트로 문제를 풀고 있었는데 푼 사람이 0인, 새로운 문제가 올라왔다. 난이도도 1이길래 빠르게 풀고 넘어가려고 했는데, 은근 생각할 게 있어서 시간이 걸렸다. 그리고 무엇보다 재밌었다. 난이도가 1인 이유는 수학 공식만 알면 쉽게 풀 수 있기 때문이라고 추측한다.. 공식을 모르면 굉장히 어렵고, 나도 오랜만에 구글링으로 수학 공식을 검색해서 풀었다. 문제에 필요한 개념을 알기 위해 문제 내용 중 다음 조건에 주목해야 한다. 단, 머쓱이가 친 공이 벽에 부딪힐 때 진행 방향은 항상 입사각과 반사각이 동일하며, 만약 꼭짓점에 부딪힐 경우 진입 방향의 반대방향으로 공이 진행됩니다. 처음엔 별 거 아닌 조건이라고 생각하고 직각 삼각형의 빗변 구하는 공식으로 풀려고 했으나, 그렇게 .. 2023. 3. 17.
자바스크립트로 알고리즘 풀기 여지껏 자바 언어로 알고리즘 문제를 풀었다. 첫 웹 개발을 자바로 배워서 스프링 개발자를 희망했기에 C++로 풀던 알고리즘을 자바로 변경했었다. 백준 알고리즘 강의를 들었을 때에도 자바로 배워서 다른 언어로 풀 생각을 하지 않았다. 근데 부스트캠프를 수강하고, 노드 개발자가 되겠다고 생각을 굳힌 요즘 문득 이런 생각이 들었다. '노드 개발자로 취업을 하면 실무에서도 자바스크립트나 타입스크립트를 쓸텐데 자바스크립트에 익숙해져야 하지 않을까?' 그래서 지금부터라도 자바스크립트로 문제를 풀려고 한다. 무엇보다 긴 시간동안 자바로만 알고리즘을 풀어서 약간 매너리즘을 느꼈는데 자바스크립트로 풀어보니 신선하야 새로운 매력이 있다. 공교롭게도 지금 읽고 있는 알고리즘 책이 자바로 쓰였지만 알고리즘이라는 것은 언어에 .. 2023. 3. 15.
동적 계획법(Dynamic Programming) 동적 계획법 동적 계획법은 부분 문제로 분해할 수 있는 최적화, 탐색, 계산 문제를 해결하기 위한 일반적인 방법을 말한다. 동적 계획법은 작은 문제 여러 개를 합쳐서 큰 문제를 풀 수 있다. 이 때, 동일한 하위 문제가 반복해서 발생할 수 있다. 따라서 동적 계획법을 효율적으로 작성하려면 반복해서 발생하는 하위 문제의 결괏값을 캐싱해 두어야 한다. 동적 계획법의 기본 개념을 익히기 위해 피보나치 수열이 자주 사용된다. 피보나치 수열 피보나치 수열은 0, 1로 시작하고 그 다음 숫자부터는 이전 두 숫자의 합이다. 따라서 0, 1, 1, 2, 3, 5, 8, ...이 된다. 수학적으로 표현하면 다음과 같다. F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2) 코드로 표현하면 다음과 같다.. 2023. 2. 6.

티스토리툴바