Algorithm

투포인터 (Two Pointers) 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘 정렬되어 있는 두 리스트의 합집합으로도 사용되며, 병합정렬의 기초가 되기도 합니다. 투포인터 알고리즘을 활용할수 있는 다음과 같은 문제가 있습니다. 아래의 문제는 두가지 방법으로 풀수 있습니다. Q. 정렬된 리스트 A와 타겟 값 S가 주어졌을 때, 두 수의 합이 S가 되는 순서쌍을 모두 구하여라. > A = [1, 3, 5, 6, 9, 11, 12, 16, 17, 19, 22, 25, 28] > S = 27 1. 이중 반복문을 이용한 풀이 가장 먼저 떠오르는 풀이는 이중 반복문을 이용해 모든 쌍을 탐색하며 조건을 만족하는 경우를 찾는 방법입니다. A = [1, 3, 5, 6, 9, 1..

문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 예제 입력 1 10 4200 1 5 10 50 100 500 1000 5000 10000 50000 예제 출력 1 6 문제 해설 그리디 알고리즘으로 푸는 문제이다. 동전의 개수를 최소로 만들기 위해서는 동전의 액수를 내림차순으로 나눌수 ..

문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거..

문제 페인은 에너지 드링크를 좋아하는 회사원이다. 에너지 드링크는 카페인, 아르기닌, 타우린, 나이아신 등의 성분이 들어있어 피로 회복에 도움을 주는 에너지 보충 음료수이다. 야근을 마치고 한밤중에 퇴근하니 벌써 새벽 1시. 하지만 주말은 아직 멀었고, 다음 날에도 정시에 출근해야 하는 페인은 오늘도 에너지 드링크를 찾는다. 반복되는 야근에 지친 나머지, 평소보다 더 많은 에너지와 피로 회복이 필요했던 페인은 집에 있던 에너지 드링크들을 한 데 합쳐서, 하나의 에너지 드링크로 만들어 한번에 마시려 한다. 페인이 에너지 드링크들을 합치는 과정은 다음과 같다. 임의의 서로 다른 두 에너지 드링크를 고른다. 한쪽 에너지 드링크를 다른 쪽 에너지 드링크에 모두 붓는다. 단, 페인은 야근 후유증으로 인해 손이 떨..

www.youtube.com/watch?v=d8KPN79UAKA&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=10 개발형 코딩 테스트 정해진 목적에 따라서 동작하는 완성된 프로그램을 개발하는 것을 요구하는 코딩 테스트 유형 일부 기업은 해커톤을 통해 채용을 진행한다 해커톤(Hackathon)이란 단기간에 아이디어를 제품화하는 프로젝트 이벤트이다 대개 1~2일 정도 진행되며 다수의 해커톤이 대회 형식을 빌려 해커톤이 끝나면 만든 프로그램을 시연하고 발표한 다음 채점을 진행한다 개발형 코딩 테스트는 분야에 따라 상세 요구사항이 다를 수 있다 예시 1) 모바일 클라이언트 개발: 안드로이드, iOS 앱 개발 예시 2) 웹 서버 개발: 스프링(Spring), 장고(Django..

www.youtube.com/watch?v=cswJ1h-How0&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=9 기타 알고리즘 소수 (Prime Number) 소수란 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수이다 6은 1, 2, 3, 6으로 나누어떨어지므로 소수가 아니다 7은 1과 7을 제외하고는 나누어떨어지지 않으므로 소수이다 코딩 테스트에서는 어떠한 자연수가 소수인지 아닌지 판별해야 하는 문제가 자주 출제된다 소수의 판별: 기본적인 알고리즘 (Python) # 소수 판별 함수(2이상의 자연수에 대하여) def is_prime_number(x): # 2부터 (x - 1)까지의 모든 수를 확인하며 for i in range..

www.youtube.com/watch?v=aOhhNFTIeFI&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=8 기타 그래프 이론 서로소 집합 서로소 집합(Disjoint Sets)란 공통 원소가 없는 두 집합을 의미 서로소 집합 자료구조 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 서로소 집합 자료구조는 두 종류의 연산을 지원한다 합집합(Union): 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 찾기(Find): 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 서로소 집합 자료구조는 합치기 찾기(Union Find) 자료구조라고 불리기도 한다 여러 개 합치기 연산이 주어졌을 때 서로소 집합 자료구조의 동작 과정은 다음..

www.youtube.com/watch?v=acqm9mM1P6o&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=7 다익스트라 최단 경로 알고리즘 최단 경로 문제 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미함 다양한 문제 상황 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현 지점 간 연결된 도로는 그래프에서 간선으로 표현 다익스트라 최단 경로 알고리즘 개요 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다 현실 세계의 도로(간선)은 음의 간선으로..

www.youtube.com/watch?v=5Lu34WIx2Us&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=6 다이나믹 프로그래밍 다이나믹 프로그래밍은 동적 계획법이라고도 부른다 일반적인 프로그래밍 분야에서의 동적(Dynamic)이란 어떤 의미를 가질까? 자료구조에서 동적 할당(Dynamic Allocation)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미한다 반면에 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미 없이 사용된 단어이다 다이나믹 프로그래밍은 다음의 조건을 만족할 때 사용할 수 있다 최적 부분 구조 (Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제로 나눌 수 있으며 작은 문제의..

www.youtube.com/watch?v=94RC-DsGMLo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=5 이진 탐색 알고리즘 순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다 이진 탐색 동작 예시 이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾는 예시를 살펴보자 [Step 1] 시작점: 0, 끝점: 9, 중간점: 4 (소수점 이하 제거) [Step 2] 시작점:0, 끝점: 3, 중간점: 1 (소수점 이하 제거) [Step 3] 시작점: 2, 끝점: ..

문제 스타박스는 손님을 입장시킬 때 독특한 방법으로 입장시킨다. 스타박스에서는 손님을 8시가 될 때 까지, 문앞에 줄 세워 놓는다. 그리고 8시가 되는 순간 손님들은 모두 입구에서 커피를 하나씩 받고, 자리로 간다. 강호는 입구에서 커피를 하나씩 주는 역할을 한다. 손님들은 입구에 들어갈 때, 강호에게 팁을 준다. 손님들은 자기가 커피를 몇 번째 받는지에 따라 팁을 다른 액수로 강호에게 준다. 각 손님은 강호에게 원래 주려고 생각했던 돈 - (받은 등수 - 1) 만큼의 팁을 강호에게 준다. 만약, 위의 식으로 나온 값이 음수라면, 강호는 팁을 받을 수 없다. 예를 들어, 민호는 팁을 3원 주려고 했고, 재필이는 팁을 2원, 주현이가 팁을 1원 주려고 한 경우를 생각해보자. 민호, 재필, 주현이 순서대로 ..

문제 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다. N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로..