본문 바로가기

개발자 일기/알고리즘 공부22

[Python]다이나믹 프로그래밍 뜯어보기 최근 알고리즘 공부를 하면서 점화식의 늪에 빠져있다. (정확히는 동적 계획법) 점화식은 다이나믹 프로그래밍(Dynamic Programming, 이하 동적 계획법)에서 사용되는 방식이자 개념 중 하나인데, 보통 알고리즘 문제를 풀 때 그냥 점화식이라는 수학적 개념이 있구나 정도로만 알고 있었다. 막상 실제로 적용해보니 어떤 문제에서 동적 계획법을 적용해서 풀어야 할지 잘 감이 오지 않았다. 문제를 단순히 보면 생각나는 1차원적이면서도 단순무식한 접근법들이 떠오르는데, 이를 적용할 경우 대부분 시간초과가 발생한다. 몇 번의 삽질을 하면서 비로소 점화식에 대한 개념이 잡혔고, 왜 동적 계획법이 필요한지 피부로 체감하게 되었다. 알고리즘에 대한 기본 개념은 있는 개발자이지만, 다이나믹 프로그래밍이 무엇인지 ".. 2025. 3. 16.
[Python]백준#28702-FizzBuzz 백준에서 브론즈 1 등급의 문제 FizzBuzz를 풀어가는 과정에서 좋은 코드를 발견하여 동작 원리와 핵심 코드를 분석해 보았다.내가 직접 작성한 코드는 굉장히 1차원적이라 좀 더 나은 방안들을 고려하다가, 상위 랭킹에 bennyws 님의 코드가 매우 간결하고 효율적이라 생각하여 포스팅을 작성했다.문제FizzBuzz 문제는 i=1,2,⋯$i = 1, 2, \cdots$ 에 대해 다음 규칙에 따라 문자열을 한 줄에 하나씩 출력하는 문제입니다.$i$가 $3$의 배수이면서 $5$의 배수이면 “FizzBuzz”를 출력합니다.$i$가 $3$의 배수이지만 $5$의 배수가 아니면 “Fizz”를 출력합니다.$i$가 $3$의 배수가 아니지만 $5$의 배수이면 “Buzz”를 출력합니다.$i$가 $3$의 배수도 아니고 $5.. 2025. 2. 5.
[프로그래머스 JS] 숫자 짝꿍 📖 문제 설명 두 정수 X, Y의 임의의 자리에서 공통으로 나타나는 정수 k(0 ≤ k ≤ 9)들을 이용하여 만들 수 있는 가장 큰 정수를 두 수의 짝꿍이라 합니다(단, 공통으로 나타나는 정수 중 서로 짝지을 수 있는 숫자만 사용합니다). X, Y의 짝꿍이 존재하지 않으면, 짝꿍은 -1입니다. X, Y의 짝꿍이 0으로만 구성되어 있다면, 짝꿍은 0입니다. 예를 들어, X = 3403이고 Y = 13203이라면, X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 3, 0, 3으로 만들 수 있는 가장 큰 정수인 330입니다. 다른 예시로 X = 5525이고 Y = 1255이면 X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 2, 5, 5로 만들 수 있는 가장 큰 정수인 552입니다(X에는 5가 3개, Y에는 .. 2023. 10. 14.
[프로그래머스 JS] 삼총사 📖 문제 설명 한국중학교에 다니는 학생들은 각자 정수 번호를 갖고 있습니다. 이 학교 학생 3명의 정수 번호를 더했을 때 0이 되면 3명의 학생은 삼총사라고 합니다. 예를 들어, 5명의 학생이 있고, 각각의 정수 번호가 순서대로 -2, 3, 0, 2, -5일 때, 첫 번째, 세 번째, 네 번째 학생의 정수 번호를 더하면 0이므로 세 학생은 삼총사입니다. 또한, 두 번째, 네 번째, 다섯 번째 학생의 정수 번호를 더해도 0이므로 세 학생도 삼총사입니다. 따라서 이 경우 한국중학교에서는 두 가지 방법으로 삼총사를 만들 수 있습니다. 한국중학교 학생들의 번호를 나타내는 정수 배열 number가 매개변수로 주어질 때, 학생들 중 삼총사를 만들 수 있는 방법의 수를 return 하도록 solution 함수를 완성.. 2023. 9. 29.
[프로그래머스 JS] 콜라 문제 📖 문제 설명 오래전 유행했던 콜라 문제가 있습니다. 콜라 문제의 지문은 다음과 같습니다. 정답은 아무에게도 말하지 마세요. 콜라 빈 병 2개를 가져다주면 콜라 1병을 주는 마트가 있다. 빈 병 20개를 가져다주면 몇 병을 받을 수 있는가? 단, 보유 중인 빈 병이 2개 미만이면, 콜라를 받을 수 없다. 문제를 풀던 상빈이는 콜라 문제의 완벽한 해답을 찾았습니다. 상빈이가 푼 방법은 아래 그림과 같습니다. 우선 콜라 빈 병 20병을 가져가서 10병을 받습니다. 받은 10병을 모두 마신 뒤, 가져가서 5병을 받습니다. 5병 중 4병을 모두 마신 뒤 가져가서 2병을 받고, 또 2병을 모두 마신 뒤 가져가서 1병을 받습니다. 받은 1병과 5병을 받았을 때 남은 1병을 모두 마신 뒤 가져가면 1병을 또 받을 수.. 2023. 9. 25.
[프로그래머스 JS] 옹알이 (2) 📖 문제 설명 머쓱이는 태어난 지 11개월 된 조카를 돌보고 있습니다. 조카는 아직 "aya", "ye", "woo", "ma" 네 가지 발음과 네 가지 발음을 조합해서 만들 수 있는 발음밖에 하지 못하고 연속해서 같은 발음을 하는 것을 어려워합니다. 문자열 배열 babbling이 매개변수로 주어질 때, 머쓱이의 조카가 발음할 수 있는 단어의 개수를 return하도록 solution 함수를 완성해주세요. 🚫 제한 사항 1 ≤ babbling의 길이 ≤ 100 1 ≤ babbling[i]의 길이 ≤ 30 문자열은 알파벳 소문자로만 이루어져 있습니다. 💾 입출력 예시 food result ["aya", "yee", "u", "maa"] 1 ["ayaye", "uuu", "yeye", "yemawoo", ".. 2023. 8. 22.