백준
백준 22942번 : 데이터 체커
https://www.acmicpc.net/problem/22942 22942번: 데이터 체커 데이터가 조건에 맞는다면 YES, 조건에 만족하지 않는다면 NO를 출력한다. www.acmicpc.net 스택 자료구조를 활용해서 푸는 문제이다. x좌표상에 N개의 원이 존재하고, 각 원의 중심(x좌표)와 반지름이 주어진다. 이 N개의 원들 중에서 임의의 원 2개를 선택했을때 교점이 존재하는지 판단하는 문제이다. 즉, N개의 원 중 어느 것이라도 다른 원과 교점이 있으면 안된다. 데이터의 개수(N)이 최대 200,000이므로 N개 중에 2개를 선택하는 모든 경우의 수를 구하는 방법은 시간 초과 판정을 받기 때문에 다른 방법으로 문제를 해결해야 한다. A (중심: a, 반지름: r1), B (중심: b, 반지름:..
백준 2473번 : 세 용액
https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 전형적인 투 포인터 알고리즘 문제를 조금 복잡하게 꼬아낸 문제이다. 서로 다른 값을 가진 N개 (3 0: e -= 1 elif v == 0: print(d[i], d[s], d[e]) exit() else: s += 1 print(*r, sep=' ')
백준 20440번 : 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1
https://www.acmicpc.net/problem/20440 20440번: 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1 첫째 줄에 지동이의 방에 출입한 모기의 마릿수 N(1 ≤ N ≤ 1,000,000)가 주어진다. 다음 N개의 줄에 모기의 입장 시각 TE과 퇴장 시각 TX이 주어진다. (0 ≤ TE m: m = cnt tem = i flag = True elif cnt < m and cnt - d[i] == m and flag: txm = i flag = False print(m) print(tem, txm)
백준 1967번 : 트리의 지름
https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 전형적이진 않지만 조금만 생각하면 풀 수 있는 그래프 탐색 문제이다. N개의 노드로 구성된 트리가 주어지고 간선으로 연결된 두 노드의 번호와 간선의 길이(비용)가 주어진다. 간선의 개수는 N-1개로 일정하다. 이 때 이 트리를 이루는 임의의 두 노드 사이의 거리의 최댓값을 구하는 문제다. 각 노드에 대하여 다른 노드로 가는 비용을 모두 더하여 값을 저장하고 그 값들 중에 최댓인..
백준 2800번 : 괄호 제거
https://www.acmicpc.net/problem/2800 2800번: 괄호 제거 첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개 www.acmicpc.net 구현하기도 까다롭고 예외처리도 해줘야해서 개인적으로 어려웠던 문제다. 괄호가 포함된 수식이 입력으로 주어진다. 이 수식에서 괄호를 제거해서 만들 수 있는 모든 서로 다른 수식을 구하려고한다. 단, 괄호는 반드시 한 쌍 이상을 제거해야하며 자신과 맞는 짝이 아닌 괄호끼리는 제거할 수 없다. 문제를 이해하는데는 큰 어려움이 없었고 처음 생각한 해결 아이디어는 이렇다. ..
백준 2812번 : 크게 만들기
https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 아이디어 접근은 쉬우나 구현이 까다로웠던 그리디 문제다. 입력으로 주어지는 N자리 숫자에서 K개 만큼의 수를 제거하여 만들 수 있는 가장 큰 (N-K)자리 수를 구하는 문제다. 처음 생각한 해결 아이디어는 이렇다. N자리 수를 구성하는 숫자들 중 가장 큰 숫자가 만들어야 하는 수의 첫째 자리로 오는 것이 수를 가장 크게 만들 수 있다. 예를들어 주어진 예시 3번에서 10자리 숫자 중 가장 큰 수는 8이지만, 8을 첫째 자리로 만들기 위해선 8 앞의 7개의 숫자를 모두 지워야..
백준 11000번 : 강의실 배정
https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 다른 비슷한 문제와 헷갈려서 조금 해맸던 문제이다. 시작시간과 종료시간이 있는 N개의 강의가 입력으로 주어지고, 강의마다 강의실을 배정하려고 한다. 한 강의가 끝나자마자 다른 강의를 시작할 수 있지만, 강의 시간이 겹친다면 그 강의실은 현재 진행중인 강의가 끝날때까지 사용할 수 없다. 강의실을 최소한으로 사용했을때 강의실 개수를 구하는 문제다. 얼핏봤을때 회의실 배정 문제와 비슷해서 N개의 강의를 종료시간 기준으로 오름차순 정렬하고 풀었더니 오..
백준 2141번 : 우체국
https://www.acmicpc.net/problem/2141 2141번: 우체국 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 0 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 접근하기 굉장히 까다로웠던 문제. 풀이를 보고나서 이해했다. 일직선 상의 1차원 좌표에 N개의 마을이 있고 각 마을의 위치와 주민의 수가 입력으로 주어진다. 여기에 우체국을 세우려고 하는데, 각 마을에 살고있는 주민들이 우체국을 가기위해 이동해야 하는 거리의 총합이 최소인 위치에 세우려고 한다. 이때 우체국의 위치를..
백준 2250번 : 트리의 높이와 너비
https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 구현이 까다로웠던 그래프 탐색 문제이다. 문제를 요약하자면 트리의 노드들을 2차원 좌표공간에 매칭시키는 문제다. 루트 노드부터 시작해서 자식으로 내려갈때(레벨이 증가할 때) 마다 x좌표(행)가 증가하,고 부모의 왼쪽 자식은 부모보다 y좌표(열)가 작으며 오른쪽 자식은 더 크다. 하나의 열에는 오직 한 개의 노드만 들어갈 수 있고 트리의 가장 왼쪽에있는 노드와 가장 오른쪽에있는 노..
백준 1774번 : 우주신과의 교감
https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 처음 풀어본 최소신장트리(MST) 문제이다. 문제를 요약하자면 N개의 점에 대한 2차원 좌표가 주어지고, 두 점을 잇는데 두 점 사이의 거리만큼 비용이 발생할 때 비용을 최소로 하면서 N개의 점을 모두 연결된 상태(특정한 점에서 다른 점까지 도달할 수 있음)로 만드려고 한다. 그런데 이때 처음부터 이미 이어져있는 점이 있을 수도 있다. 이때 필요한 최소 비용을 구하는 문..