정신차려 하프물범 정신차려 하프물범

1. 문제 링크 https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 2. 풀이 1) 문제 풀이 각 50만개씩인 명단 2개 in으로 판별(시간 초과, n^2 = 2500억개) -> 이진탐색(풀림, 시간 복잡도 50만 * logN = 50만 * 11 정도) -> set활용(풀림, 제일 간단, O(len(s) + len(t)) = 2 * 50만) 두 집합의 교집합, 합집합, 차집합은 2 * O(n)이 2000만을 넘지 않는다면 set 쓰자. 2) 풀이..

1. 문제 링크 https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 2. 풀이 1) 풀이 설명 - 빠른 도착지의 짐 부터 싣는데 최적해라는 것 - 도착지를 기준으로 s-r 까지 가장 많이 실을 수 있는 짐의 양을 재는 것이다. 도착지를 기준으로 오름차순으로 정렬한다. 시작부터 도착지 범위에서 min(남은 트럭 용량(capa), 박스 크기(box)) 을 골라서 가장 작은 값을 넣는 것이다. 이때 박스 크기는 달라지지 않지만, 범위..

1. 문제 링크 https://www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 2개 회의실로 3개 회의를 모두 진행할 수 있다. 예를 들어, 첫번째 회의실에서 첫번째 회의를 진행하고 두번째 회의실에서 두번째 회의와 세번째 회의를 진행하면 된다. 1개 회의실로 3개 회의 www.acmicpc.net 2. 풀이 1) 풀이 설명 분류: 그리디, 스위핑 스위핑은 정렬 후 다음 데이터만 생각하기 때문에 그리디랑 같이 엮인다. => 이럴 경우 heapq 사용하기 heapq(room 배열)에 끝나는 시간을 담아서, 다음 시작 시간이 heapq에 담긴 0번째(가장 빨리 끝나는 시간)보다 클 경우, 배열에 끝나는 시간을 추가한다. 그렇지 않으면 빼고 추가 2) 풀이 코드 import..

1. 문제 링크 https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 2. 풀이 코드 출력 형태가 리스트가 아니라 string 형식이어서 뭐가 틀린지 찾느라 열받았던 문제^,,, import sys input = sys.stdin.readline tc = int(input()) result = [] for _ in range(tc): cmds = input().rstrip() length = int(input()) stack = input().rstrip()[1:-1].split(',') flag = Tr..

문제 링크 https://www.acmicpc.net/problem/2469 2469번: 사다리 타기 첫 줄에는 참가한 사람의 수 k가 나온다(3 ≤ k ≤ 26). 그 다음 줄에는 가로 막대가 놓일 전체 가로 줄의 수를 나타내는 n이 나온다(3 ≤ n ≤ 1,000). 그리고 세 번째 줄에는 사다리를 타고 난 후 결정 www.acmicpc.net 풀이 처음 아이디어로는 '?'를 제외한 나머지 사다리를 탄 후 결과 값과 비교하려 했지만 -> '?'의 위치도 중요해서 복잡해짐. [풀이 참고함] 핵심: 가로줄이 있으면 두 알파벳이 교환된다. 첫 줄(초기값) ~ 물음표 줄 전까지 사다리 타기 진행 & 맨 밑(결과)~물음표 다음줄까지 진행 (아래서 위로) 그럼 물음표 줄을 가운데에 두고 before, '???'..

문제 링크https://www.acmicpc.net/problem/3079 3079번: 입국심사첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109)www.acmicpc.net 풀이풀이 설명* 분류: 이진탐색인원수가 10억명, 시간도 10억초 까지의 범위이므로 이진탐색을 떠올린다.대체로 이진 탐색의 기준이 되는 건 구하고 싶은 변수이다. 지금은 시간을 출력하는 것이므로 기준을 시간(초)로 잡는다.  검사대 시간 배열 -> info시간을 기준으로 한다면 start = 가장 짧은 검사대 시간, end = (가장 긴 검사대 시간 * 사람 인원수) 로 하겠다..

문제 링크https://www.acmicpc.net/problem/20444 20444번: 색종이와 가위첫 줄에 정수 n, k가 주어진다. (1 ≤ n ≤ 231-1, 1 ≤ k ≤ 263-1)www.acmicpc.net 풀이풀이 설명* 분류: 이진탐색n번의 가위질을 할때 만들어지는 조각의 경우의 수를 정하는 기준은 가로로 몇번, 세로로 몇번 자르는지에 따라 달라진다. 예를 들어, 3번 자를 경우1) 세로로 3번 자르는 경우 -> 4조각2)세로로 1번 가로로 2번 자르는 경우 -> 6조각이 나온다. 따라서 가로: row, 세로: col(n-row) 로 친다면, total(조각수) = (row + 1)(col + 1) 이므로,row를 기준으로 탐색한다고 하면 mid 값으로 설정할 수 있다.풀이 코드n, k..

문제 링크 https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 풀이 풀이 설명 * 분류: 이분탐색(?) 카테고리는 이분탐색이지만 정렬로도 해결 가능해서 딱히 쓰진 않았다.. 더했을 때, 가장 0에 가까운 조합 2개를 뽑는 것 --, ++, -+ 의 조합일 수 있음 -99 +99 와 같이 합이 0이 되려면 절대값이 같으면 된다. 그러므로 인접한 값을 더한 덧셈배열(diff) 만들어서 절대값을 기준으로 정렬한다. 이때..