정보 기술 놀이터

현실 세계에는 컴퓨터를 활용하더라도 최적의 해를 구하기에 시간이나 메모리 공간이 매우 많이 필요한 문제가 있습니다. 따라서 우리는 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 합니다. 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 향상시킬 수 있는 방법이 있습니다. 그 중 하나가 바로 다이나믹 프로그래밍(Dynamic Programming)입니다. 다이나믹 프로그래밍은 동적 계획법이라고도 불리며, 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 합니다. 다이나믹 프로그래밍의 구현은 일반적으로 탑다운(Top-Down)과 보텀엄(Bottom-Up) 2가지 방식이 있습니다. 다이나믹 프로그래밍은 다음의 조건을 만족하는 문제를 해..

이진 탐색(Binary Search)는 말 그대로 반으로 쪼개면서 탐색하는 방법입니다. 이 때, 이진 탐색 대상(리스트은 반드시 정렬되어 있어야만 사용할 수 있습니다. 이진 탐색은 순차 탐색과 달리 시작점, 끝점, 중간점 변수 3개를 이용합니다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색 과정입니다. 정렬된 데이터에서 이진 탐색 방법으로 숫자 4를 찾는 과정은 다음과 같습니다. 순차 탐색은 처음부터 끝까지 탐색하기 때문에 시간복잡도는 O(N)이지만, 이진 탐색은 단계마다 2로 나누므로 시간복잡도는 O(LogN)입니다. 코딩테스트에서는 보통 탐색 범위가 2,000만을 넘어가면 이진 탐색으로 문제를 접근해야 주어진 시간안에 해결할 수 있습니다. 이..

https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr def search(n, times, mid): cnt = 0 for t in times: cnt += mid // t return True if cnt >= n else False def solution(n, times): start = 0 end = min(times) * n mid = start while mid + 1 != end: mid = (start + end) // 2 if sear..

정렬(Sorting)은 데이터를 어떠한 기준에 따라서 순서대로 나열하는 것입니다. 정렬 알고리즘은 가장 기본이 되는 선택 정렬(Selection Sort), 삽입 정렬(Insertion Sort), 버블 정렬(Bubble Sort)부터 퀵 정렬(Quick Sort), 합병 정렬(Merge Sort), 계수 정렬(Count Sort) 등 매우 다양합니다. 코딩테스트에서는 Python 기본 정렬 라이브러리를 사용하면 충분히 빠른 시간내에(O(NlogN)) 정렬을 수행할 수 있습니다. 따라서, 정렬 라이브러리 사용 예제 몇 가지를 확인해 보겠습니다. def solution(arr): sorted_arr = arr.copy() sorted_arr.sort() # sorted_arr.sort(reverse=Tru..

탐색(Search)은 보통 많은 양의 데이터중에서 원하는 데이터를 찾는 것을 의미합니다. 프로그래밍에서는 그래프, 트리 등의 자료구조(Data structure)를 이용하여 탐색을 구현합니다. 탐색 방법 중 대표적인 것이 바로 깊이 우선 탐색(Depth-First Search, DFS)과 너비 우선 탐색(Breadth-First Search, BFS)입니다. DFS와 BFS를 구현하는 자료구조인 스택(Stack), 큐(Queue), 그래프(Graph)와 재귀 함수(Recursive Function)에 대한 설명은 생략하겠습니다. DFS는 그래프 탐색 과정에서 최대한 깊숙이 들어가서 노드를 방문한 후(리프 노드까지), 다시 돌아가 탐색하는 알고리즘입니다. DFS의 동작 과정은 다음과 같습니다. 1. 탐색 ..

구현(Implementation)은 머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램 코드로 작성하는 것을 말합니다. 어떤 문제를 풀더라도 프로그램 코드 작성은 필수이기 때문에 구현 문제 유형은 모든 범위의 문제 유형을 포함하고 있습니다. 따라서, 대부분 구현 문제에 대한 별도의 유형을 정하기 어렵습니다. 보통 구현 문제는 풀이를 떠올리는 것은 쉽지만 코드로 옮기기 어려운 것들입니다. 결국 구현 문제는 자신의 프로그래밍 피지컬로 승부를 봐야합니다. 구현 문제를 잘 풀어내기 위해서는 자신의 주언어 라이브러리 사용법을 잘 숙지해야 합니다. 예를 들어 리스트에서 순열을 구해야 하는 문제를 만난다면 itertools 라이브러리로 쉽게 구현할 수 있습니다. 하지만 이것을 몰랐다면 많은 시간이 필요할 것입니다. 하..

그리디(Greedy)는 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘으로, 단순하지만 강력한 문제 해결 방법입니다. 즉, 그리디 알고리즘은 매 순간 가장 좋아 보이는 것을 선택하기 때문에 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않습니다. 그리디 알고리즘을 이용한 문제 출제는 폭이 매우 넓기 때문에, 다익스트라(Dijkastra) 알고리즘과 같은 특별한 경우를 제외하고는 단순 암기를 통해 모든 문제를 해결하기는 어렵습니다. 따라서, 그리디 알고리즘이 적용 가능한 문제인지 아닌지 판단하고 실제로 풀어낼 수 있는 능력이 중요합니다. 참고로, 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같이 기준에 따라 선택하는 내용이 나온다면 보통 그리디 알고리즘으로 해결할 수 있습니다. ..

'주식 가격' 정의는 다음과 같다. 문제 설명 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,000 이하인 자연수입니다. prices의 길이는 2 이상 100,000 이하입니다. 입출력 예 prices return [1, 2, 3, 2, 3] [4, 3, 1, 1, 0] 입출력 예 설명 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다. 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다. 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다. 4초 시점의 ₩2은 1초간 가격이 떨어..

'완주하지 못한 선수' 정의는 다음과 같다. 문제 설명 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. 참가자 중에는 동명이인이 있을 수 있습니다. 입출력 예 participant compl..

'올바른 괄호' 정의는 다음과 같다. 문제 설명 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 ()() 또는 (())() 는 올바른 괄호입니다. )()( 또는 (()( 는 올바르지 않은 괄호입니다. '(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요. 제한사항 문자열 s의 길이 : 100,000 이하의 자연수 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다. 입출력 예 s answer ()() true (())() true )()( false (()( false 입출..