Algorithm

본 글은 건국대학교 알고리즘 동아리 AlKon 스터디 5조에서 진행된 발표 내용입니다. 2517 달리기 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 www.acmicpc.net 시간 제한 입력 범위 1초 N, 기량 3 ≤ N ≤ 500,000 // 1 ≤ 기량 ≤ 1,000,000,000 N: 선수의 수 N개의 줄: 각 선수들의 평소 실력을 앞에서 달리고 있는 선수부터 제시 참가한 선수들의 평소 실력은 모두 다르다. 접근법 세미나에서 들은 내용은 아래와 같다. 기량의 최댓값은 1,000,000,000이므로 이 범위로는 세그먼트 ..

본 글은 건국대학교 알고리즘 동아리 AlKon 스터디 5조에서 진행된 발표 내용입니다. 2458 키 순서 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 시간 제한 입력 범위 1초 N, M, a, b 2 ≤ N ≤ 500 // 0 ≤ M ≤ N(N-1)/2 N: 학생의 수 M: 키를 비교한 회수 a, b: a번 학생이 b번 학생보다 키가 작다. 문제: 자신이 키가 몇 번째인지 알 수 있는 학생이 모두 몇 명인지를 출력하라. 접근법 아직 문제만 보고 알고리즘을 떠올리는 게 쉽지가 않아서 플로이드-워셜을 어떻게 써..

Counting Sort (계수 정렬) 시간 복잡도 Counting Sort 알고리즘은 추가적인 배열을 이용하여, 두 수를 비교하는 과정 없이 정렬하는 알고리즘으로, 시간복잡도는 O(n)이다. 장/단점 일반적으로 빠르다는 정렬 알고리즘의 평균 시간복잡도는 O(nlogn)이다. 이에 비하면 Counting Sort는 굉장히 빠른 시간이지만, 메모리 낭비와 정수로 표현되는 자료에 제한된다는 등의 단점으로, 보통은 O(nlogn)의 정렬 알고리즘을 이용한다. Counting Sort는 정렬할 데이터의 크기가 비교적 작을 때 효율적이다. 알고리즘 1. array를 순회하며, 각 값이 나올 때마다 해당 값을 index로 하는 count 배열의 값을 1 증가시킨다. ex. if arr[3] == 1 -> count..

1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 출력 M개의 줄에 답을 출력한다. 존재하면 1을, 존..

Binary Search (이분 탐색 / 이진 탐색) 정렬된 배열에서 특정 값을 찾는 알고리즘 시간복잡도 O(logN) 알고리즘 이분 탐색은 내가 찾고자 하는 값(key)과 배열의 중간 값을 비교한다. 이 때, key가 더 크다면, 중간 값 이후의 값들만이 탐색 대상이 된다. 반대로, key가 더 작다면, 배열의 중간값 이전의 범위가 다음 탐색의 범위가 되는 것이다. 이렇게 탐색의 범위를 1/2씩 줄여 나간다. (-> 시간복잡도가 logN이 되는 이유) lo 와 hi의 초기 값은 각각 0, arr.size()-1 이다. 중간 인덱스 구하기 mid = (lo + hi) / 2 내가 찾는 값과 중간 값(중간 인덱스에 위치한 값) 비교하기 arr[mid] vs key 비교 결과에 따라 다음 탐색 범위 정하기 ..

2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 접근 방식 접근 1 ≤ N ≤ 30 이므로, 3x1부터 3x30 타일에 대한 경우의 수를 arr 배열에 저장하고, arr[N] 값을 출력한다. 부분 문제를 해결하기 위하여 점화식을 세워보자. 우선, arr[0]=1 이고, 홀수인 i에 대해서는 경우의 수가 모두 0이다. 1. i=2 3x2 타일에 대하여 3가지 경우의 수가 존재한다. 2. i=4 a. 3x4 는 3x2 옆에 3x2 타일을 붙인다고 ..

12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직..

본 글은 건국대학교 알고리즘 동아리 AlKon 스터디 5조에서 진행된 발표 내용입니다. 11060 점프 점프 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 시간 제한 입력 범위 1초 N, A(N개의 수) 1 ≤ N ≤ 1000 // 1 ≤ A ≤ 100 1xN 크기의 배열에서, i 번째 칸에 적힌 수를 Ai 라고 할 때, 해당 칸에서 오른쪽으로 Ai칸 이하만큼 점프할 수 있다. 가장 왼쪽 끝에서 오른쪽 끝으로 갈 때, 점프 횟수의 최솟값을 구하여라. 접근법 점프 횟수의 최솟값을 구해야 하므로, dp..