728x90 TIL - 프로그래밍/Python 알고리즘198 [230228] n진법 구하기(with divmod) - Python divmod(a,b) 튜플 형태로 return a를 b로 나눈 몫 / 나머지 (몫, 나머지) n진법 구하기 (2 2023. 2. 28. [프로그래머스] [3차] n진수 게임 - Python https://school.programmers.co.kr/learn/courses/30/lessons/17687# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 참가인원(m)이 t바퀴 : m*t가 최대 100,000이므로 게임에 나올 수 있는 수 다 구한 뒤 튜브가 말할 수 구하기! 코드 # i를 n진법으로 변환하기 def change(n,i): box = {2:'b',8:'o',16:'x'} if n in box: return format(i,box[n]).upper() if i == 0: return '0' result = '' nn = '01.. 2023. 2. 28. 위상 정렬(Topology Sort) 알고리즘 '순서가 정해져 있는 작업'을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘 사이클 발생X 위상 정렬은 시작점이 존재해야 함 2가지 해결책을 냄 현재 그래프는 위상 정렬이 가능한지 위상 정렬이 가능하다면 그 결과는 무엇인지 큐(Queue)를 이용한 방식 진입차수가 0인 정점을 큐에 삽입 (진입 차수 : 먼저 수행되는 것 갯수) 큐에서 원소를 꺼내 연결된 모든 간선을 제거 간선 제거 이후에 진입 차수가 0이 된 정점을 큐에 삽입 큐가 빌 때까지 2번~3번 과정을 반복 모든 원소를 방문하기 전에 큐가 빈다면 사이클 존재 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과 from collections import deque # 노드의 개수와 간선의 개수를 입력 받기 v, e = map(in.. 2022. 12. 10. 벨만 포드 알고리즘 음수 간선이 포함된 상황에서의 최단 거리 문제 시간 복잡도 O(VE) 다익스트라 알고리즘에 비해 느림 동작 원리 출발 노드를 설정합니다. 최단 거리 테이블을 초기화합니다. 다음의 과정을 N-1번 반복합니다. 전체 간선 E개를 하나씩 확인합니다. 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신합니다. 만약 음수 간선 순환이 발생하는지 체크하고 싶담면 3번의 과정을 한 번 더 수행합니다. 이때 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재하는 것입니다. 다익스트라 vs 벨만 포드 다익스트라 매번 방문하지 않는 노드 중에서 최단 거리가 가장 짧은 노드를 선택합니다. 음수 간선이 없다면 최적의 해를 찾을 수 있습니다. 벨만 포드 매번 모든 간선을 전부 확인합니다. 따라서 다익스.. 2022. 12. 4. [백준] 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. 이전 1 ··· 6 7 8 9 10 11 12 ··· 33 다음 반응형
