728x90 반응형 Python3173 2022.02.19 [백준] (python 파이썬) N번째 큰 수 https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 풀이 이 문제는 heap을 사용해서 해결했다. 문제에서 n*n의 표가 주어진다. 그리고 n번째 큰 수를 출력해야 한다. 모든 수를 heap에 저장 후, n번째 큰 수를 찾으면 메모리 초과가 발생한다. 그래서 첫 줄을 heap에 추가한다. 그러면 heap에 n개의 수가 들어가고 루트노드에는 최소값이 오게 된다. 그래서 다음 줄부터 값을 최소힙과 비교해서 최소힙보다 크면 pop후 큰 값을 push해준다. 모.. 2022. 2. 19. 2022.02.19 [백준] (python 파이썬) 숨바꼭질 4 https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 이 문제는 최단 거리를 찾는 문제이기 때문에 bfs를 사용했다. 또한 최단 거리로 목표지점으로 가기위한 경로를 출력해야 했기 때문에 route배열을 이용해 해당 인덱스로 가기 위한 이전 인덱스를 저장했다. 1에서 출발해서 10까지로 예를 들면 아래와 같다. 1 2 3 4 5 6 7 8 9 10 0 1 2 4 5 위와 같이 배열에 이전의 위치가 저장되어있다. .. 2022. 2. 19. 2022.02.17 [백준] (python 파이썬) 이중 우선순위 큐 https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 풀이 https://neomindstd.github.io/%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/boj7662/ [백준/파이썬] 7662번 이중 우선순위 큐 풀이 파이썬을 이용한 백준 온라인저지 문제풀이 neomindstd.github.io 이 문제는 위의 블로그의 설명을 보며 이해하고 풀었습니다. 이 문제는 최대힙과 최소힙 2개를 사용했다. 단순히 두개만 사용하면 .. 2022. 2. 17. 2022.02.17 [백준] (python 파이썬) 보석 도둑 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 이 문제는 최대 힙과 최소 힙을 모두 사용했다. 우선 보석의 무게와 가격을 무게에 대한 최소힙으로 정렬, 가방이 담을 수 있는 무게는 리스트에 담아 오름차순 정렬해주었다. 그리고 for문으로 가방에 담을 수 있는 무게의 보석을 jewel_2힙에 -가격으로 저장했다. 이유는 최대 힙으로 만들어 넣을 수 있는 보석 중, 가장 비싼 보석.. 2022. 2. 17. 이전 1 ··· 27 28 29 30 31 32 33 ··· 44 다음 728x90 반응형
