본문 바로가기
728x90

자료구조6

[백준] 2920번: 음계 - python https://www.acmicpc.net/problem/2920 2920번: 음계 다장조는 c d e f g a b C, 총 8개 음으로 이루어져있다. 이 문제에서 8개 음은 다음과 같이 숫자로 바꾸어 표현한다. c는 1로, d는 2로, ..., C를 8로 바꾼다. 1부터 8까지 차례대로 연주한다면 ascending, 8 www.acmicpc.net 금공강의 힐링을 즐기며 누워서 브론즈 문제 한 문제로 일상 시작. 쉬운 문제지만 O(n)로 짤려고 생각했다. arr1 = [1,2,3,4,5,6,7,8] arr2 = [8,7,6,5,4,3,2,1] arr = list(map(int, input().split())) cnt1 = 0 cnt2 = 0 for i in range(8): if arr[i] == a.. 2024. 4. 5.
[백준] 11279번: 최대 힙 - python https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 최소 힙 풀었더니 옆에 연관문제라고 떠서 봤는데 날로 먹는 최대 힙 문제였다ㅎㅎ 행복하게 - 두개 붙이고 통과 import heapq import sys input = sys.stdin.readline n = int(input()) hq = [] for i in range(n): m = int(input()) if m: heapq.heappush(hq, -m) else: i.. 2024. 4. 5.
[백준] 1927번: 최소 힙 - python https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 힙 자료구조를 잘 사용할 수 있는지 테스트하는 문제 ^^ 전에 회의실 문제에서 사용해서 익숙해서 쉽게 풀었다. import heapq import sys input = sys.stdin.readline n = int(input()) hq = [] for i in range(n): m = int(input()) if m: heapq.heappush(hq, m) else: if h.. 2024. 4. 5.
[백준] 18870번: 좌표압축 - python https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net 사실 처음 보고 O(n^m) 제곱으로 순간 하면 편하겠다.. 라고 생각했지만 알고리즘을 공부하는 사람으로 그짓은 이제 못하겠다. 무조건 해시맵이나 집합 자료형을 쓰는 거라고 생각했고, 코드를 작성했다. 처음에 입력받고, 입력받은 것을 토대로 set자료형으로 받고 정렬을 위해 리스트로 반환한다. 그 다음 dic로 인덱스와 값을 순서대로 저장한다. .. 2024. 4. 4.
728x90

티스토리툴바