전체 글
[백준 1854번] K번째 최단경로 찾기 - 파이썬
⚠️ 문제 - https://www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 🔐 풀이 이 문제는 다익스트라 알고리즘을 통해 해결할 수 있었습니다. 일반적인 최단경로 찾는 문제와 다르게 위 문제는 K번째의 최단경로를 찾아야하기 때문에 일반적인 최단경로를 찾는 문제에서는 각 노드까지의 최단거리만을 배열에 저장해두는 반면, 위 문제에서는 각 노드마다 최단거리 하나만을 저장하는 것이 아닌 K개의 경로를 저장해..
[백준 2467번] 용액 - 파이썬
⚠️ 문제 - https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 🔐 풀이 이 문제의 풀이 방법은 2가지가 가능합니다. 첫 번째로 투 포인터를 사용하는 것입니다. 용액의 값은 이미 정렬되어 있기 때문에 리스트의 첫번째에는 용액의 특성값 중 가장 작은 값이, 마지막에는 특성값 중 가장 큰 값이 들어있습니다. 리스트의 양 쪽 끝에 포인터를 두고, 두 값의 합이 음수라면 왼쪽의 포인터를 한칸씩 오른쪽으로 이동시켜 더 큰 값을 더해보고 합의 절댓값이..
[백준 1300번] K번째 수 - 파이썬
⚠️ 문제 - https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 🔐 풀이 이 문제를 해결하기 위한 포인트는 어떤 수 X가 있을 때, 한 행에서 X보다 작은 값의 개수를 구하는 것이 행 번호와 관련이 있다는 것입니다. 예를 들어, 아래와 같이 3*3의 배열이 있다고 했을 때 index = 1 index = 2 index = 3 index = 1 1 2 3 index = 2 2 4 6 index = 3 3 6 9 2행에..
[백준 13904번] 과제 - 파이썬
⚠️ 문제 - https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 🔐 풀이 문제 풀이의 주요 아이디어는 과제를 첫날부터 채워가는 것이 아닌 마감일로부터 거꾸로 채워가는 것입니다. 왜냐하면 만약 마감일이 4일 남은 과제 A와 6일 남은 과제 B가 있을 때, 4일차에는 A, B 과제 모두 할 수 있지만 6일차에는 A 과제는 더 이상 할 수 없고 B 과제만 할 수 있기 때문에 과제의 마감일부터 거꾸로 매일 그 날 가능한 점수가 높은 과제를 수행하면 됩니다. 이때 거꾸로 채워감으로써 그 날 선택받지..
[백준 11000번] 강의실 배정 - 파이썬
⚠️ 문제 - https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 🔐 풀이 우선순위 큐를 통해 구현하기 위해 파이썬의 heapq를 이용했습니다. 큐에는 강의실 별로 강의가 종료되는 시간이 기록됩니다. 그러면 큐의 맨 앞에는 가장 빨리 종료되는 강의의 종료 시간이 오게 되고 이것과 추가할 강의의 시작 시간을 비교해서 만약 시작 시간이 종료 시간보다 빠르다면 새로운 강의실에서 강의를 해야해서 heappush를 통해 새로운 강의실의 종료 시간을 추가하고, 시작 시간이 종료 시간보다 느리다면 강의가 종..
[데이터베이스] SQL (Structured Query Language)
SQL (Structured Query Language) ? SQL은 1974년에 IBM 연구소에서 System R이라는 관계형 DBMS를 연구할 때 관계형 대수와 관계형 해석을 기반으로 집계 함수와 갱신 연산 등을 추가하여 개발된 데이터 언어입니다. SQL 데이터 정의어 사용자는 SQL 데이터 정의어를 사용하여 테이블, 새로운 attribute, 뷰, 인덱스를 생성 및 제거할 수 있습니다. CREATE TABLE 학생( 학번INTEGER NOT NULL, 이름CHAR(10), 나이INTEGER, 학과CHAR(10), PRIMARY KEY(학번), FOREIGN KEY(학번) REFERENCES 등록(학번) ON DELETE CASCADE, ON UPDATE CASCADE, CHECK(나이>=0 AND ..
[백준 10989번] 수 정렬하기 3 - 파이썬 (메모리 초과)
⚠️ 문제 - https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 🔐 풀이 위 문제에서는 메모리 제한이 있어서 아래와 같이 입력을 받아 배열에 넣고 정렬하게 되면 메모리 초과가 발생하게 됩니다. import sys N = int(sys.stdin.readline().rstrip()) arr = [] for _ in range(N): arr.append(int(sys.stdin.readline().rstrip())) arr.sort() for idx in range(N..
[데이터베이스] 관계형 데이터베이스
관계형 데이터 모델 관계형 데이터 모델에서 릴레이션은 2차원의 테이블을 의미합니다. 테이블의 열(필드)는 attribute, 테이블의 행(레코드)는 tuple입니다. 데이터의 가장 작은 논리적 단위인 "김철수", "010-1234-1234" 등은 attribute의 값(value)입니다. 이런 데이터 값들은 더 이상 분해할 수 없는 원자값(atomic value)만 가능합니다. 도메인이란 하나의 attribute가 취할 수 있는 같은 타입의 모든 원자들의 집합입니다. ❗️attribute의 유일성 보장 이러한 관계형 데이터 모델에서는 한 릴레이션에서 모든 attribute의 이름이 반드시 달라야 합니다. 릴레이션 릴레이션 R의 스키마(schema)는 릴레이션 이름과 attribute 집합으로 구성됩니다...