Jinnie devlog

최대 부분배열의 합 - 4가지 알고리즘 비어 있지 않은 숫자 배열에서 합이 최대가 되는 연속된 부분 배열 구간의 합을 구하는 방법 4가지가 있다. 완전탐섹(브루트포스 알고리즘) 중복을 제거한 탐색 분할정복(Divide and Conquer) 동적 계획법(Dynamic Programming) 완전탐색(브루트포스 알고리즘) 단순히 모든 부분배열을 비교하여 최대인 배열을 구하는 알고리즘이다. MaxSum은 최종 결과합, ThisSum은 각 부분배열의 합을 저장하는 변수이다. 삼중반복문을 이용하여 i(0,n)~j(i,n)까지의 부분배열을 구한다. 시간복잡도: O(n^3) int MaxSubarray1(int A[], int N){ int MaxSum, ThisSum; int i,j,k; MaxSum = 0; f..

1. 자료형 수 자료형 데이터는 모두 수로 표현할 수 있다. 정수형 정수를 다루는 자료형 양의 정수, 음의 정수, 0이 있다.실수형 소수점 아래의 데이터를 포함하는 수 자료형으로 파이썬에서는 변수에 소수점을 붙인 수를 대입하면 실수형 변수로 처리한다. 소수부가 0이거나, 정수부가 0인 소수는 0을 생략하고 작성할 수 있다. 실수형 데이터를 표현하는 방식으로 파이썬에서는 e나 E를 이용한 지수 표현 방식을 이용할 수 있다. e 다음에 오는 수는 10의 지수부를 의미한다. ex) le9 는 10의 9제곱이 된다. 최단 경로 문제에서는 도달할 수 없는 노드에 대하여 거리를 ‘무한(INF)’으로 설정하곤 한다. 최댓값이 10억 미만이라면 무한(INF)을 표현할 때 10억을 사용할 수 있다. -> 이때 일일이 1..

1697(숨바꼭질), 5014(스타트링크) 두 문제 모두 큐를 활용한 BFS 방식의 문제다. 이동할 수 있는 거리만큼의 for문을 돌며, 큐에 삽입하고 이동거리를 +1씩 해주며 최종 목적지의 이동거리를 구하였다. 똑같은 위치를 반복해서 방문하게 되면, 필요없는 작업을 하게되어 visited 배열을 통해 한번만 방문하도록 하였다. 백준 1697 숨바꼭질 from collections import deque def bfs(s): q = deque([s]) visited[s]=1 while q: cur = q.popleft() if cur == K: return count[K] for i in (cur-1, cur+1, cur*2): if 0

배낭 문제 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 배낭문제는 짐을 쪼갤 수 있는 경우(무게가 소수일 수 있는 경우)와 짐을 쪼갤 수 없는 경우(이 경우 짐의 무게는 0 이상의 정수만 가능) 두 가지로 나눌 수 있는데, 짐을 쪼갤 수 있는 경우의 배낭문제를 분할가능 배낭문제(Fractional Knapsack Problem), 짐을 쪼갤 수 없는 경우의 배낭문제를 0-1 배낭문제(0-1 Knapsack Problem)라 부른다. https://ko.wikipedia.org/wiki/%EB%B0%B0%EB%82%AD_%EB%AC%B8%EC%A0%9C 배낭 문제 - 위키백과, 우리 모두의..