개발로그

문제 숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를 뽑아야 한다. 1. 숫자가 쓰인 카드들은 N X M 형태로 놓여있다. 2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다. 3. 그 다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다. 4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려해 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다. 입력 조건 첫 행에는 행의 개수 N과 열의 개수 M이 자연수로 주어진다. 두번째 행부터 N개 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 출력 조건 게임의 룰에 맞게 선택한..

#그리디 #알고리즘 #코딩테스트 #자바 #이것이_코딩테스트다 문제 다양한 수로 이루어진 배열이 있을 때, 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번 초과하여 더해질 수 없는 것이 이 법칙의 특징이다. 입력조건 첫째 줄에 N, M, K의 자연수가 주어지며, 공백으로 구분한다. 둘째 줄에 N개의 자연수가 주어진다. 풀이 먼저, 가장 큰 수가 K번 초과할 수 없을 때, 그 다음 큰 수를 활용해야하기 때문에, N개의 자연수를 정렬했다. 정렬하고 나서 가장 큰 수와 그 다음 큰 수를 활용했다. 가장 큰 수가 K번, 그 다음 큰 수가 1번이 하나의 싸이클로 생각했다. M에서 K+1의 크기를 가진 싸이클이 몇 번 나오는지 M / (K+1)로 계..

가중치를 가진 유향 그래프에서 목적지에 이르는 모든 가능한 경로 중 최단 경로를 찾는 알고리즘이다. 다익스트라, 벨만-포드, 모든쌍 최단경로, 싸이클이 없는 그래프의 최단 경로가 있다. 최단경로 문제에서 입력 그래프는 크게 두가지 유형을 갖는다. 1) 모든 간선 가중치가 음이 아닌 일반적인 경우 -> 다익스트라 알고리즘 2) 음의 가중치가 존재하는 경우 -> 벨만-포드 알고리즘 주의할 것은 음의 가중치는 허용하나 가중치의 합이 음인 싸이클은 절대 허용하지 않는다. 다익스트라 알고리즘 최소신장트리를 위한 프림 알고리즘과 원리가 거의 같다. 프림 알고리즘에서는 간선을 연결하는데 필요한 최소 비용을 저장하지만, 다익스트라에서는 시작 노드에서의 최소비용이 저장된다. 먼저, 시작노드의 값을 0으로 초기화하고 나머..

무향 그래프에서 신장트리는 노드를 그대로 두고, 간선을 (노드의 개수 - 1)개만 남겨 트리가 되도록 만드는 것이다. 간선들이 가중치를 갖는 그래프에서 간선 가중치의 합이 가장 작은 트리를 최소신장트리라고 한다. 프림 알고리즘 프림 알고리즘은 집합 S를 공집합에서 시작해 모든 노드가 포함될 때까지 키워나간다. 노드가 하나 포함될 때마다 간선이 하나씩 확정된다. 확정 노드를 저장할 S와 시작 노드부터 각 노드에 도착할 때 필요한 가중치를 저장한 d를 준비한다. d는 아주 큰 수로 초기화한다. 그리고 시작 노드는 0으로 초기화한다. 그리고 집합 S에 모든 노드가 포함되기까지 노드를 추가한다. 추가할 때, 먼저 현재 노드 위치에 연결된 노드에 가중치를 계산한다. 그에 대한 최소를 찾아 S에 포함시키고, S에 ..

그래프에서 모든 정점을 방문해야 할 때가 자주 있다. 모든 정점을 방문하는 방법은 다양하지만 대표적으로 너비우선탐색(BFS)와 깊이우선탐색(DFS)이 있다. BFS와 DFS 모두 일반적인 그래프를 대상으로하는 탐색이지만, 직관적인 이해를 위해 트리구조를 대상으로 루트부터 탐색하는 것으로 진행하겠음. 너비우선탐색 (BFS, Breadth-First Search) 루트를 시작으로, 루트의 자식을 차례로 방문한다. 다음으로 루트 자식의 자식, 2개의 간선을 거쳐서 도달할 수 있는 정점을 방문한다. 이처럼 루트에서 거리 순으로 차례로 방문하게 된다. BFS를 코드로 구현할 때, 자료구조 큐를 사용한다. 먼저 큐에 루트 노드를 삽입하고, 큐가 비어있을 때까지 큐에서 하나를 꺼내 그 노드에 대한 자식 노드를 큐에 ..

그래프 그래프는 현상이나 사물을 정점과 간선으로 표현한 것으로, 정점은 대상이나 개체를 나타내고 간선은 이들간의 관계를 나타낸다. 그래프는 크게 4가지 그래프로 나눌 수 있다. 1) 간선으로 이어진 그래프 2) 간선에 가중치를 더한 그래프 3) 간선에 방향을 가진 그래프(유향 그래프) 4) 간선에 가중치를 더하고 방향을 가진 그래프 그래프의 표현 그래프를 컴퓨터에서 표현할 때는 크게 행렬을 이용하는 방법과 리스트를 이용하는 방법이 있다. 인접형렬을 이용한 방법 그래프 G에서 정점의 총 개수가 n이라고 하면, n X n 행렬을 준비한다. 정점 i와 정점 j 사이에 간선이 있으면 행렬의 (i, j)원소와 (j, i) 원소의 값을 1로 할당하고 나머지는 0으로 할당한다. 가중치가 있는 그래프를 표현할 경우 각..

동적 프로그래밍 큰 문제의 해답에 작은 문제의 해답이 포함되어 있는데, 이를 재귀 호출 알고리즘으로 구현하면 지나친 중복이 발생하는 경우에 이 재귀적 중복을 해결하는 방법 2가지 성질 1. 최적 부분구조 큰 문제의 해답에 그보다 작은 문제의 해답이 포함된다. 2. 중복 호출로 인한 심각한 비효율의 발생 한 번만 구해서 저장해 놓았다가 사용해도 되는 값들을 계산할 때마다 호출하는 비효율 거의 모든 재귀적 알고리즘은 최적 부분구조를 구현한다. 병합정렬, 퀵정렬 등도 최적 부분구조를 갖는다. 하지만, 이들은 재귀적 구현에서 중복이 발생하지 않는다. 이 점에서 동적 프로그래밍의 대상이 되는 문제와 다르다. 동적 프로그래밍을 구현할 때, 중복적으로 호출되는 값을 따로 저장해두고 그 값을 호출한다.

해시 테이블 원소가 저장될 자리가 원소 값에 의해 결정되는 자료구조. 검색 효율의 극단. 저장된 자료와의 비교를 통해 자리를 찾지 않고 단 한 번의 계산(해시함수)으로 자신의 자리를 찾는다. 하지만, 중요한 장애물이 있다. 계산을 통해 얻은 주소에 다른 값이 저장되어 있는 경우(충돌) 해시함수 키 값을 입력으로 받아 해시 테이블 상의 주소를 리턴한다. 두 가지 성질을 만족한다. 1) 입력 원소가 해시 테이블 전체에 고루 저장되어야 한다. 2) 계산이 간단해야 한다. 대표적인 방법으로 나누기 방법, 곱하기 방법이 존재한다. 나누기방법 : 테이블 크기(m)로 나누어 나머지를 주소 값으로 리턴한다. 곱하기방법 : A (0 < A < 1) 를 곱하고, 소수부에 테이블 크기(m)을 곱해 정수부를 주소 값으로 리턴..

검색트리 개체의 레코드를 저장하고 검색하기 위한 트리 형태의 자료구조 *레코드 : 개체에 대한 모든 정보를 포함한다. 어떤 사람이 레코드라면, 직장, 주민번호, 이름, 집 주소 등이 포함될 수 있다. 이들 각각의 정보를 나타내는 부분을 필드라고 한다. 검색트리는 최대 몇 개의 자식노드로 분기할 수 있느냐에 따라 이진검색트리와 다진검색트리로 나눈다. 이진 검색트리는 최대 2개의 자식 노드를 가질 수 있다. 이진검색트리 이진검색트리는 3가지 특성을 갖는다. 1) 이진검색트리의 각 노드는 키 값을 하나씩 갖는다. 키 값은 고유값이어야 한다. 2) 최상위에 루트 노드가 있고, 각 노드는 최대 2개의 자식 노드를 갖는다. 3) 임의의 노드 키 값은 왼쪽 자식노드보다 크고, 오른쪽 자식노드보다 작다. (left <..

기초적인 정렬 알고리즘 선택정렬 가장 큰 원소를 찾아 배열의 마지막 인덱스의 원소와 자리를 바꾼다. 이후 마지막 인덱스 원소를 제외한 나머지로 반복한다. def selectionSort(lst): size = len(lst) for i in range(size): maxIdx = lst.index(max(lst[:size-i])) lst[maxIdx], lst[(size-i)-1] = lst[(size-i)-1], lst[maxIdx] return lst 버블정렬 제일 큰 원소를 끝자리로 옮기는 작업을 반복한다. (비교를 통해 큰 원소를 뒤로 보냄) def bubbleSort(lst): size = len(lst) for i in range(size): for j in range((size-1)-i): ..