파이썬의 heapq 라이브러리를 통해 손 쉽게 최소힙과 최대힙을 구현할 수 있다. 우선, heapq는 기본적으로 최소힙으로 구현되어있다. 즉, heapq의 heappush를 통해 값들을 삽입하면 해당 값들은 숫자가 가장 작은 순서대로 트리 구조로 값이 저장된다. heapq의 연산을 사용하기 위해선 각 연산의 파라미터로 큐로 사용할 리스트와 원소를 넘겨주면 된다. 1. heappush - 값 추가 import heapq heap_q = [] heapq.heappush(heap_q, 3) heapq.heappush(heap_q, 10) heapq.heappush(heap_q, 1) heapq.heappush(heap_q, 0) heapq.heappush(heap_q, 4) print(heap_q) # [0,..
시간 제한 메모리 제한 0.1 초 128MB 문제 (링크) https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 나의 코드 import heapq import sys input = sys.stdin.readline n = int(input()) left_heap = [] right_heap = [] for _ in range(n): x = int(input()) if len(left_heap) == len(right_heap): he..
사담지원하고 싶은 회사의 지원자격 중 영어 말하기 공인시험 점수가 있었다. 토익 스피킹과 오픽 중 하나로 제출이 가능했는데, 토익 스피킹은 스크립트를 달달 외우는 시험이라고 해서 쿨하게 버리고 오픽으로 보기로 했다. 사실, 오픽 시험을 본 건 이번이 처음이 아니다. 군 생활 중 특별 외박 받으려고 공부해서 응시해본 적이 있었고, 당시에는 IH가 나왔다. 같이 공부했던 친구는 AL이 나와서 약간 자존심이 상하긴 했지만 여튼 특별 외박을 받긴 했었다. 이번 시험은 왜 갑자기 그랬는지는 기억이 안나지만 정말 급발진해서 시험 일주일 전에 신청했다. 심지어 채용 공고가 나오기도 전이어서 좀 천천히 해도 되겠다는 생각을 했을법한데 왜 그랬는지 모르겠다. 뭐에 홀렸었나보다. 아찔했던 건 시험을 본 직후 채용 공고가..
똑같은 수나 문자를 여러 번 곱하는 것을 거듭제곱이라고 한다. 흔히 우리가 말하는 2의 4제곱(2^4=16), 5의 3제곱(5^3=125) 등은 거듭제곱을 표현한 것이다. 당연히 코드를 통해서 이를 빠르게 계산할 수 있다. 반복문 사용 a의 n제곱 값을 구하고 싶을 때, for문을 사용해 직관적으로 다음과 같은 코드를 작성할 수 있다. def power(a, n): ans = 1 for _ in range(n): ans *= a return ans 재귀함수 사용 반복문이 아닌 재귀적 방식으로도 위 코드를 구현할 수 있다. a의 n제곱을 쭉 풀어보면 다음과 같다. 위 식은 부분문제로 나눌 수 있다. 만약 a의 n제곱이 아닌 a의 n+1제곱을 구하고자 할 땐 a^n의 값에 a를 한 번 더 곱해주면 되는데, ..
문제 (링크) https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 나의 풀이 # 오답 import sys from collections import deque input = sys.stdin.readline move = [ [1, 0], [-1, 0], [0, 1], [0, -1] ] r, c = map(int, input().split()) dist = [[int(1e9)] * c for _ in range(r)] q_jihun =..
문제 (링크) https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 나의 풀이 import sys import heapq input = sys.stdin.readline n, m = map(int, input().split()) start = int(input()) graph = [[] * (n+1) for _ in range(n+1)] INF = int(1e9) distance = [INF] * (n+1) fo..
문제 (링크) https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 나의 풀이 n = int(input()) stairs = [0] * (n + 1) d = [0] * (n + 1) for i in range(1, n + 1): stairs[i] = int(input()) # 계단은 한 번에 한 개 or 두 개 # 세 개 연속 X # 마지막 무조건 도착 if n == 1: print(stairs[n]) elif n == 2: print(stairs[1] + st..
트랜잭션이란? 트랜잭션은 은행 ATM이나 데이터베이스등의 시스템에서 사용되는 더 이상 쪼갤 수 없는 업무 처리의 최소 단위이다. 예를 들어 A가 B의 계좌로 1000원을 입금하는 행위가 발생할 때, "A의 계좌에서 1000원이 빠진다." 와 "B의 계좌에 1000원이 더해진다."는 더 이상 쪼갤 수 없는 최소 단위라고 할 수 있다. 이는 즉, A가 돈을 지불하는 행위와 B가 돈을 받는 행위가 분리될 수 없으며 하나의 작업으로 묶여야한다는 것을 의미한다. 트랜잭션의 특징 → 데이터베이스 작업에서 오류가 발생할 경우 데이터를 복구하는 단위가 된다. → 데이터베이스에서 한 번에 여러가지 작업이 일어날 때, 이것들을 분리해주는 작업 단위가 된다. → 트랜잭션은 묶인 작업이 모두 실행되거나 모두 실행되지 않아야한..
