programmers.co.kr/learn/courses/30/lessons/12953 코딩테스트 연습 - N개의 최소공배수 두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배 programmers.co.kr 💡 N개의 숫자를 소인수분해한 후 Counter를 이용해 합집합을 구하여 모두 곱했습니다. arr에 주어진 수를 소인수분해하기 위해 factorize와 이에 사용되는 isPrime 함수를 추가로 만들었습니다. isPrime은 숫자를 입력으로 받고 이 숫자가 소수면 True, 아니면 False를 반환하는 함수입니다. factorize ..

programmers.co.kr/learn/courses/30/lessons/12913 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟 programmers.co.kr 💡 Dynamic Programming으로 풀이했습니다. 먼저 주어진 land과 같은 shape의 dp라는 리스트를 생성합니다. 이때 모든 값은 0으로 초기화합니다. dp의 두 번째 줄부터, 각 위치에 도달할 때까지의 최댓값을 dp에 저장합니다. 이때 연속해서 같은 열은 방문할 수 없게 해줍니다. cf. dp의 첫 번째 줄에선 아직까지 더해온 값이 없어 그..

programmers.co.kr/learn/courses/30/lessons/17677 코딩테스트 연습 - [1차] 뉴스 클러스터링 뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브 programmers.co.kr 💡 Counter를 이용해 중복을 고려한 교집합 및 합집합을 구했습니다 프로그래머스에서 라이브러리를 사용할 수 있는지 확인해보니, 파이썬의 표준 라이브러리는 사용할 수 있다고 한다. 이 코드에 사용된 collections과 math 모두 표준 라이브러리라 다행이었지만, 너무 라이브러리에 의존한 풀이였나, 싶기도 하다... 두 글자씩 끊어 바이그램을 만드는..

programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 💡 Dynamic Programming으로 풀이했습니다. 먼저 주어진 triangle과 같은 shape의 dp라는 리스트를 생성합니다. 이때 모든 값은 0으로 초기화합니다. dp의 두 번째 줄부터, 각 위치에 도달할 때까지의 최댓값을 dp에 저장합니다. cf. dp의 첫 번째 줄에선 아직까지 더해온 값이 없어 그대로 0이므로 고려하지 않아도 됩니다. dp의 마지막 줄에 다다를 때까지 이를 반복하고, 마지막 줄에 도달하면 while문을 종료합니다. 여기..

programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 💡 begin에서 target으로 변환될 수 있는지 확인하는 것이 아니라, 거꾸로 target에서 한 알파벳씩 변환하면서 begin으로 변환될 수 있는지 확인합니다. 먼저 words 안에 target이 없다면 절대 begin이 target으로 변환될 수 없으므로 0을 반환하게 합니다. words안에 target이 있다면, answer..

programmers.co.kr/learn/courses/30/lessons/49993 코딩테스트 연습 - 스킬트리 programmers.co.kr 💡 skill에서 순서가 정해진 스킬을 제외한 스킬들은 valid 여부에 영향을 주지 않습니다. 따라서 이러한 스킬들은 지운 상태에서 valid 여부를 확인하고자 합니다. 주어진 skill에서 가능한 순서를 모두 구해 valid에 저장합니다. ex) skill = "CBD"인 경우, valid = ['', 'C', 'CB', 'CBD'] 빈 스트링의 경우 skill에 주어진 스킬 중에선 아무것도 배우지 않는 경우를 의미함 각 skill_tree에 대해 skill에 포함되지 않은 스킬은 모두 지운 상태가 valid에 포함되는지 확인합니다. 포함되면 answer..