Algorithm

[Python] 프로그래머스 Lv2 - 줄 서는 방법

🔗 문제 링크 코딩테스트 연습 - 줄 서는 방법 n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람 programmers.co.kr 📂 분류 구현 수학 💡 풀이 이 문제는 규칙만 찾는다면 쉽게 해결할 수 있는 문제이다. 접근 방식 n!를 구한다. n! / n , k % (n! / n)를 구한다. 여기서 몫이 0이라면 -1 해준다. 2번의 해당하는 요소를 answer에 넣는다. n은 -1 하고, k는 num으로 나눈 나머지를 넣어준다. 1, 2, 3번 과정을 n이 0이 될 때까지 반복한다. 💻 코드 from math import factorial def solut..

[Python] 프로그래머스 Lv2 - 숫자의 표현

🔗 문제링크 코딩테스트 연습 - 숫자의 표현 Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 programmers.co.kr 📂 분류 완전탐색 💡 풀이 n이 10,000이하인 수 이기 때문에 완전탐색으로 풀었다. 반복문으로도 해결할 수 있는 문제이지만, 재귀의 약한 것 같아 재귀함수를 사용해서 풀었다. 💻 코드 def recursion(n, i, num): if n == num: return True if n > num: return False n += i return recursion(n, i + 1, num) def solution(n): answe..

[Python] 프로그래머스 Lv2 - 숫자 블록

🔗 문제 링크 코딩테스트 연습 - 숫자 블록 1 10 [0, 1, 1, 2, 1, 3, 1, 4, 3, 5] programmers.co.kr 📂 분류 구현 수학 💡 풀이 이 문제는 설명을 잘 보고 풀어야 하는 문제이다. 설명을 보면 10,000,000번까지 규칙을 적용했다고 나와있다. 따라서 천만이 넘는 번호라면 1번 블록을 설치해야 한다. 접근 방식 해당 숫자에 가장 큰 약수를 넣어준다. 만약 소수라면 1을 넣어준다. 💻 코드 def solution(begin, end): MAX = 10000001 answer = [] for i in range(begin, end + 1): num = 0 if i == 1 else 1 for j in range(2, int(i ** 0.5) + 1): if i % j..

[Python] 프로그래머스 Lv2 - k진수에서 소수 개수 구하기 (2022 KAKAO BLIND RECRUITMENT)

🔗 문제링크 코딩테스트 연습 - k진수에서 소수 개수 구하기 문제 설명 양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다. 0P0처럼 소수 양쪽에 0이 있는 경우 P0처럼 소 programmers.co.kr 📂 분류 구현 💡 풀이 단순 구현 문제였는데 에라토스테네스의 체를 이용해 소수를 구하려고 했으나 범위를 얼마나 지정해야 줘야 알 수 없기에 단순하게 소수를 구하는 로직을 구현했다. 에라토스테네스의 체를 이용하면 1번과 11번이 런타임 오류가 발생한다. 접근 방식 n을 k진수로 바꿔준다. 문제 설명에 나와있는 조건에 따라 소수는 '0'을 split 한 숫자이다. 💻 코드 def convert(num,..

[Python] 프로그래머스 Lv2 - 멀리 뛰기

🔗 문제링크 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2 programmers.co.kr 📂 분류 DP 💡 풀이 이 문제는 피보나치수열과 유사하다. 따라서 피보나치수열의 문제를 풀듯이 해결하면 된다. 💻 코드 MOD = 1234567 def solution(n): a, b = 0, 1 for _ in range(n): a, b = b, (a + b) % MOD return b

[Python] 프로그래머스 Lv2 - 땅따먹기

🔗 문제링크 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟 programmers.co.kr 📂 분류 DP 💡 풀이 처음에는 단순하게 행의 최댓값과 열이 겹친다면 두 번째로 큰 수를 구하는 방식으로 접근했다. 하지만 이 접근방식은 잘못된 방식이었고 이 문제는 DP로 접근해야 해결할 수 있는 문제였다. 접근방식 현재 값에 같은 열은 밟을 수 없으므로 현재 열을 제외한 이전 행의 최댓값을 더해준다. 💻 코드 def solution(land): for i in range(1, len(land)): for j in range(l..