ITeus

이번 포스팅은 동적계획법을 이용하는 정수 삼각형 문제입니다. programmers.co.kr/learn/courses/30/lessons/43105?language=python3 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 이번 문제는 이진트리와 유사해 보이는 피라미드 형식의 Data가 주어질때 오직 좌하 or 우하 로만 이동하여 모든값의 합이 최대가 되게하는 문제입니다. 아래 예시를 보시죠. 하지만 해당 문제는 이진트리도, 이진 탐색트리도 아니기 때문에 위에서부터 답을 찾아내려가면 애로사항이 발생합니다.(요 경우는 욕심쟁이 방법이라고 봐야겠죠?) 예를들어서, 7 -> 8 -> 1..

이번 포스팅은 욕심쟁이 방법론 입니다. 욕심쟁이 방법론은, 작은 문제에 대한 최선의 선택을 하는 알고리즘 방법론입니다. 무슨소리인지 감이 잘 안옵니다. 아래 예시를 보겠습니다. 1달러당 무게가 1이라고 가정해 봅시다. 이때 집게사장님은 욕심쟁이 이기 때문에, 무조건 큰 돈은 우선으로 줍습니다. 그러면 5달러를 모두 담고, 남은 공간에 3달라를 담는것이 주어진 상황에서 최선의 선택이겠죠? 하지만 이렇게 하면 최적의 이익을 얻을 수는 없습니다. 욕심쟁이 방법론은 동적 프로그래밍 방법론과 유사하게 작은 소문제에 대한 해를 찾아서, 전체 문제의 해를 찾는 알고리즘 계획 방법론입니다. 동적프로그래밍 방법론은 이전 단계의 최적해를 기억해서 전체 문제의 최적해를 찾는다면 욕심쟁이 방법론은 욕심을 부려서 모든 소문제의..

이번 포스팅은 알고리즘을 설계하는 방법 중 분할정복 방법에 대한 포스팅입니다. 분할정복이란 글자 그 자체로 이해하면 편합니다. 1. 분할 : Data를 분할한다. 2. 정복 : 분할된 Data에 알고리즘을 적용한다. 3. 결합 : 정복단계의 알고리즘 결과를 취합한다. 위 3단계를 거쳐서 알고리즘이 수행되는 단계를 거치는 알고리즘 설계기법입니다. (단, 3단계 결합이 빠지는 경우도 분할정복 방법론으로 봅니다) 분할정복을 사용하는 알고리즘으로는 이진탐색, 퀵정렬, 합병정렬등을 예로 들 수 있습니다 이진 탐색을 예로 볼까요? 위 이진탐색의 내용을 다시 보겠습니다. 정복에서 알고리즘이 종료되지 않는다면 분할 단계에서 받은 부분배열에서 또다시 부분배열을 나누게 됩니다. 원하는 수준으로 작은 Data가 나오기 전까..

알고리즘의 경우 알고리즘에 들어가는 데이터의 수와 알고리즘의 구성 또는 해당 알고리즘을 실행하는 컴퓨터에 따라서 알고리즘 수행시간이 유동적으로 나타납니다. 이때, 동일한 동직을 수행하는 알고리즘 끼리 성능을 어떻게 비교할까요? 이번 포스팅은 알고리즘의 점근성능에 대한 내용입니다. 1. 점근성능 알고리즘의 점근 성능이란, 실제 수행시간은 아니지만 해당 알고리즘의 성능을 대변하는 수치를 의미합니다. 알고리즘의 점근성능을 이야기할 때 몇가지를 가정합니다. 1. 일반 사칙연산이나 비교문은 동일한 시간이 소요된다.(Data와 상관없이 상수시간이 소요된다) 2. 알고리즘의 수행시간은 최고차항의 영향이 지배적이다. 아래 예시 알고리즘을 살펴보겠습니다. #숫자를 입력받아, nxnxn 행렬을 만드는 알고리즘 입니다. d..

이번 포스팅은 Hash를 이용한 빠른 탐색 문제에대한 포스팅 입니다. programmers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 해당 문제를 살펴보면, 다수가 참가한 경기에서 한명만이 낙오가 발생하였고 해당 낙오자가 누구인지 찾는 문제입니다. 간단히 생각하면, 참가자를 Sorting하고, 완료자를 Soring해서 index순으로 비교하면 답은 찾을 수 있습니다. 하지만, 두개의 List를 Sorting하고 inde..

C언어를 해보신분이라면 아시겠지만 C언어에선 함수의 매개변수를 수정해도, 해당 매개변수의 변화가 Global 변수에 영향을 주지 않습니다. #include void f(int a, int b){ a = a + b; } int main() { int v1 = 9; int v2 = 1; f(v1, v2); printf("%d",v1); return 0; } ==> 9 위 예시를보면, v1이 a로 입력, a에 1을 더해서 a가 10으로 출력된것 같지만 그렇지 않죠. 그렇기 때문에 C언어같은 경우 Pointer라는 개념을 통해서 매개변수 자체를 바뀌게할 수 있는 방법이 있습니다. 하지만 Python을 봅시다. Python은 Pointer가 없습니다. 그러면 Python은 매개변수를 어떤방식으로 전달할까요? 아래..