honalog

구현방법- 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 힙 자료구조 이요1. 현재 가장 가까운 노드를 저장해 놓기 위해 힙 자료구조를 추가적으로 이용2. 현재 최단 거리가 가장 짧은 노드를 선택해야하므로 최소 힙 사용 import heapqimport sysinput = sys.stdin.readlineINF = int(1e9) # 무한을 의미하는 값으로 10억을 설정# 노드의 개수, 간선의 개수를 입력받기n, m = map(int, input().split())# 시작 노드 번호를 입력받기start = int(input())# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기graph = [[] for i in range(n + 1)]# 최단 거리 테..

각 지점은 노드로 표현, 연결된 도로는 간선으로 표현 다익스트라 최단 경로 알고리즘: 가장 비용이 적은 노드 선택해서 과정 반복 - 알고리즘 동작 과정1. 출발 노드 설정2. 최단 거리 테이블 초기화3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택4. 해당 노트를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신5. 3,4번을 반복   - 다익스트라 알고리즘 특징그리디 알고리즘: 매 상황에서 방문하지 않은 가장 비용이 적은 노드 선택해서 임의의 과정 반복한번 처리된 노드의 최단거리는 고정되어 더이상 바뀌지 않는다한 단계당 하나의 노드에 대한 최단거리를 확실히 찾는 것으로 이해할 수 있다.- 다익스트라 알고리즘 수행한 후 테이블에 각 노드까지 최단 거리 정보 저장됨 - 간단 ..

다이나믹 프로그래밍 = 동적 계획법 - 동적자료구조 : 프로그램이 실행되는 도중 실행에 필요한 메모리 할당하는 기법다이나믹 프로그래밍: 의미 없음 - 조건1. 최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있음, 작은 문제의 답을 모아 큰 문제 해결2. 중복되는 부분 문제: 동일한 작은 문제 반복적으로 해결 - 피보나치 수열1,1,2,3,5,8,13,21,34,55,89 점화식 : 인점한 항들 사이의 관계식 수열을 배열/리스트에 저장 #피보나치 수열 끝날 때를 명시(x == 1 / x == 2)def fibo(x): if x == 1 or x == 2: return 1 return fibo(x-1) + fibo(x-2)print(fibo(4)) - 탑타운 = 하향식 = 메모이제이션한 번 ..

파라메트릭 서치 : 최적화 문제를 결정 문제(예 혹은 아니오)로 바꿔 해결하는 기법ex) 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제 일반적으로 코테에서 파라메트릭 서치 문제는 이진 탐색을 이용해 해결할 수 있음 # 떡볶이 떡 만들기# 떡의 개수N 과 요청한 떡의 길이 m 입력n,m = list(map(int, input().split(' ')))# 각 떡의 개별 높이 정보를 입력array = list(map(int, input().split()))# 이진탐색을 위한 시작점과 끝점 설정start = 0end = max(array)# 이진 탐색 수행(반복)result = 0while(start mid: total += x - mid # 떡의 양이 부족한 경우..

이진탐색 라이브러리bisect_left(a,x) : 정렬된 순서 유지하면서 배열 a에 x 삽입한 가장 왼쪽 인덱스 반환bisect_right(a,x) : 정렬된 순서 유지하면서 배열 a에 x 삽입할 가장 오른쪽 인덱스 반환 from bisect import bisect_left, bisect_rightdef count_by_range(a,left_value, right_value): right_index = bisect_right(a,right_value) left_index = bisect_left(a, left_value) return right_index - left_indexa =[1,2,3,3,3,3,4,4,8,9]print(count_by_range(a,4,4))print(co..

순차탐색: 기본적인 탐색 알고리즘 이진탐색 : 정렬된 리스트에서 탐색 범위 절반씩 좁혀가며 데이터 탐색탐색범위: 시작점, 끝점, 중간점(소수점 이하 제거) 시간복잡도 : O(logN) def binary_search(array, target, start, end): while start target: end = mid -1 else: start = mid +1 return Nonen, target = list(map(int, input().split()))array = list(map(int, input().split()))result = binary_search(array, target, 0, n-1)if result == None: ..

코드 설명  n = int(input())array = []for _ in range (n): data =input().split() array.append((data[0],int(data[1])))array = sorted(array,key = lambda student: student[1])for student in array: print(student[0], end = ' ')  append(())는 파이썬에서 리스트에 튜플 형태의 데이터를 추가 append()에 data[0],int(data[1]) 튜플 추가 print(student)-> ('홍길동', 95), ('이순신', 77) print(student[0])-> 홍길동 이순신

n, k = map(int,input().split())a = list(map(int, input().split()))b = list(map(int, input().split()))a.sort()b.sort(reverse=True)for i in range(k): if a[i]

📕 문제https://school.programmers.co.kr/learn/courses/30/lessons/60059 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  📄 내가 생각한 풀이  💻 답안 # 2차원 리스트 90도 회전def rotate_a_metrix_by_90_degree(a):#행길이 계산 n = len(a)# 열길이 계산 m = len(a[0])# 결과리스트 result = [[0]*n for _ in range(m)] for i in range(n): for j in range(m): result[j][n-i..

📕 문제A, B 두 사람이 볼링을 치고 있습니다. 두 사람은 서로 무게가 다른 볼링공을 고르려고 합니다. 볼링공은 총 N개가 있으며 각 볼링공마다 무게가 적혀 있고, 공의 번호는 1번 부터 순서대로 부여됩니다. 또한 같은 무게의 공이 여러개 있을 수 있지만, 서로 다른 공으로 간주합니다. 볼링공의 무게는 1부터 M까지의 자연수 형태로 존재합니다.예를 들어 N이 5이고, M이 3이며 각각의 무게가 차례대로 1, 3, 2, 3, 2일 때 각 공의 번호가 차례대로 1번부터 5번까지 부여됩니다. 이때 두 사람이 고를 수 있는 볼링공 번호의 조합을 구하면 다음과 같습니다.(1번, 2번), (1번, 3번), (1번, 4번), (1번, 5번), (2번, 3번), (2번, 5번), (3번, 4번), (4번, 5번)결..