문제 설명 두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요. 제한 사항 arr은 길이 1이상, 15이하인 배열입니다. arr의 원소는 100 이하인 자연수입니다. 솔루션(유클리드 호제법) function gcd(a, b) { if (b === 0) return a; return gcd(b, a%b); } function solution(arr) { r..

초고 일시: 2023년 6월 29일 15:20~17:00 문제: 프로그래머스 기출문제 모음 사용 언어: Python3 결과: 2 정답 / 7 문제 2023 현대모비스 알고리즘 경진대회를 대비하고자, 2023 카카오 채용 코딩테스트 기출 문제를 풀었다. 프로그래머스에 카카오 기출문제가 잘 정리되어 있다. 카카오 코딩테스트는 입력을 변수로 넘겨주기 때문에 입력에 대해서는 신경쓸 필요가 없다. 대신 데이터를 쓰기 쉽게 전처리를 할 필요가 있다. 1. 개인정보 수집 유효기간 def check_day(today, prev, s): today = today.split('.') year1 = int(today[0]) month1 = int(today[1]) day1 = int(today[2]) prev = prev...

문제 백준 2252번: 줄 세우기 알고리즘 분류 위상정렬 나의 풀이 일반적인 정렬로는 풀지 못한다. 위상 정렬이라는 특수한 정렬을 써야한다. 위상정렬의 개념만 이해하면 바로 풀 수 있다. 자신보다 키가 작은 사람이 없는 학생을 큐에 담고, 큐에 대해 BFS를 수행한다. 큐에서 꺼낼 때마다 줄을 세운다. 자신보다 키가 작은 사람이 있는 학생은 그 학생이 줄에 세워지기 전까지는 큐에 들어갈 수 없다. 자신보다 키가 작은 학생이 줄에 세워지면 그 학생에 대한 의존성이 없어진 것이므로, 이제 큐에 들어갈 수 있다. 이러한 과정을 반복하여 학생 간의 키 우선순위만으로 정렬한다. 우선순위 정보가 없는 학생들은 마지막에 체크하여 줄에 세워준다. 처음엔 큐를 그냥 list로 두었는데 시간이 5000ms가 나왔다. 그런..

문제 백준 1655번: 가운데를 말해요 알고리즘 분류 자료구조 우선순위 큐 풀이과정 못 풀어서 솔루션을 봤다. 우선순위큐를 이런 식으로 쓸 수 있다는게 좀 신기했던 솔루션이다. 우선 우선순위큐를 2개 만든다. leftheap과 rightheap. 간단히 말해서, leftheap은 중간값보다 작거나 같은 값을 저장하는 Max Heap이고, rightheap은 중간값보다 큰 값을 저장하는 Min Heap이다. leftheap의 root는 항상 중간값이다. 중간값의 위치는 중간이어야 하므로, leftheap과 rightheap의 길이는 같거나 1이 작다. 로직은 이해해서 직접 구현한 힙으로 로직을 구성했는데, 시간초과가 떴다. 불필요한 연산이 있던건가. 그냥 포기하고 heapq 모듈을 사용했다. 나의 풀이 1..

아래 글은 'Introduction to Algorithms(한빛아카데미)'와 위상 정렬 개념 및 구현를 보고 작성한 것이다. 대표 문제 백준 2252번: 줄 세우기 위상 정렬(Topological Sort) 위상 정렬을 알기 위해서는 먼저 '방향 비순환 그래프(DAG)'에 대해 알고있어야 한다. 방향 비순환 그래프(Directed Acyclic Graph): DAG는 말 그대로, 사이클이 없는 방향 그래프이다. DAG는 보통 이벤트/객체 간의 우선순위를 나타내기 위해 사용된다. DAG인 그래프 G = (V, E)의 위상 정렬은 G가 간선 (u, v)를 가질 때, u가 v보다 순서상으로 먼저 나타나도록 모든 노드를 선형으로 나열하는 것이다. 즉, 우선순위에 따라 배열을 정렬하는 것이다. 따라서 우선순위 ..

아래 글은 'Introduction to Algorithms(한빛아카데미)'와 분할 정복 블로그 를 보고 정리한 것이다. 대표 문제 백준 6549번: 히스토그램에서 가장 큰 직사각형 분할 정복 분할 정복(Divide and Conquer)은 (1) 분할과 (2) 정복, (3) 결합의 세 가지 단계를 거치면서 재귀적으로 문제를 해결한다. 분할: 현재의 문제와 동일하되 입력의 크기가 크기, 또는 문제의 크기를 더 작은 부분 문제로 분할한다. 정복: 부분 문제를 재귀적으로 풀어서 정복한다. 부분 문제의 크기가 충분히 작으면 직접적인 방법으로 푼다. 결합: 부분 문제의 해를 결합해 원래 문제의 해가 되도록 만든다. 부분 문제가 재귀적으로 풀 수 있을 만큼 충분히 클 때, 재귀 대상이라고 한다. 부분 문제가 충분..