https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 난이도 : 골드 1 태그 : 세그먼트 트리, 자료구 설명 세그먼트 트리를 활용한 구간 합 구하기 문제입니다. 세그먼트 트리란, 최상위 노드(루트)에는 모든 값들의 합, 그리고 범위를 이분할하여 해당 범위의 값을 저장하고, 그 자식 노드 역시 범위가 1이 될 때까지 반복적으로 분할합니다. 즉, 미리 구간합을 구해놓고 사용하는 방법으로써, 트..

https://www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net 난이도 : 실버 3 태그 : 자료 구조, 문자열, 정렬, 해시를 사용한 집합과 맵 설명 이 문제 같은 경우, 문자열 별로 카운트를 해야 하므로, 해시맵을 유용하게 쓸 수 있겠습니다. 소스코드 fun main(): Unit = with(System.`in`.bufferedReader()) { val hashMap = HashMap() repeat(readLine().toInt()) { val..

https://www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 난이도 : 골드 3 태그 : 자료구조, 그리디 알고리즘, 우선순위 큐, 정렬 설명 d일 안에 강의를 하러 오면 p만큼의 돈을 받을 수 있습니다. n개의 강의를 갈 수 있을 때, 최대로 벌 수 있는 돈을 구하는 문제입니다. 이 문제를 처음 봤을 때 든 생각은, 아! 일자를 오름차순 정렬하고, 돈을 내림차순 정렬하면 되겠구나! 생각했습니다. 하지만, 머지않아 몇 개..

https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net 난이도 : 실버5 태그 : 자료구조, 해시를 통한 집합과 맵 설명 해시맵을 사용해 풀이할 수 있습니다. 맵이란, (키, 쌍)으로 된 자료구조로써, 파이썬의 경우 딕셔너리가 여기에 해당합니다. {이름 : true/false} 의 쌍을 갖고, 출입기록이 있으면 true, 퇴근기록이 있으면 false. 이후 맵의 키를 모아 내림차순 정렬을 한 후, 값이 true인..

https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 난이도 : 실버 2 태그 : 자료 구조, 우선순위 큐 설명 https://uknowblog.tistory.com/126 [백준 1927번] [Kotlin] 최소 힙 https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 ..

https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 난이도 : 골드 4 태그 : 자료구조, 해시를 통한 집합과 맵, 두 포인터, 이분 탐색 설명 N개의 수 중 어떤 수가 다른 두 수의 합일때, 그 수를 좋다고 합니다. 좋은 수의 개수를 찾는 문제입니다. 이 분제는 두 포인터 혹은 이분 탐색으로 풀 수 있을 것 같은데, 저는 두 포인터를 사용해 풀이하도록 하겠습니다. left, right 두 개의 포인터를 선언하고, left + right의 값이 타 값보다 작으면 left를 +..

https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 난이도 : 실버 3 태그 : 자료구조, 문자열, 해시를 사용한 집합과 맵, 트리를 사용한 집합과 맵 설명 집합을 하나 만들고, 이 안에 집합 S에 있는 문자열들을 있습니다. 이후, 검사해야 할 문자열들이 집합에 포함되어 있는지 하나씩 검사합니다. 소스코드 fun main(): Unit = with(System.`in`.bufferedReader()) { val (n..

https://www.acmicpc.net/problem/1269 1269번: 대칭 차집합 첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어 www.acmicpc.net 난이도 : 실버 4 태그 : 자료구조, 해시를 사용한 집합과 맵, 트리를 사용한 집합과 맵 설명 자바/코틀린의 자료 구조중 하나인 집합(set)을 사용하맨 꽤 쉽게 풀 수 있습니다. 소스코드 fun main():Unit = with(System.`in`.bufferedReader()) { readLine() val a = readLine().split(" ").map { it.toInt() ..

https://www.acmicpc.net/problem/9733 9733번: 꿀벌 각각의 일을 한 횟수와 비율을 공백으로 구분하여 출력한다. 출력은 {Re,Pt,Cc,Ea,Tb,Cm,Ex} 순서대로 하며, 비율은 소수점 둘째 자리까지 출력한다. 주어진 목록에 없는 일은 출력하지 않는다. 입력의 www.acmicpc.net 난이도 : 실버 5 태그 : 구현, 자료 구조, 문자열, 해쉬를 사용한 집합과 맵 설명 해쉬맵을 사용하여 각 일을 몇 번 했는지 카운트하여 풀 수 있습니다. 소스코드 import java.util.* import kotlin.collections.HashMap fun main() = with(System.`in`.bufferedReader()) { val target = arrayOf..

https://www.acmicpc.net/problem/23253 23253번: 자료구조는 정말 최고야 위 그림처럼 책이 쌓여 있으므로, 첫 번째 더미 - 두 번째 더미 - 첫 번째 더미 - 두 번째 더미 순으로 꺼내면 책 번호순으로 나열할 수 있다. www.acmicpc.net 난이도 : 실버 5 태그 : 구현, 애드 혹, 스택, 자료 구조 설명 책 더미의 맨 위에있는 책을 꺼내, 순서대로 나열할 수 있는가에 대한 문제입니다. 책더미의 맨 위에서 꺼내는 것이므로, 책 더미가 애초에 내림차순으로 정렬되어 있지 않으면 책을 순서대로 나열하는 것은 항상 불가능합니다. 즉, 쌓여있는 책의 번호를 입력받고, 이게 내림차순 정렬이 되어있는가만 판단하면 됩니다. 소스코드 import sys # 책의 개수, 책의 ..