Toolofv 님의 블로그

백준 - 2252 줄 세우기첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 횟수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.www.acmicpc.net 문제N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오. 입력첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤..

백준 - 14502 연구소첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.www.acmicpc.net문제인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스..

Given a string s, find the length of the longest substring without repeating characters. 중복 문자가 없는 가장 긴 부분 문자열의 길이를 리턴하라 입출력 예시 Example 1:Input: s = "abcabcbb"Output: 3Explanation: The answer is "abc", with the length of 3.Example 2:Input: s = "bbbbb"Output: 1Explanation: The answer is "b", with the length of 1.Example 3:Input: s = "pwwkew"Output: 3Explanation: The answer is "wke", with the len..

백준 - 1086 박성원첫째 줄에 집합의 수의 개수 N이 주어진다. N은 15보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 집합에 포함된 수가 주어진다. 각 수의 길이는 길어야 50인 자연수이다. 마지막 줄에는 K가 주어진다. K는 100보다 작거나 같은 자연수이다.www.acmicpc.net문제박성원은 이 문제를 풀지 못했다.서로 다른 정수로 이루어진 집합이 있다. 이 집합의 순열을 합치면 큰 정수 하나를 만들 수 있다. 예를 들어, {5221,40,1,58,9}로 5221401589를 만들 수 있다. 합친수가 정수 K로 나누어 떨어지는 순열을 구하는 프로그램을 작성하시오.하지만, 박성원은 이 문제를 풀지 못했다.따라서 박성원은 그냥 랜덤하게 순열 하나를 정답이라고 출력하려고 한다. 이 문제..

백준 - 1311 할 일 정하기 1첫째 줄에 사람과 일의 수 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 D의 내용이 주어진다. 비용은 10,000보다 작거나 같은 자연수이다.www.acmicpc.net문제N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다.사람은 1번부터 N번까지 번호가 매겨져 있으며, 일도 1번부터 N번까지 번호가 매겨져 있다.Dij를 i번 사람이 j번 일을 할 때 필요한 비용이라고 했을 때, 모든 일을 하는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오. 입력첫째 줄에 사람과 일의 수 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 ..

백준 - 7869 두 원첫째 줄에 두 원의 중심과 반지름 x1, y1, r1, x2, y2, r2가 주어진다. 실수는 최대 소수점 둘째자리까지 주어진다.www.acmicpc.net문제 두 원이 주어졌을 때, 교차하는 영역의 넓이를 소수점 셋째자리까지 구하는 프로그램을 작성하시오.입력첫째 줄에 두 원의 중심과 반지름 x1, y1, r1, x2, y2, r2가 주어진다. 실수는 최대 소수점 둘째자리까지 주어진다.출력첫째 줄에 교차하는 영역의 넓이를 반올림해 소수점 셋째자리까지 출력한다.  문제해결방법 - (서치 참조)   1. 겹치는 부분이 없을 때 : 02. 한 원이 다른 원 안에 포함될 때 : 작은 원의 넓이3. 겹치는 부분을 계산해야 할 때 :(큰 원 부채꼴 넓이 - 큰원의 내접한 삼각형 넓이) + (..

백준 - 20149 선분 교차 3첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다.www.acmicpc.net 문제해결방법 -   1. 사선공식(신발끈 공식)을 이용하면 주어진 3점의 좌표 방향에 따라 1, 0, -1을 출력한다는 것을 알 수 있다. 1) (x1, y1) (x2, y2) 직선에서 각 점 (x3, y3) 과 (x4, y4)을 사선공식으로 돌린다. 결과를 곱했을 때  0, -1의 경우만 교점이 있을 가능성이 있다.2) (x3, y3), (x4, y4) 직선에서도 각 점 (x1, y1) 과 (x2, y2)을 사선공식으로 돌린다. 위와 같다. 2. 위 결과가 둘 다 0, -1인 경우만 본다. 예외적으로 기울기가 같을 때,..

백준 - 6549 히스토그램에서 가장 큰 직사각형입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다.www.acmicpc.net문제 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다. 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.입력입력은 테스트 케이스 여..

백준 - 25308 방사형 그래프첫째 줄에 8개의 능력치를 나타내는 정수 $a_1, a_2, \cdots , a_8$가 공백으로 구분되어 주어진다. ( $1 \leq a_i \leq 10^4$)www.acmicpc.net  문제해결방법 - (구글링, 챗GPT 참조) 1. 신발끈 공식이라 일컬어지는 사선공식을 활용한다. 이 사선공식은 좌표로 주어지는 삼각형의 넓이를 구하는 공식인데, 절댓값을 취하기 전, 계산한 결과가 음수냐 양수냐에 따라 p1(x1, y1), p2(x2, y2), p3(x3, y3)의 순서로 선을 긋는다고 할 때 시계방향인지, 반시계방향인지 알 수 있다. (음수면 시계방향, 양수면 반시계방향) 이 문제에서 방향을 체크하는 것으로 연동되어 알 수 있는 것은 삼각형이 p2(x2, y2)에 따..