알고리즘

[백준-4485] 녹색 옷 입은 애가 젤다지? - Python

문제 소개 문제 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주인공, 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다. [0][0]번 칸이기도 하다. 왜 이런 곳에 들어왔냐고 묻는다면 밖에서 사람들이 자꾸 "젤다의 전설에 나오는 녹색 애가 젤다지?"라고 물어봤기 때문이다. 링크가 녹색 옷을 입은 주인공이고 젤다는 그냥 잡혀있는 공주인데, 게임 타이틀에 젤다가 나와있다고 자꾸 사람들이 이렇게 착각하니까 정신병에 걸릴 위기에 놓인 것이다. 하여튼 젤다...아니 링크는 이 동굴의 반대편 출구, 제일 오른쪽 아래 칸인 [N-1][N-1]까..

[백준-1238] 파티 - Python

문제 소개 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다. 이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라. 사용한 알고리즘 더보기 다익스트라 알고리즘 적용 크게 다른건 없고 Graph가 단방향이라는것이 유의 해야하고..

[백준-2668] 숫자고르기 - Python

문제 소개 문제 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오. 예를 들어, N=7인 경우 아래와 같이 표가 주어졌다고 하자. 사용한 알고리즘 더보기 DFS (루트 저장) DFS 중에서 진행된 루트를 저장하는 DFS를 하면된다. 비슷한 문제로는 https://dizzy-theme.tistory.com/53가 있다. 구상 첫번째줄에서..

[백준-2573] 빙산 - Python

문제 소개 https://www.acmicpc.net/problem/2573 사용한 알고리즘 더보기 BFS 알고리즘 & 부분 업데이트 이번 문제는 시간초과와 메모리초과를 해결하는 부분이 어려웠음 일단은 풀어서 해결을 했지만 풀고나니 별개로 조금더 최적화 할 수 있는 여지가 있는것 같다 (어떤 부분일까?) 구상 물과 얼음의 위치를 저장해놓은 Arr를 업데이트 할때 원본 Arr를 복사하지 않고 빙산을 업데이트 하면 안된다. 만약에 동시에 진행이 된다면 근접해 있는 빙산에 대해서 내년에 빙산에서 물이되는 위치가 바로 물로 판정이 되고 근접해 있는 옆빙산에 영향을 주기 때문이다. 이부분을 알았다면 빙산과 물의 위치를 저장해놓은 Map을 복사해서 2개를 만들어야 한다고 생각 할 수 있다. 왜냐하면 복사본을 만들지..

비교기반 정렬의 시간복잡도 하한은 nlog(n) 이다

비교기반 정렬 비교기반 정렬이 무엇인가에 대한 설명은 --에 있다 비교기반 정렬의 시간 복잡도의 하한은 \(n log(n)\) 이라고 알려져 있다. 조금 더 정확하게 표현은 다음과 같은 구절을 보면 된다. Can we say that it is impossible to sort faster than Ω(n lg n) in the worst case? If we could, then this would be what it’s called a lower bound. 비교기반 정렬은 가장 Worst Case에 대해서도(그러니까 모든 Case의 정렬 형태에 대해) 필요한 시간 복잡도가 \(nlog(n)\) 정도라는 것으로 이보다 더 적은 방법이 없다는 것이다. 여담으로 시간 복잡도의 상한은 \(n^2\) 이다 ..

[백준-5014] 스타트링크 - Python

문제 소개 강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다. 스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다. 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다. 보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄 엘리베이터는 버튼이 2개밖에 없다. U버튼은 위로 U층을 가는 버튼, D버튼은 아래로 D층을 가는 버튼이다. (만약, U층 위, 또는 D층 아래에 해당하는 층이 없을 때는, 엘리베이터는 움직이지 않는다) 강호가 G층에 도착하려면, 버튼을 적어도 몇 번 눌러야 하는지 구하는 프로그..

다익스트라 알고리즘

먼저 봐야 할 것 Graph 탐색 알고리즘 요약 그래프 탐색중에서 최단거리 탐색에 사용되는 알고리즘이며 1. 거리(시간,비용)이 양수로 주어지고 2. 알고리즘을 수행하면 어떤 1개의 node에서 갈 수 있는 모든 node에 대해 최단거리를 구할수있다. 3. Heap의 자료구조를 사용하여 구현한다. 문제 소개 Graph 탐색 사용한 알고리즘 더보기 다익스트라 알고리즘 구상 Code 소개 # Python code import heapq import collections graph = collections.defaultdict(dict) # graph 입력받기 위해 ##################################### # graph = { # 'A': {'B': 8, 'C': 1, 'D': 2}..

두 수의 합

먼저 봐야 할 것 투포인터 알고리즘 요약 문제 소개 두 수의합이 특정 타겟이 되는 인덱스를 반환하라 예를들어 [ 2 , 7 , 11 , 15 ] 인 리스트가 있다고 할 때 타겟값이 9라고 한다면 결과로 2와 7의 위치인 0과 1을 반환하면 되는 것이다 사용한 알고리즘 더보기 투포인터 구상 리스트를 정렬한뒤 투포인터 , 오른쪽과 왼쪽을 가르치는 포인터를 양쪽 맨끝으로 지정한뒤 특정 타겟 값보다 크면 제일 큰 값을 가르키는 오른쪽 포인터를 왼쪽으로 이동 특정 타겟 값보다 작으면 제일 작은 값을 가르키는 왼쪽 포인터를 오른쪽으로 이동 그런데 어떻게 이러한 탐색 방법이 항상 working하는것인가 살펴보자 정렬된 리스트 \( a_1 , a_2 , a_3 , ... , a_L \) 배열중에 정답 $S$을 가르치는..

[백준-1655] 가운데를 말해요 - Python

문제 : [백준-1655] 가운데를 말해요 (Python) 출처 : 백준 사용한 알고리즘 더보기 자료 구조 : heapq 를 이용한 탐색 Python Code import sys import heapq sys.stdin = open("input.txt", "r") N = int(input()) right_heap=[] # 최소 힙 left_heap=[] # 최대 힙 for _ in range(N): temp_input = int(input()) if len(left_heap)==len(right_heap): heapq.heappush(left_heap,(-temp_input,temp_input)) else : heapq.heappush(right_heap, (temp_input, temp_input)) ..

[백준 - 12865] 평범한 배낭 - Python

먼저 봐야 할 것 요약 문제 소개 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자. 사용한 알고리즘 더보기 Dynamic programming 구상 이문제는 대표적인 DP ..