알고리즘

백준 2493번 탑 문제 풀이입니다. 2493번: 탑 (acmicpc.net) 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 2009 정올 초등부, 고등부 문제입니다. 직전에 포스팅했던 '옥상 정원 꾸미기'와 유사점이 많은 문제입니다. 문제 요약 및 분석 오른쪽에서 왼쪽으로 레이저를 발사하는데 탑의 기둥부분(벽면)에 맞으면 수신이 되는 방식입니다. 높이가 다른 각 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지가 문제입니다. 이때 N = 5 x 10^5 으로 O(n)이나 O(NlogN) 안에는 들어와야..

백준 6198번 옥상 정원 꾸미기 문제 풀이입니다. 6198번: 옥상 정원 꾸미기 (acmicpc.net) 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net 2006 USACO Silver 문제입니다. 개인적으로 문제 푸는데 이걸 스택으로 푼다는 걸 떠올리는데 오래걸렸던 것 같습니다. 문제 요약 및 분석 왼쪽에서 오른쪽으로 각 빌딩에 대해서 크거나 같지 않은 빌딩의 개수를 구하는 문제가 되겠습니다. 일단 입력을 보았을 때 N = 8 x 10^4 입니다. N^2으로 풀면 시간 초과가 날 것 같고 N이나 N..

백준 1406번 에디터 문제 풀이입니다. 1406번: 에디터 (acmicpc.net) 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 문제요약 키보드로 에디터에 텍스트를 입력하듯 명령을 했을 때 최종 글자를 출력하는 문제입니다. 단, 입력 할 수 있는 경우는 '커서 좌로 1칸이동', '커서 우로 1칸이동', '백스페이스', '알파벳 입력' 4가지 입니다. 문제 접근 아래의 그림까지만 떠올리면 쉽게 풀 수 있습니다. 커서를 움직인다는 접근보다, 커서는 가만히 가운데 있고 좌우로 글자가 스택에 쌓이는 그림을 떠올릴..

백준 10799번 쇠막대기 문제 C++ 풀이입니다. 10799번: 쇠막대기 (acmicpc.net) 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 2015 초, 중등부 정올 지역본선 문제입니다. 문제 요약 레이저로 잘린 쇠막대기의 개수를 구하는 문제인데, 입력값이 괄호로 이뤄져 있습니다. 1. 모든 레이저는 "( )" 로만 표현됩니다. 2. 나머지 괄호는 막대기의 양 끝을 표현하게 됩니다. 이때 문제에 중요한 조건이 있습니다. '쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다' 항상 안쪽에 위치하는 괄호가 더 짧은..

백준 1956번 운동 문제 파이썬 풀이입니다. 1956번: 운동 (acmicpc.net)문제 자체는 짧고 간단합니다. '가중치가 있는 유향그래프에서 가장 작은 사이클을 찾아라' 로 요약할 수 있겠습니다. 처음에 다익스트라 문제로 착각하여 삽질을 좀 했는데, 아래와 같이 코드를 짰을 때 반례가 생겼다. 틀린코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 from collections import deque INF = float('inf') v, e = map(int, input().split()) graph = [[] for _ in range(v+1)] for _ in range(e): a, b, ..

백준 14938번 서강그라운드 문제 파이썬 풀이입니다. 14938번: 서강그라운드 (acmicpc.net) 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 2017 SPC에 출제 되었던 문제입니다. 한 노드에서 각 노드까지의 최단거리를 알아야하기에, 최단 경로 탐색 알고리즘인 다익스트라(Dijkstra) 알고리즘으로 풀 수 있는 문제입니다. 다익스트라 알고리즘은 N*logN 시간복잡도를 가지게 되는데, 총 N개의 노드를 시작점으로 탐색해야기에 N개 * N*logN 의 시간복잡도를 필요로 하고, N은 최대 100이기에..

백준 16202번 MST 게임 문제 파이썬 풀이입니다. https://www.acmicpc.net/problem/16202 16202번: MST 게임 첫 턴에 찾을 수 있는 MST는 총 5개의 간선 {(1, 3), (1, 2), (2, 4), (4, 6), (4, 5)}로 이루어져 있고, 비용은 16이다. 두 번째 턴에는 첫 턴에서 구한 MST에서 간선의 비용이 최소인 (2, 4)를 제거한 후 남아있 www.acmicpc.net 문제 이름에서 대놓고 알고리즘을 알려주고 있기 때문에 MST를 푸는 방법인 Kruskal 알고리즘으로 풀 수 있었습니다. Edge의 최대가 10000개여서 O(ElogE)인 알고리즘으로 K번 돌아도 충분한 문제였습니다. 주요코드 line 10 ~ 22 : 유니온파인드 함수 lin..

백준 14217번 그래프 탐색 1 문제 파이썬 풀이입니다. https://www.acmicpc.net/problem/14217 14217번: 그래프 탐색 남규나라의 왕 zych는 도로 정비 계획을 발표하였다. 두 도시를 잇는 도로들을 새로 만들거나, 안전상의 문제로 도로를 없애기도 할 계획이다. 도로 정비 계획은 두 도시와, 만들건지, 없앨건지에 www.acmicpc.net 비슷한 버전의 '그래프 탐색 2'를 풀었다면 아주쉽게 풀 수 있는 문제였습니다. 도로가 사라졌을 때는 원래 최단 거리였던 길이 없어진 경우도 있기 때문에 매번 distance 배열을 초기화 시켜야 한다는 사실만 주의하면 이전 버전 문제와 거의 유사했습니다. 주요코드 line 18 ~ 33 : 1부터 시작해서 각 node까지 BFS를 ..

백준 14218번 그래프 탐색 2 문제 파이썬 풀이입니다. https://www.acmicpc.net/problem/14218 14218번: 그래프 탐색 2 첫째 줄에는 도시의 개수 n,도로의 개수 m이 주어진다. 다음 m개의 줄에는 두 도시가 주어진다.(2≤n≤1,000,1≤m≤100,000) 다음 줄에는 도로 정비 계획에 들어가 있는 도로의 수 q가 주어지고, 다음 q www.acmicpc.net 실버1 치고는 널널한? 문제였습니다. N이 1000이라 최적화없이 대충짜도 어째저째 돌아가는 문제였습니다. INF로 초기화 시킨 distance 배열을 만들어 두고, 테스트가 들어올 때마다 node 1에서 시작해서 BFS를 돌며 최소거리로 갱신시켜 나가는 방식으로 해결할 수 있었습니다. 주요코드 line 1..

백준 5546번 파스타 문제 파이썬 풀이입니다. https://www.acmicpc.net/problem/5546 5546번: 파스타 상근이는 매일 저녁으로 파스타를 만들어 먹는다. 상근이가 만들 수 있는 파스타는 총 세 종류로 토마토 소스, 크림 소스, 바질 소스이다. 상근이는 앞으로 N일 동안 먹을 파스타를 계획하려고 www.acmicpc.net 너무나도 DP스러운 문제기 때문에 점화식을 찾아서 구현해주면 되는 문제입니다. dp 테이블는 dp[N번째 날짜에][직전에안먹은거,직전에먹은거][파스타종류] 가 되고 fix 배열에 고정된 파스타에 대한 정보를 저장합니다. 주요코드설명 더보기 line 13~20 : 1일차에 먹는 경우를 세팅해줍니다. line 22~38 : 2일차부터 N일차까지 토마토 소스, 크..