전체 글 (178) 썸네일형 리스트형 열쇠 (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 ★ ◎ 다.. 소용돌이 예쁘게 출력하기 (1022번) - 백준 (BOJ) https://www.acmicpc.net/problem/1022 1022번: 소용돌이 예쁘게 출력하기 첫째 줄에 네 정수 r1, c1, r2, c2가 주어진다. www.acmicpc.net 백준 - 소용돌이 예쁘게 출력하기 (1022번) 난이도 : Gold 3 알고리즘&자료구조 : Simulation & Implementation (구현) 시간복잡도 (Time Complexity) : O( (r2-r1+1) * (c2-c1+1) ) ★ 핵심 Idea ★ ◎ 각 정사각형의 왼쪽 아래 꼭지점은, [(2 * 해당 좌표) + 1] ^ 2 가 된다. ex) (3, 3) 좌표 → [(2 * 3) + 1] ^ 2 = 7 ^ 2 = 49 현재 좌표가 어느 정사각형에 속해있는지, 행과 열 값중 더 큰 값을 통해 확인하.. 용이 산다 (3430번) - 백준 (BOJ) https://www.acmicpc.net/problem/3430 3430번: 용이 산다 옛날 아주 먼 옛날, 한 마을에 용이 살고 있었습니다. 그 마을에는 호수가 여러개 있었는데, 그 호수들은 모두 물이 들어 있었습니다. 이 마을에는 가끔 비가 내립니다. 신기하게도 비는 한 호수 www.acmicpc.net 백준 - 용이 산다 (Enter The Dragon) (3430번) 난이도 : Gold 1 알고리즘&자료구조 : 우선순위 큐 (Priority Queue) & 그리디 (Greedy) 시간복잡도 (Time Complexity) : O( nlogn ) ★ 핵심 Idea ★ ◎ 특정 호수 "x"에 시간 "t" 에서 비가 내렸다고 하면, "t" 시점 전의 비가 오지 않은 날에는, "t"에서 내린 비를 먹을.. 이전 1 2 3 4 5 6 ··· 23 다음
