본문 바로가기

Algorithm

 (129)
선분 교차 1 (17386번) - 백준 (BOJ) https://www.acmicpc.net/problem/17386 17386번: 선분 교차 1 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 세 점이 일직선 위에 있는 경우는 없다. www.acmicpc.net 백준 - 선분 교차 1 (17386번) 난이도 : Gold 3 알고리즘&자료구조 : Geometry (기하학) ★ 핵심 Idea ★ ◎ 선분 1을 포함하는 직선의 방정식을 A, 선분 2를 포함하는 직선의 방정식을 B라고 설정한다. 두 선분 1, 2가 교차하려면, 아래의 두 가지 경우를 동시에 만족해야 한다. ① 직선 B로 인해 나눠지는 평면 B1과 B2가 있다고 하면, 선분 1의 양 끝 점이 서로 다른 평면에 위치해..
센서 (2212번) - 백준 (BOJ) https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 백준 - 센서 (2212번) 난이도 : Gold 5 알고리즘&자료구조 : Sorting (정렬) & Greedy (그리디) ★ 핵심 Idea ★ ◎ 주어진 센서들을 좌표 순서대로 정렬하고, 인접 좌표 간 거리를 구해서 리스트로 만든다. 위의 거리 리스트를 다시 정렬하고, 가장 값이 큰 K-1개를 제외한 나머지 값들의 합이 수신 가능 영역 길이 합의 최솟값이 된다. < 전체..
열쇠 (9328번) - 백준 (BOJ) https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 백준 - 열쇠 (Keys) (9328번) 난이도 : Gold 1 알고리즘&자료구조 : BFS (너비우선탐색) & DFS (깊이우선탐색) & Simulation (구현) ★ 핵심 Idea ★ ◎ 아직 열지 못한 문들을 기준으로 BFS를 구현한다. 먼저 초기 탐색을 진행해서, 열지 못하는 문들을 찾는다. 예를 들어, 현재 [A, B, H, X]의 문을 아직 열지 못했고, 현재 갖고있는 열쇠가 [b, h]라면, B..
마라톤 2 (10653번) - 백준 (BOJ) https://www.acmicpc.net/problem/10653 10653번: 마라톤 2 젖소 박승원이 2번째 와 4번째 체크포인트를 건너뛸경우 경로는 (0,0) -> (1,1) -> (2,2) 로 4가 된다. 이보다 더 짧게 달릴수는 없다. www.acmicpc.net 백준 - 마라톤 2 (Marathon) (10653번) 난이도 : Gold 3 알고리즘&자료구조 : Dynamic Programming (동적계획법) ★ 핵심 Idea ★ ◎ 젖소가 X번 체크포인트까지 이동했을 때, 0 ~ K 번 건너뛴 경우 각각에 대해서 최솟값을 기록한다. 위 작업을 1번부터 N번 체크포인트까지 순차적으로 진행하면, 마지막 N번 체크포인트에서의 최솟값이, 문제에서 요구하는 최소거리가 된다. imp..
주식 (12014번) - 백준 (BOJ) https://www.acmicpc.net/problem/12014 12014번: 주식 입력 파일에는 여러 테스트 케이스가 포함될 수 있다. 파일의 첫째 줄에 케이스의 개수 T(2 ≤ T ≤ 100)가 주어지고, 이후 차례로 T 개 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에 두 www.acmicpc.net 백준 - 주식 (12014번) 난이도 : Gold 2 알고리즘&자료구조 : Binary Search (이진 탐색) & LIS ★ 핵심 Idea ★ ◎ 주식의 탈을 쓴, 전형적인 LIS 문제이다. 백준의 가장 긴 증가하는 부분 수열 2 문제를 먼저 풀어보면 좋다. import sys input = sys.stdin.readline from bisect import bisec..
새로운 게임 (17780번) - 백준 (BOJ) https://www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 백준 - 새로운 게임 (17780번) 난이도 : Gold 2 알고리즘&자료구조 : Simulation (구현) ★ 핵심 Idea ★ ◎ 전형적인 구현 문제로, 문제에서 하라는 대로 구현하면 된다. import sys input = sys.stdin.readline class Chess(): def __init__(self, N, K): board = [list(map(int, i..
폭탄 던지는 태영이 (20543번) - 백준 (BOJ) https://www.acmicpc.net/problem/20543 20543번: 폭탄 던지는 태영이 시험을 망친 태영이가 인하대학교에 폭탄을 던진다! 인하대학교는 N×N 크기의 정사각형 모양의 땅이다. 인하대학교의 모든 땅은 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c) www.acmicpc.net 백준 - 폭탄 던지는 태영이 (20543번) 난이도 : Gold 1 알고리즘&자료구조 : Prefix Sum (누적 합) 시간복잡도 (Time Complexity) : O( N^2 ) ★ 핵심 Idea ★ ◎ 누적합으로 생각보다 간단하게 구현할 수 있는 문제이다. N = 5, M = 3일 때, (0, 0) 좌표에 영향을 미칠 수 있는 폭탄의 위치는 (1, 1) 뿐이다. 따라서 (0, ..
인터넷 설치 (1800번) - 백준 (BOJ) https://www.acmicpc.net/problem/1800 1800번: 인터넷 설치 첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차 www.acmicpc.net 백준 - 인터넷 설치 (1800번) 난이도 : Gold 1 알고리즘&자료구조 : Priority Queue (우선순위 큐) / Dijkstra (다익스트라) / 정렬 (Sorting) 시간복잡도 (Time Complexity) : O( (N)log(P) * log(max(L)) ) ▷ 아이디어 떠올리기가 상당히 어려운 문제였다. ★ 핵심 Idea ★ ◎ 다..

티스토리툴바