나를 위한 개발일기 나를 위한 개발일기

다이나믹 프로그래밍 다이나믹 프로그래밍의 가장 큰 특징은 메모리를 적절히 사용해 수행 시간을 비약적으로 증가시키는 방법이다. 메모리가 완전 탐색에 비해 더 많이 필요할 수 있지만 메모리를 조금 더 사용함으로써 수행 시간을 비약적으로 증가시킨다. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장해 다시 계산하지 않도록 하며 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운, 버텀업)으로 구성된다. 다이나믹 프로그래밍은 문제가 다음의 조건을 만족할 때 사용할 수 있다. 최적 부분 구조 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. ex) 피보나치 수열 중복되는 부분 문제 동일한 작은 문제를 반복적으로 해결해야 한다. ex) f(2)의 반복적인..

정렬 알고리즘 정렬이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다. 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다. 블로그의 [모두의 알고리즘] 탐색과 정렬 편에 정리 해두긴 했지만 장기기억으로 변화시키기 위해 한번 더 정리해본다. 선택정렬 O(N^2) 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복하며 정렬한다. array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i # 가장 작은 원소의 인덱스, 첫 번재 인덱스의 값이 가장 작다고 가정. for j in range(i+1, len(array)): # i 다음 값 부터 살펴봄 ..

탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이며, 대표적인 그래프 탐색 알고리즘으로 DFS와 BFS가 있다. 그래프 탐색 알고리즘을 공부하기 전 먼저 알아두면 좋은 개념들을 먼저 정리한다. 스택: LIFO 형식의 자료구조. 입구와 출구가 동일한 형태라 생각하면 된다. 비유하자면 뷔페의 접시 파이썬에서 기본적인 리스트를 이용해 스택구조를 활용할 수 있다. stack = [] # 순서대로 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() stack.append(5) stack.append(2) stack.append(3) stack.append(7) stack.pop() stack.append(1) stack.append(4) stac..

구현 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정. 대게 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭한다. 구현 유형의 예시는 다음과 같다. 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제 적절한 라이브러리를 찾아서 사용해야 하는 문제 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용된다. # 동, 북, 서, 남 dx = [0, -1, 0, 1] dy = [1, 0, -1, 0] # 현재 위치 x, y = 2, 2 for i in range(4): # 다음 위치 nx = x + dx[i] ny = y + dy[i] print(nx,ny) - 완전..

요즘 프로그래머스나 백준 같은 알고리즘을 풀어볼 수 있는 사이트에서 알고리즘 문제들을 하나씩 풀어보고 있다. 방학동안 한 스타트업에서 IT Admin 계약직으로 일하게 돼 업무가 바쁘지 않은 동안은 내 공부를 할 수 있었는데, 이 시간에 어떤 걸 공부하면 좋을까 생각하다 알고리즘 문제를 풀어보게 됐다. 맞은 문제는 다른 사람들의 코드를 보며 더 간결한, 빠르게 작동하는 방식도 있다는 점을 배웠고, 아무리 생각해도 어떤 방법으로 풀어야 할 지 모르겠는 문제들도 있었다... 물론 이런 경우 구글링하면 대부분 나오긴 했으나 이해가..안되는.. 경우도 있었다..ㅎㅎ 알고리즘 문제에도 유형이 존재한다는 것을 알게 됐고, 유형별로 공부를 해야겠단 생각을 했다. 알고리즘 문제를 풀어보며 느낀 것은 어떤 방식으로 풀어..

자료구조 회문찾기(큐와 스택) 큐: 줄서기. FIFO(First In First Out) 인큐와 디큐: 인큐는 자료를 집어 넣는 동작이고 디큐는 자료를 빼내는 동작. 스택: 접시 꺼내기. LIFO(Last In First Out) 뷔페에서 맨 아래 있는 접시를 꺼내려면 맨 위에 있는 접시부터 하나하나 꺼내야 한다. 푸쉬, 팝: 푸쉬는 스택에 자료를 집어 넣는 동작, 팝은 자료를 빼는 동작 큐와 스택은 자료를 일렬로 보관하는 특징이 있다. 리스트를 사용해 큐와 스택을 만들어 볼 수 있다. 큐) qu = [] : 빈 리스트를 만들고 qu.append(x) : 리스트의 맨 뒤에 x를 추가한다 x = qu.pop(0) 리스트의 맨 앞에서 자료를 꺼낸다. 스택) st = [] : 마찬가지로 빈 리스트를 생성 st..

탐색과 정렬 병합정렬 / O(n*log n) 재귀호출을 이용한 방법과 일반적인 방법이 있다. 재귀호출을 이용한 방법 리스트의 중앙값을 mid로 두고 g1은 mid의 왼쪽 값들, g2는 mid의 오른쪽 값들로 설정한다. g1과 g2에 값이 있는 동안 g1이 각 배열의 첫 번째 값들을 비교하며 작은 것을 결과 리스트에 추가한다. g1과 g2 둘 중에 한쪽 값만 남게 되는 경우 순서대로 결과 리스트에 추가하며 정렬한다. 일반적인 방법 퀵정렬 기준과 비교해서 그룹을 나눈 다음 각각 재귀 호출해 합치는 방식 재귀호출을 이용한 방법 기준을 맨 끝 인덱스 값으로 잡고 리스트의 값이 기준보다 작으면 g1, 크면 g2에 추가한다. 각각의 리스트에서 리스트 길이가 1이 될때까지 실행하므로 g1(기준 값 보다 작은 리스트)..

탐색과 정렬 순차탐색 / O(n) 문제: 리스트에 찾는 값이 여러 개 있더라도 찾는 값의 모든 위치를 리스트로 돌려주는 탐색 알고리즘을 만들어라. 리스트에 없다면 빈 리스트인 [ ]를 돌려준다. 쉽다고 생각하고 들이댔으나 현재 result로 보이는 값을 처음에 전부 lst로 만들었더니 어떤 예를 들던 빈값이 나왔다. if문에서의 lst[i]값이 없어서 조건을 만족시키지 못하고, 그래서 그냥 빈 리스트의 값을 리턴값으로 줬던 것 같다. 문제: 학생 번호와 이름이 리스트로 주어졌을 때 학생 번호를 입력하면 학생 번호에 해당하는 이름을 순차 탐색으로 찾아 돌려주는 함수를 만들어라 개인적으로 맞추고 꽤 기분 좋았던 문제다. 3개의 정보를 받아서 만든 함수는 처음이라 맞나 싶었는데 결과가 정확하게 나오는 걸 보고..