내 취미는 머신러닝

플로이드 워셜 알고리즘 최단 거리 정보 저장 다익스트라 : 1차원 리스트 플로이드 : 모든 노드에 대해 다른 모든 노드로 가는 최단거리 정보를 담아야 하기 때문에 2차원 리스트를 사용한다. → O(N^2) 알고리즘 다익스트라 : 그리디 알고리즘 플로이드 : 다이나믹 프로그래밍, N번만큼의 단계를 반복하며 ‘점화식에 맞게’ 2차원 리스트를 갱신한다. INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정 # 노드의 개수 및 간선의 개수를 입력받기 n = int(input()) m = int(input()) # 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화 graph = [[INF] * (n + 1) for _ in range(n + 1)] # 자기 자신에서 자기 자신으로 가..

https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 풀이전략 : 18은 3으로 나누면 6개가 되지만, 5로 먼저 나누면 3개 + 나머지를 3으로 나누면 1개가 된다. 즉 큰 수로 나누는 것이 개수를 최소로 할 수 있다. 5로 나누어 떨어지는 수 5로 나눈 몫을 cnt(개수)에 담는다. 5로 나누어 떨어지지 않는 수 3으로 계속해서 뺀다. 3으로 빼다가 5의 배수가 되었을 때 5로 나눈다. while이 n > 0 이면 3의 배수 ex.9를 처리하지 못한다. 등..

최단 경로 문제 최단경로 알고리즘이란, 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 다양한 문제 상황 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 → 플로이드 워셜 알고리즘 각 지점은 그래프에서 노드로 표현한다. ex) 국가, 도시 등 지점 간 연결된 도로는 그래프에서 간선으로 표현한다. 다익스트라 최단 경로 알고리즘 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다. 음의 간선이 없을 때 정상적으로 동작한다. 그리디 알고리즘으로 분류된다. 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복한다. 특징 그리디 : 매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택해 임의의 과..

문제 출처 : BOJ 1932번 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 풀이 접근) 다이나믹 프로그래밍 알고리즘 2차원 행렬 dp테이블을 만들어야 한다. input으로 받는 숫자들을 dp 테이블로 둔다. 다음 행을 기준으로 전 행이 어디로 이동할 수 있는지 파악해야 한다. (이동 제약이 걸려있는 문제들이 보통 그런다) 이게 무슨말이냐.. 아래 예시를 보면 1은 위에서(8) 내려올 수 있고 위에서 왼쪽(3)에서 내려올 수 있다. 이 두가지로 케이스를 나누어야 한다. 답) 내가 풀다가 포기해서 동빈..

sorted()와 sort() 차이 한눈에 보기 sorted() : 반환 값으로 정렬된 리스트를 뱉어낸다. sort() : 리스트 자체가 정렬되는 것이다. num = [15, 26, 39] # 내림차순 정렬 # return 값이 있기 때문에 변수로 받아줘야 한다. result = sorted(num, reverse = True) print(result) # 결과 [39, 26, 15] num = [15, 26, 39] # num 이라는 리스트 자체를 정렬하는 것이다. num.sort(reverse = True) print(num) # 결과 [39, 26, 15] sorted() 인자값 reverse = True : 내림차순 정렬, default = False key : key 값을 기준으로 정렬한다. 여..

복잡도 : 알고리즘의 성능을 나타내는 척도 시간 복잡도 : 특정한 크기의 입력에 대해 알고리즘의 수행 시간 분석 공간 복잡도 : 특정한 크기의 입력에 대해 알고리즘의 메모리 사용량 분석 → 복잡도가 낮을수록 좋은 알고리즘 빅오 표기법(big-O notation) 가장 빠르게 증가하는 항만 고려함 함수의 상한만을 고려함 $3N^3 + 5N^2 + 1,000,000$ → 빅오 표기법으로는 계수도 무시하고 가장 큰 항만 남겨 $O(N^3)$ 으로 표기함 수행시간 측정 코드 import time start_time = time.time() # 측정 시작 end_time = time.time() # 측정 종료 print("time:", end_time-start_time) 실수형 컴퓨터는 2진수로 이해하기 때문에..

* 문제에 대한 설명은 프로그래머스 사이트에 나와있기 때문에 적지 않았습니다. https://school.programmers.co.kr/learn/courses/30/lessons/42889?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 첫 코드(1,6,7,9,13,23,24번 실패) 실패한 이유를 모르고 정말 헤맸다.. 근데 알고리즘 스터디를 하면서 알게되었다. 진작 내가 짠 코드를 하나하나 그려볼 걸 그랬다. def solution(N, stages): answer = [] result = [] for i in rang..

스택 선입후출, LIFO 입구와 출구가 동일한 형태 append(), pop()은 시간복잡도가 O(1) stack = [] stack.append(5) # [5] stack.append(2) # [5,2] stack.append(3) # [5,2,3] stack.pop() # [5,2] stack.append(6) # [5,2,6] print(stack[::-1]) # [6,2,5] 가장 위에 있는 원소부터 출력 큐 선입선출, FIFO 리스트를 이용할 수 있지만 시간복잡도가 효율적이지 않아서 라이브러리 이용 from collections import deque queue = Queue() queue.append(5) queue.append(2) queue.append(3) queue.popleft() q..

구현(Implementation) 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 알고리즘에서 구현? 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제 구현의 유형 알고리즘은 간단한데(이렇게 이렇게 하면 될거같은데?!) 코드가 길어지는 문제(구현을 못함..) 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제 파이썬이 다른 언어들보다 문자열 처리하기 편함 적절한 라이브러리를 찾아서 사용해야 하는 문제 순열/조합 파이썬 itertools 사소한 조건 설정이 많은 문제 시뮬레이션과 완전 탐색 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 직접 수행하는 방법 완전 탐색 : 모든 경우의 수를 주저없이 전부 계산하는 방법 일반적으로 ..