https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 난이도 : 골드 2 태그 : 데이크스트라, 그래프 이론 설명 다익스트라를 응용한 문제입니다. S에서 시작하여, G - H 혹은 H - G 구간을 거쳐, t1, t2, t3, 총 3개의 목적지 후보로 갈 수 있다 가정해보겠습니다. 이 때, 시작점인 S와 목적지인 T1의 최단거리가 S - G - H - T1 혹은 S - H - G - T1 과 같을 때, T1은 가능한 목적지 경로입니다. S - ..
https://www.acmicpc.net/problem/12891 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 난이도 : 실버 2 태그 : 문자열, 슬라이딩 윈도우 설명 슬라이딩 윈도우란 고정 크기의 구간을 이동하며 윈도우 내 데이터를 탐색하는 기법입니다. 투 포인터와 비슷한 원리로 작동합니다. 본 문제에서는 항상 고정된 p 사이즈 만큼의 구간만을 탐색하기 때문에, 첫 0 ~ p구간 까지 각각 A, C, G, T의 개수를 카운팅 한 뒤, 구간을 하나씩 이동하며 A, C, G, T의 ..
https://www.acmicpc.net/problem/26517 26517번: 연속인가? ? 실수 $t$에 대하여, 함수 $f(x)$가 $x=t$에서 정의되어 있고, $\lim_{x \rightarrow t} f(x) = f(t)$인 경우 "$f(x)$는 $x=t$에서 연속이다"라고 한다. 함수 $f(x) = \begin{cases}ax+b & (x \leq k)\\ cx+d & (x > k)\end{cases}$가 주 www.acmicpc.net 난이도 : 실버 5 태그 : 수학, 미적분학 설명 x = t에서, 두 함수가 서로 연속인지 판단하는 문제입니다. f(x) = ax + b, f(x) = cx + d 이므로, 단순히, at + b와 ct + d가 서로 같은 값인지 판단하면 됩니다. 소스코드 ..
https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 난이도 : 실버 5 태그 : 수학, 다이나믹 프로그래밍, 조합론 설명 서쪽과 동쪽의 다리를 서로 잇는 문제입니다. 항상 양쪽 다리 개수가 같거나, 강 동쪽이 다리가 더 많으므로, 단순히 오른쪽 다리 m개 중 왼쪽다리 개수 n만큼을 고르는 조합으로 볼 수 있습니다. 즉, mCn 으로 볼 수 있겠네요. 소스코드 fun main() = with(System.`in`.bufferedReader()) { ..
https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 난이도 : 실버 3 태그 : 그리디 설명 그리디 알고리즘을 통해 풀 수 있는 문제입니다. 현재의 주유소보다 다음 주유소가 더 효율이 좋다면, 무조건 다음 주유소로 이동하는게 효율적입니다. 따라서, 현재 주유소보다 효율이 좋은 주유소를 탐색한 후, 해당 주유소까지 이동할 기름만 충전한 후, 해당 주유소르 이동합니다. 소스코드 import java.util.* fun main() = w..
https://www.acmicpc.net/problem/15921 15921번: 수찬은 마린보이야!! 기댓값 E(X)의 정의는 ‘각 사건이 벌어졌을 때의 이득과 그 사건이 벌어질 확률을 곱한 것을 전체 사건에 대해 합한 값’이다. 다시 말해, 어떤 수 x가 수열에 등장할 확률 P(x) = (x의 등장 횟수) / www.acmicpc.net 난이도 : 브론즈 4 태그 : 수학 설명 연습기록이 주어졌을 때, (연습 기록들의 평균값) / (연습 기록들 중 하나를 균일한 확률로 뽑을 때의 기댓값) 을 구하는 문제입니다. 이게 무슨소리지..? 하면서 두 세번은 읽어봤습니다.연습 기록 중 하나를 균일한 확률로 뽑았을 때의 기댓값..? 이게 평균이랑 뭐가 다르지? 네. 다를 거 없었습니다.평균값 / 평균값은 항상 ..
https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 난이도 : 골드 3 태그 : 수학, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색, 조합론, 백트래킹 설명 DFS를 사용해 풀면 되겠네! 라는 생각이 바로 떠올랐지만, 생각해보니 순수 DFS만으로 풀기에는 조금 무리가 있었습니다. 결국... 이게 뭐지??? 하는 생각에 태그를 펼쳐봤습니다. 그렇습니다. 이 문제는 1. 5 x 5 = 25명의 자리 중 7명을 뽑고(..
fun main() { val line = readLine()!!.split(" ") var a = line[0].toLong() var b = line[1].toLong() var result:Long = if (a < b) (b * (b + 1)) / 2 - (a * (a - 1) / 2) else (a * (a + 1)) / 2 - (b * (b - 1) / 2) print(result) } https://www.acmicpc.net/problem/2355 2355번: 시그마 첫째 줄에 두 정수 A, B가 주어진다. (-2,147,483,648 ≤ A, B ≤ 2,147,483,647) www.acmicpc.net 난이도 : 브론즈 2 태그 : 수학, 사칙연산 설명 두 수 A, B가 주어질 때, 두..
https://www.acmicpc.net/problem/1264 1264번: 모음의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 영어 대소문자, ',', '.', '!', '?', 공백으로 이루어진 문장이 주어진다. 각 줄은 최대 255글자로 이루어져 있다. 입력의 끝에는 한 줄 www.acmicpc.net 난이도 : 브론즈 4 태그 : 구현, 문자열 설명 문자열에서 모음의 개수를 출력하는 문제입니다. 코틀린에서는 파이썬과 같이 in 키워드를 통해, 특정 원소가 배열/리스트 안에 있는지 검사할 수 있습니다. 소스코드 import java.io.BufferedReader import java.io.InputStreamReader fun main() { val vowel = arra..
https://www.acmicpc.net/problem/2477 2477번: 참외밭 첫 번째 줄에 1m2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1 ≤ K ≤ 20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지 www.acmicpc.net 난이도 : 실버 2 태그 : 수학, 구현, 기하학 설명 실제 코딩테스트에 연습삼아 응시해봤다가, 기하학 문제에 큰 쓴맛을 느끼고, 기하학 문제를 공부하기로 마음 먹었습니다. 첫 번째 기하학 문제. 참외밭입니다. 밭은 항상 ㄱ 또는 ㄱ을 회전한 모양을 하고 있고, 이 육각형 임의의 점 중 하나에서 시작하여, 동서남북 방향과 길이가 주어집니다. 아, 큰 사각형에서 작은 사각형 그냥 빼면 되겠다. 를..