전체 글

https://www.acmicpc.net/problem/10798 10798번: 세로읽기 총 다섯줄의 입력이 주어진다. 각 줄에는 최소 1개, 최대 15개의 글자들이 빈칸 없이 연속으로 주어진다. 주어지는 글자는 영어 대문자 ‘A’부터 ‘Z’, 영어 소문자 ‘a’부터 ‘z’, 숫자 ‘0’ www.acmicpc.net 풀이 입력으로 5개의 단어가 주어진다. 단어들의 길이는 15글자를 넘지않기에 리스트를 작성해서 이중for문으로 출력해준다. # 10798번 세로읽기 import sys input = sys.stdin.readline graph = [[False]*15 for _ in range(5)] for i in range(5): word = list(input().rstrip()) for j in r..

사실상 java와 제어문이 유사하기에 따로 건들부분이 없었다. 기본적인 코드에 대해서 알아보겠다. if문 switch문 for문 while문 do while문 break continue 조건연산자 => (조건) ? (true일 경우 실행) : (false일 경우 실행) 퀴즈1 짝수일까, 홀수일까 퀴즈2 3의 배수 찾기

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 풀이 1, 단방향문제 최대값이 문제없어서 INF는 10억을 잡아주었다. 2, 각 경우의 수의 distance를 받아서 마을 ->파티 경로랑 파티 -> 마을 경로를 더해서 비교해준다. 마무리만 잘해주면 된다. # 1238번 파티 import sys import heapq input = sys.stdin.readline INF = int(1e9) def dijkstra(..

https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 풀이 음수의 간선이 포함되었기에 벨만 포드 알고리즘으로 문제를 풀어준다. 벨만포드의 알고리즘은 다익스트라 알고리즘의 최적의 해를 포함한다. 다만 시간복잡도가 다익스트라에 비해 높다.자세한 내용은 https://sunghyun98.tistory.com/51 이 글에서 확인 할 수 있다. # 11657번 타임머신 # 벨만 포드 알고리즘 im..

본문에 앞서 질좋은 책을 집필해주신 나동빈님한테 감사합니다. 벨만포드 알고리즘을 최단경로 문제에서 다익스트라 대신 사용해도 문제는 없지만 시간복잡도가 증가하기에 가급적으로 음수 간선이 존재할 때만 사용해주자 최단경로 문제 유형 1) 모든 간선이 양수인 경우 2) 음수 간선이 있는 경우 2-1) 음수 간선 순환은 없는 경우 2-2) 음수 간선 순환이 있는 경우 벨만 포드 최단 경로 알고리즘은 음의 간선이 포함된 상황에서도 사용할 수 있다. 또한 음수 간선의 순환을 감지할 수 있습니다. 벨만 포드의 기본 시간 복잡도는 O(VE)로 다익스트라 알고리즘에 비해 느리다. 벨만 포드 알고리즘 단계 1) 출발 노드를 설정한다. 2) 최단 거리 테이블을 초기화합니다. 3) 다음의 과정을 N-1번 반복합니다. 3-1) ..

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이 1, 양방향이고 최대치를 sys.maxsize로 잡아서 문제의 제한사항으로부터 자유로워 졌다. 2, 똑같은 다익스트라문제이지만 무조건 마지막에 주어진 두 정점을 지나야하기때문에 시작값이 매개변수로 주어진 다익스트라 함수를 만들어서 경로 1 - num1 - num2 - n 이랑 1 - num2 - num1 - n을 비교해준다. # 1504번 특정한 ..

https://www.acmicpc.net/problem/14284 14284번: 간선 이어가기 2 정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. www.acmicpc.net 풀이 1, 양방향이며 최대치는 5억이기에 INF는 10억으로 잡아주었다. 2, 다익스트라 적용 # 14284번 간선 이어가기 2 import heapq import sys input = sys.stdin.readline INF = int(1e9) def dijkstra(start, target): q = [] # heapq.heappush(dist, node) heapq.heappush(q,..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 풀이 1, 양방향 문제이다. INF는 10억이기에 int(1e9)로 해주었다. 2, 다익스트라 적용 # 1916번 최소비용 구하기 import heapq import sys input = sys.stdin.readline INF = int(1e9) def dijkstra(start, target): q = [] # heapq.heappush(dist, node) ..