1. 파라메트릭 서치란? 파라메트릭 서치는 최적화 문제를 결정 문제로 바꾸어 풀어 나가는 기법입니다. 여기서 결정 문제란 'yes' or 'no', 즉, '예' 또는 '아니오'로 답하는 문제를 말합니다. 파라메트릭 서치는 주로 특정 조건을 만족하면서 동시에 가장 적합한 변숫값을 찾아나가는 문제에서 활용되며, 이진 탐색(Binary Search)을 이용하여 구현합니다. 예를 들어, 특정 조건을 만족하는 가장 큰 값을 구하는 최적화 문제에서 이진 탐색을 통해 적합한 해(solution)의 범위를 절반씩 좁혀 나갈 수 있습니다. 2. 파라메트릭 서치는 언제 사용하면 좋을까? 앞서 파라메트릭 서치 문제는 이진 탐색을 활용해 해결할 수 있다고 했습니다. 이진 탐색 알고리즘은 입력 데이터가 많거나(e.g., 1,0..

동적계획법 (다이나믹 프로그래밍)에 대해서 코딩 문제는 많이 푼 것 같지만 여러 유형의 dp 에 대해 다뤄보지 못한 것 같아 포스팅한다. 본 게시글은 해당 게시글의 내용 파이썬으로 변경하였다. 예를 들어 정수들이 저장된 nXn의 좌상단에서 우 하단 까지 이동하는 문제에서 오른쪽이나 하단으로만 이동이 가능하다는 조건으로 지나간 값들의 합이 최소가 되도록 하는 최적의 경로를 찾아보자. 0,0에서 i,j 까지 가는 방법은 2가지가 있다. i, (j-1)를 거쳐서 오거나 (i-1), j 로 오는 방법이다. 이렇게 거쳐서 오는 값들을 수식으로 확인해보면 다음과 같다. 그럼 파이썬으로 프로그래밍 하자. def mat(i,j): if i == 1 and j == 1: return m[i][j]; # 외길로 판단하여 ..

다익스트라 알고리즘은 한 지점에서 다른 모든 지점까지의 최단 경로를 계산하는 알고리즘이다. 플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 계산하는 알고리즘이다. 다익스트라의 시간 복잡도는 간단하게 구현하면 O(V²)이고 개선된 방법은 O(ElogV)이다. 플로이드 워셜의 시간 복잡도는 O(V³)이다. 최단 경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 그래서 '길 찾기' 문제라고도 불린다. 최단 경로 알고리즘 유형에는 다양한 종류가 있는데, 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있다. 최단 경로 문제는 보통 그래프를 이용해 표현하는데 각 지점은 그래프에서 '노드'로 표현되고, 지점 간 연결된 도로는 그래프에서 '간선'으로 표현된다. 컴퓨터공학과 학부 ..

보호되어 있는 글입니다.

미로찾기를 해봅시당 https://www.youtube.com/watch?v=nyjFmDUDgO4 코딩 빌런님의 영상을 보고 정리한 글입니다. 미로를 찾기위해선 두가지를 수행해야합니다. - 미로가 처음과 끝이 이어진 길인지(목적지 까지 갈 수 있는가) - 미로를 어떻게 최단경로로 갈 것인가 자 그럼 먼저 첫번째 부터 봅시다 1. 미로가 목적지 까지 갈 수 있는가 먼저 [0,0] 을 올라 타고 array에 [0,0] 을 넣어준다. 그 뒤 해당 좌표에는 -1 값으로 변경하고 array에서 없애줌 (갔던 길 임을 표시하는 것) 그리고 좌표를 돌면서 갈 수 있는 길인지 확인한다. 이 알고리즘대로 하면 목적지에 갈 수 있는지 알고리즘을 수행하게 됨 코드로 나타낸 것을 확인해보자 pop은 값을 반환하고 그 값을 빼..

import re s = 'apple orange:banana,tomato' l = re.split(r'[ ,:]', s) print(l) ''' ['apple', 'orange', 'banana', 'tomato'] '''

Pyhton 진법 변환 n진수 → 10진수 * 결과값은 모두 string 입니다. python에서는 기본적으로 int() 라는 함수를 지원한다 int(string, base) 위와 같은 형식으로 사용. base에는 진법을 넣으면 된다. print(int('101',2)) print(int('202',3)) print(int('303',4)) print(int('404',5)) print(int('505',6)) print(int('ACF',16)) 20 51 104 185 2767 10진수로 변경이 가능하다. 10진수 → 2, 8, 16진수 2, 8, 16진수는 bin(), oct(), hex() 함수를 지원한다. print(bin(11)) print(oct(11)) print(hex(11)) 0b101..

4-Queens 문제 (n = 4) 4개의 퀸을 4x4 체스보드에 배치 일단, 기본 가정으로 같은 행(row)에는 놓을 수 없음 후보 해답: 4 * 4 * 4 * = 256 가지의 탐색 공간이 있음 (하나의 행에 하나만 놓을 수 있다는 것 -> 4가지, 4개의 행) -> 4*4*4*4 프루닝 (가지치기)와 프로미싱을 어떻게 할 것인가? 첫번째 경우 -> 2번째행 3열,4열 (퀸을 둘 수 있음) 두번째 행에서 3번째 열에 해당될때 모든 경우의 수가 성립하지 않으므로 다음 경우의 수로 넘어간다. 그다음 행에서 가능한 공간을 찾아보자. 대각선, 같은 행, 같은 열에는 존재하면 안된다. (서로 공격하지 못하는 거리에 있어야함 성립하는 경우가 없으므로 다른 경우로 넘어가자 N-Queens 문제 해결 기본 가정: ..

되추적 / 백트래킹(backtracking) 임의의 집합(set)에서 주어진 기준(criterion)대로 원소의 순서를 선택하는 문제를 푸는 데 적합 트리 자료구조의 변형된 깊이 우선 탐색(DFS) 모든 문제 사례에 대해 효율적이진 않지만 많은 문제 사례에 대해 효율적임 n-Queens, 부분 집합의 합, 0-1 배낭문제, etc 미로찾기 문제 해당 문제는 스택 알고리즘을 이용해서도 풀 수 있다. 예시 pop: stack의 마지막에 있는 것 꺼낸다 posh: stack의 제일 뒤에 쌓는다 DFS 형태로 방문하고 백트래킹 하는 형식으로 문제를 해결할 수 있다. 상태공간트리(State Space Tree) 상태공간: 해답을 탐색하기 위한 탐색 공간 상태공간트리: 탐색 공간을 트리 형태의 구조로 암묵적으로 해..

보호되어 있는 글입니다.

사용자에게 빠르게 정보를 제공하기 위해 사용하는 캐시에서 새로운 데이터가 발생했을 때, 가장 오래전에 사용된 데이터를 제거하고 새로운 데이터를 삽입하는 알고리즘입니다. 새로운 데이터가 들어온 경우 캐시에 넣어준다. 캐시가 가득차있다면, 가장 오래된 데이터를 제거하고 넣어준다. 존재하는 데이터가 들어온 경우 해당 데이터를 꺼낸 뒤, 가장 최근 데이터 위치로 보내준다. 파이썬으로 구현하면 다음과 같습니다. cache_Size = 5 cache = [1, 2, 3, 4, 5] user_data = [3, 7, 2] for data in user_data: # Miss! if data not in cache: if len(cache) < cacheSize: cache.append(data) else: cache..

정보들이 다 기록되며 진행된다. DFS(3)을 호출하면 Stack에 해당 내용이 저장이됨 호출되는 순간 DFS(2)가 호출됨 그리고 해당 x=2에대한 내용이 Stack에 새로 할당되어 저장이됨 그럼 이제 DFS(1)함수도 호출 됨 이러한 매개변수, 지역변수, 복귀주소에 대한 내용이 스택프레임이라고 명명함 D(3) -6 :이런거는 그냥 6번째 줄 코드에 있는 DFS로 간다는 말임 함수 다 돌고 종료되면 스택에 있는 최상단에 있는 것들이 지워진다... 메모리들이 해제된다 이말이야 그러면 제일 위부터 보자 제일 상단에 있는 얘가 DFS(2) 에서 6번째 라인으로 복귀한다고 했으니 그럼 뭐다? 그럼이제 7라인에서 x값인 1이 출력이 됨 그다음 2 출력 그 다음 3 출력