본문 바로가기

분류 전체보기115

[BOJ/PYTHON] 11779. 최소비용 구하기 2 (최단 경로 - 다익스트라) 백준 문제 링크: https://www.acmicpc.net/problem/11779 문제 요약 A번째 도시에서 B번째 도시로 가는 최소비용과 경로 구하기 핵심 아이디어 문제를 읽으며 도시가 정점, 버스가 간선, 버스 비용은 가중치라는 것을 파악하면 된다! 비용이 양수라 다익스트라로 풀면 된다. ‘경로’ 구하는 게 필요했는데, 애초에 최단거리 갱신할 때 경로 정보도 같이 넣어주면 된다. 다익스트라 함수를 돌리며 현재 보는 노드가 ‘도착 도시’일 때 해당 값을 출력하면 된다. 풀이 # gold3-11779. 최소비용 구하기 2 import sys, heapq input = sys.stdin.readline n = int(input()) # 도시의 개수 m = int(input()) # 버스의 개수 grap.. 2023. 5. 16.
[BOJ/PYTHON] 11657. 타임머신 (최단 경로 - 벨만포드) 백준 문제 링크: https://www.acmicpc.net/problem/11657 문제 요약 1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하기 이동시간이 양수면 그만큼 이동, 0이면 순간이동, 음수면 타임머신으로 시간 되돌아감 핵심 아이디어 시작점, 도착점, 시간이 주어졌기에 정점과 간선의 가중치가 주어진 상황이다. 근데 이 시간이 음수 값도 가능하기에 다익스트라로 풀 수 없다. 벨만포드로 풀면 된다. 풀이 # gold4-11657. 타임머신 import sys input = sys.stdin.readline n, m = map(int, input().split()) # 도시 개수, 버스 노선 개수 edges = [] for _ in range(m): a, b, c = map(int.. 2023. 5. 16.
[BOJ/PYTHON] 18223. 민준이와 마산 그리고 건우 (최단 경로 - 다익스트라) 백준 문제 링크: https://www.acmicpc.net/problem/18223 문제 요약 마산(도착지, v번 정점)이 더 가까우면 그냥 마산으로, 최단 경로에 건우가 있으면 겸사겸사 구해줌 민준이가 찾은 최단 경로 위에 건우가 있다면 "SAVE HIM" 을 아니면 "GOOD BYE" 를 출력 핵심 아이디어 그래프 간선에 가중치가 있고, 가중치가 양수이기 때문에 다익스트라 알고리즘을 사용하면 된다. 이때, 건우를 구해준 후 마저 마산까지 가는 거리가 최단경로보다 길어지지 않으면 건우를 구하는 거라 건우를 구하러까지 가는 최단 거리, 구하고 나서 마산까지 가는 최단 거리, 출발지에서 마산까지 직통으로 가는 최단 거리값들이 필요하다. 풀이 # gold4-18223. 민준이와 마산 그리고 건우 impor.. 2023. 5. 16.
[Database] 데이터 모델 데이터 모델 : 현실 세계의 정보들을 컴퓨터에 표현하기 위해 단순화, 추상화해 표현한 개념적 모형. 데이터베이스 설계 과정에서 데이터의 구조(스키마)를 논리적으로 표현하기 위해 사용되는 도구. 데이터 모델 구성 요소: 개체, 속성, 관계 개체(Entity): DB에 표현하려는 개념. 속성으로 구성됨. 특징 파일 시스템의 레코드에 대응. 정보 제공 역할. 영속적으로 존재하는 개체의 집합. 다른 개체와 하나 이상의 관계 맺음. 유일한 식별자에 의해 식별 가능 예시) 교수 개체는 속성(교수번호, 성명, 전공, 소속)으로 구성. 개체 타입(레코드 타입): 속성(으로만 기술된 개체의 정의) 개체 인스턴스: 하나의 개체 나타내는 것. 한 줄. 개체 세트: 개체 인스턴스의 모음 개체 선정 방법 자료 흐름도(DFD)를.. 2022. 11. 21.
[Algorithm] 구현 - 완전 탐색(Brute Force), 백트래킹 구현이란 구현: 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 완전 탐색: 모든 경우의 수를 탐색하며 다 계산하는 해결 방법 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행 구현 문제 접근법 사소한 입력 조건 등을 문제에서 명시 문제 길이가 긴 편 완전 탐색 완전 탐색 문제의 조건 경우마다 따질 게 명확 특정 상태를 구성하고, 그 상태가 특정 조건을 만족하는지 검토해야 경우의 수가 모두 탐색할 수 있을 만큼 적음 시간복잡도를 생각하지 않으면 완전탐색으로 모든 문제를 풀 수 있으므로, 처음에 완전탐색 풀이를 생각한 후 차츰 최적화하는 방식도 꽤 많은 문제에서 유용함 모든 경우를 탐색하는 풀이를 생각해 봤는데 N(입력)제한이 매우 작다면 완전 탐색을 의심 완전 탐색 문제를 푸는 법 모.. 2022. 11. 13.
[Algorithm] 그리디(greedy, 탐욕법) 그리디 알고리즘 그리디: 탐욕법. 어떤 문제가 있을 때 ‘현재 상황에서 지금 당장 좋은 것만 고르는 방법’으로 문제 푸는 것. 현재의 선택이 나중에 미칠 영향은 고려 X 현재 상황에서 가장 좋아 보이는 것만을 선택해도 풀 수 있는 문제 보통 정렬 기준 제시해줌: 큰 순서대로, 작은 순서대로 등 그리디 알고리즘의 정당성 풀이를 위한 아이디어 떠올리고 이것이 정당한지 검토할 수 있어야 부분 문제로 나눠서 구한 답이 전체 문제의 일부 부분적인 최적 전략을 반복적으로 하면 답이 나오는 문제 참고 이것이 취업을 위한 코딩테스트다 2022. 11. 13.

티스토리툴바