알고리즘
[BOJ-2579] 계단 오르기 문제와 동적 프로그래밍 (Golang)
들어가며 사실 동적 프로그래밍을 너무 오랫동안 하지 않고, 예전에 했을 때도 그냥 이런게 있구나 정도로만 하고 넘어갔던 것이 문제였는지, 해당 문제는 손도 대지 못했던 문제였다. 이래서 이번에는 동적 프로그래밍을 제대로 공부해보자고 마음먹고, 문제를 풀어보았다. 동적 프로그래밍(Dynamic Programming)? 동적 프로그래밍(Dynamic Programming, DP)은 문제를 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법이다. 이 기법은 주로 최적화 문제에 사용되며, 중복되는 하위 문제를 효율적으로 해결하기 위해 메모이제이션(Memoization) 또는 테이블을 사용하여 이전 계산 결과를 저장하고, 재사용하는 방식으로 동작한다.
2025년 5월 26일
[프로그래머스] 조이스틱 (Golang)
문제 프로그래머스 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다음 알파벳 ▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로) ◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서) ▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서) 예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다. - 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다. - 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다. - 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다. 따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다. 만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요. 해당 문제는 코딩 테스트 연습 파트에서 LEVEL2로 분류되어있는데, 사실 왜 LEVEL2일까 싶을 정도로 생각보다 내겐 어려운 문제였다.
2025년 5월 26일
[프로그래머스] 입국 심사 (Golang)
문제 프로그래머스 문제 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다. 모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다. 입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요. 제한사항 - 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다. - 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다. - 심사관은 1명 이상 100,000명 이하입니다. 접근 일반적으로 이렇게 범위가 넓은 경우 이진 탐색을 통해 문제를 해결할 수 있다.
2025년 5월 23일
[BOJ-3273] 두 수의 합 문제를 두 가지 방식으로 풀어보자 (해시, 투 포인터) With Go
문제 BOJ-3273 바로가기 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오. 위처럼 주어진 배열 중에 합이 지정한 수 x가 되는지를 묻는 문제이다.
2025년 5월 21일
[BOJ-9934] 완전 이진 트리 (Golang)
개요 이직 준비를 하며 트리 알고리즘을 오랜만에 공부하다가 마주치게 되어 포스팅 하게 되었다. 완전 이진 트리 문제는 중위 순회한 순서 배열을 통해 완전 이진트리의 원형을 알아내어 출력하는 문제로 먼저 중위 순회라는 개념을 먼저 알아야 한다. 중위 순회 전위/중위/후위 순회의 기준은 노드의 시점을 보고 판단한다. 노드 -> 왼쪽 서브트리 -> 오른쪽 서브 트리 순서로 하면 노드가 앞에 있으니 전위 순회이며, 왼쪽 서브트리 -> 노드 -> 오른쪽 서브 트리 순서대로 하면 노드가 중간에 있으니 중위 순회이다
2025년 5월 21일