포시코딩

https://www.acmicpc.net/problem/1374 1374번: 강의실 첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 www.acmicpc.net https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net https://www.acmicpc.net/problem/1092 109..

문제 https://www.acmicpc.net/problem/1233 1233번: 주사위 지민이는 주사위 던지기 게임을 좋아하여 어느 날 옆에 있는 동호를 설득하여 주사위 던지기 게임을 하자고 하였다. 총 3개의 주사위가 있다. 그리고 이 주사위는 각각 S1(2 ≤ S1 ≤ 20), S2(2 ≤ S2 www.acmicpc.net 브론즈 2의 난이도 문제 치고 푸는데 생각도 오래 하고 걸리기도 오래 걸린데다 푸는 방법도 여러 방법으로 나와서 따로 포스팅하게 되었다. 일단 들어가기 앞서 완전 탐색만 알았지 브루트 포스는 처음 들어보는 알고리즘이었는데 알고보니 둘 다 같은 말이었다. brute = 단순히, 짐승이란 뜻 force = 힘 그냥 짐승처럼 힘만 갖고 밀어붙인다는 뜻으로 0000부터 9999까지 가..

문제 https://www.acmicpc.net/problem/10809 10809번: 알파벳 찾기 각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다. 만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출 www.acmicpc.net 시간 제한과 메모리 제한도 넉넉하기 때문에 파이썬에서 문자열을 아스키 코드로 변환하는 함수를 알면 쉽게 풀 수 있는 문제다. 난이도도 solved.ac 기준 브론즈 2로 낮은 편에 속한다. 내 풀이 S = input() for x in range(ord('a'), ord('z')+1): print(S.find(chr(x)), end=' ') 알파벳의 아스키 코드 변환 함수인 or..

https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net https://..

Union-Find 개요 집합에는 두가지 종류의 연산이 필요 membership 연산: 집합에 포함된 값인지 합집합(Union), 교집합(Intersection), 차집합(Difference) 파이썬에서는 Set을 통해 집합을 표현할 수 있다. Dict도 가능하지만 중복 key에 대한 처리를 해줘야 함으로 Set이 더 효과적 집합의 함수 집합에는 다음과 같은 함수들이 필요하다. make-set(x) -> x만으로 구성된 집합을 정의(make) find(x): membership fn -> x가 속한 집합의 대표값 리턴 ex) 두 집합 S, T가 있을 때, find(5)라고 한 경우 T에 5가 포함되어 있다면 T를 대표하는 값을 리턴 union(x, y) -> 두 key 값 x, y를 하나의 집합으로 합침..

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net https://www.a..

문제 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 이코테의 떡볶이 떡 만들기 문제와 동일하다. 구현 이진 탐색에 대해서는 숫자로 이루어진 배열 안에서 특정 숫자가 존재하는지 찾는거에 대해서만 배운 상태였어서 이진 탐색을 활용해 어떻게 푸는지도 감을 잡지 못했는데 파라메트릭 서치 알고리즘으로 풀면 된다는 해설을 보면서 점점 이해가 됐던 것 같다. 파라메트릭 서치로 문제를 바라보면 다음과 같다. 최적화 N..

문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 구현 '공유기 간의 거리'를 줄이면 설치 가능한 '공유기 대수'가 늘어나고 거리를 늘리면 설치 가능한 '공유기 대수'가 줄어든다. 반대로, 설치 가능한 '공유기 대수'가 적다면 거리가 너무 길다는 뜻이니 거리를 줄여 설치 가능 대수를 늘릴 수 있고 설치 가능 대수가 '크거나 같다면' 거리를 늘리면서 (최대거리를 구해야 하니) 최대 거리도 만..

알고리즘에서 logN의 밑은 2이므로 만약 N이 10억이라고 할 때, N = 10억 = 10^9 log2N = log2(10^9)가 된다. 이건 다시 9log2(10)이 되는데 log2(10)은 3.3정도로 생각하면 되므로 9*3.3 = 약 30이라는 결과를 얻을 수 있다. 만약 문제가 MlogN의 시간복잡도를 요구하는데 M이 200,000이었을 경우 MlogN = 20만 * 30 = 6,000,000이 된다. 메모리 사용량은 1000 = 1KB. 1,000,000 = 1MB가 되므로 MlogN의 메모리 사용량은 약 6MB가 된다는 것을 알 수 있다.

https://www.acmicpc.net/problem/2747 2747번: 피보나치 수 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net https://www.acmicpc.net/p..