백준(8)
-
🥈백준 1966 프린터 큐 python 풀이 / 딕셔너리 큐를 사용한 풀이
문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다. 예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 ..
2024.01.15 -
[Python] 🥈백준 2667 단지 번호붙이기 /DFS를 활용하여 연결요소 구하기
예제 입력 1 7 0110100 0110101 1110101 0000111 0100000 0111110 0111000 예제 출력 1 3 7 8 9 아이디어 생각하기 연결요소 문제는 풀어도 풀어도 뇌리에 안 박혀서 이렇게 블로그를 쓰고자 한다.... 로직순서 변수설명 map: 지도, home: 각각 단지내 집의 수, nums: 각각 단지내 집의 수를 담는 리스트 (1) 단지 지도 생성 (2) dfs 알고리즘을 돌며, ⓐ 범위를 벗어날 때 ⓑ집이 있을 때 ⓒ집이 없을 때 경우를 나눈다. ⓐ ⓒ는 return False (3) ⓑ 집이 있을 때의 경우, home +=1 집을 1개 추가하고 maps[x][y] = 0 #숫자를 세고 0으로 집을 없앰 다시 못 돌게 집을 없애버린다 dfs(x-1,y) #상하좌우 재..
2023.02.19 -
[Python] 백준 파이썬 풀이 11724/연결 요소의 개수
문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. 출력 첫째 줄에 연결 요소의 개수를 출력한다. 예제 입력 1 6 5 1 2 2 5 5 1 3 4 4 6 예제 출력 1 2 import sys input = sys.stdin.readline sys.setrecursionlimit(1000000) #재귀 최대깊이, dfs 사용 시 오류 방지 n, m = map(int, inp..
2023.02.02 -
[Python] 백준 11652번 풀이 / 카드 / sorted()에서의 key lambda 사용하기
문제 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지고 있는 정수를 구하는 프로그램을 작성하시오. 만약, 가장 많이 가지고 있는 정수가 여러 가지라면, 작은 것을 출력한다. 입력 첫째 줄에 준규가 가지고 있는 숫자 카드의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 출력 첫째 줄에 준규가 가장 많이 가지고 있는 정수를 출력한다. 예제 입력 1 5 1 2 1 2 1 예제 출력 1 1 틀렸던 코드 import sys input = sys.stdin.readline n = int(inp..
2023.01.30 -
[Python] 퀵 정렬 알고리즘/ 이것이 코딩테스트다 정렬편
퀵 정렬 "기준을 정하고 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 정렬" 우리는 정렬할 배열의 0번째 인덱스를 기준으로 삼을 것이다. 이 기준을 피벗이라고 부른다. 퀵 정렬을 사용하여 리스트 [5,7,9,0,3,1,6,4,8]을 오름차순으로 정리해보도록 하자 (1) 리스트의 왼쪽부터 피벗보다 큰 값을 찾고, 오른쪽부터는 피벗보다 큰 값을 찾은 후, 둘의 위치를 바꿔준다 (2) 다시 왼쪽부터 탐색하여 피벗(5)보다 큰 수(9), 작은 수(3)의 위치를 바꿔주자 (3) 위 과정을 반복하게 되면 작은 수와 큰 수가 엇갈리게 되어 바꿀 수 없는 상황이 온다 !! (4) 이럴 땐 작은 수와 피벗의 위치를 바꾼다 (5) 이렇게 되면 피벗의 왼쪽은 피벗보다 작은 수 오른쪽은 큰 수가 정렬된다. (6) 각각 ..
2023.01.30 -
[Python] 백준 10989번 수 정렬하기 3 /메모리 초과 오류 해결
import sys input = sys.stdin.readline n = int(input()) arr = [] for i in range(n): arr.append(int(input())) arr.sort() for i in arr: print(i) 입력받은 값을 빈 배열 arr에 append 후, sort()함수로 오름차순하여 출력하는 형식을 생각했다 하지만 메모리 초과 발생...! 메모리 제한이 8MB로 굉장히 작은데, 많은 메모리를 소요하는 파이썬으로 실행하니 쉬운 문제임에도 불구하고 오래 걸렸다.... 메모리 초과 발생 이유 (1) sort,sorted를 사용 (2) sys.stdin.readline이 아닌 그냥 input()를 사용 (3) for 문 안에 append를 작성 따라서 이 문제는..
2023.01.30