본문 바로가기
728x90

TIL - 프로그래밍292

벨만 포드 알고리즘 음수 간선이 포함된 상황에서의 최단 거리 문제 시간 복잡도 O(VE) 다익스트라 알고리즘에 비해 느림 동작 원리 출발 노드를 설정합니다. 최단 거리 테이블을 초기화합니다. 다음의 과정을 N-1번 반복합니다. 전체 간선 E개를 하나씩 확인합니다. 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신합니다. 만약 음수 간선 순환이 발생하는지 체크하고 싶담면 3번의 과정을 한 번 더 수행합니다. 이때 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재하는 것입니다. 다익스트라 vs 벨만 포드 다익스트라 매번 방문하지 않는 노드 중에서 최단 거리가 가장 짧은 노드를 선택합니다. 음수 간선이 없다면 최적의 해를 찾을 수 있습니다. 벨만 포드 매번 모든 간선을 전부 확인합니다. 따라서 다익스.. 2022. 12. 4.
SQL - SQL 연습(설치없이) https://www.w3schools.com/sql/default.asp SQL Tutorial W3Schools offers free online tutorials, references and exercises in all the major languages of the web. Covering popular subjects like HTML, CSS, JavaScript, Python, SQL, Java, and many, many more. www.w3schools.com # 이어 붙이기 SELECT Country || City FROM Customers; # 공백 SELECT Country || ' ' || City FROM Customers; ### # MySQL은 .. 2022. 11. 1.
[백준] 12851. 숨바꼭질 2 - Python https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 생각 가장 빠른 시간으로 찾는 방법은 간단했는데 그 방법이 몇 가지인지 생각하는게 어려웠다 여러 방법 수를 구하기 위해 deque쓰기 K에 도착하기전 K-1에 도착하는 방법의 수를 셀까 하다가 같은 시간(그 위치 최단 도착 시간)에 방문하는 거 한 번 더 deque에 넣어주기 코드 from sys import stdin input = stdin.readline.. 2022. 10. 14.
[백준] 9935. 문자열 폭발 - Python https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 실패1 - 시간 초과 # 폭발 전 문자열 s = list(input()) # 폭발 문자 explosion = list(input()) e_len = len(explosion) cnt = -1 # 폭발할게 없을 때까지 == 지난 턴의 폭발 횟수가 0이면 더이상 폭발 할게 없음 while cnt != 0: # 이번 턴의 폭발 횟수 cnt = 0 for i in range(0,len(s).. 2022. 9. 23.
str.split()와 str.split(' ')의 차이 💛🧡 string = "word1 word2 word3 word4 " print(string.split()) > ['word1', 'word2', 'word3', 'word4'] print(string.split(" ")) > ['word1', 'word2', '', 'word3', '', '', 'word4', '', '', '', ''] split() : 공백이 n개이건 상관없이 무조건 1개로 보고 처리 "\t"(탭), "\n"(엔터)도 처리 split(' ') : 공백 각각을 따로따로 처리 https://school.programmers.co.kr/learn/courses/30/lessons/12930 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프.. 2022. 9. 22.
9월 22일 알고리즘 상태 및 목표 1. 프로그래머스 2. 백준 1. 프로그래머스 Lv1~3 46문제 풀기 2. 백준 class 2,3,4 채우기 (67문제) 2022. 9. 22.
반응형

티스토리툴바