ITeus

이번 문제는 탐욕법(Greedy)알고리즘을 이용한 예제입니다. https://programmers.co.kr/learn/courses/30/lessons/42860 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 탐욕법, 혹은 욕심쟁이 알고리즘은 예전 포스팅에서 간단이 다뤘지만, 주어진 국소 해에서 무조건 최선의 선택을 하여 최적의 해를 찾는 알고리즘 입니다. https://teus-kiwiee.tistory.com/81 욕심쟁이 방법론 이번 포스팅은 욕심쟁이 방법론 입니다. 욕심쟁이 방법..

지난번 포스팅에서 이어집니다. teus-kiwiee.tistory.com/60?category=924328 매운음식 성애자(Way Cool) 프로그래머스의 힙의 첫번째 문제입니다. programmers.co.kr/learn/courses/30/lessons/42626?language=python3 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들.. teus-kiwiee.tistory.com 지난번, 단순 List를 사용해서, Scovile 지수가 원하는 값이 나올때까지 반복되는 매운음식 성애자 문제를 다뤘습니다. 하지만, 이때 List를 사용해서 효옹성 테스트를 지나가지를 못했습니다. 해당 문제에서는 Heap 구조를 사용해서 빠르게 Minimum 값을..

Python을 사용하다보면, 편합니다. 정말로 편합니다. 하지만 컴퓨터과학을 전공한 입장에서, "이렇게 편해도 되나?" 싶을때가 가끔 있습니다. 편한건 좋지만, 어떻게 작동하는지를 알아야 하는 맘이 듭니다. 이번 포스팅은 Python의 함수/패키지의 Detail을 확인하는 방법에대한 포스팅입니다. 가장 먼저, Python의 기본 함수를 확인하는 방법입니다.docs.python.org/ko/3/library/index.html 파이썬 표준 라이브러리 — Python 3.9.2 문서파이썬 표준 라이브러리 파이썬 언어 레퍼런스 는 파이썬 언어의 정확한 문법과 의미를 설명하고 있지만, 이 라이브러리 레퍼런스 설명서는 파이썬과 함께 배포되는 표준 라이브러리를 설명합docs.python.org파이썬은 오픈소스 언어..

이번 포스팅은 동적계획법을 이용하는 정수 삼각형 문제입니다. 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달라를 담는것이 주어진 상황에서 최선의 선택이겠죠? 하지만 이렇게 하면 최적의 이익을 얻을 수는 없습니다. 욕심쟁이 방법론은 동적 프로그래밍 방법론과 유사하게 작은 소문제에 대한 해를 찾아서, 전체 문제의 해를 찾는 알고리즘 계획 방법론입니다. 동적프로그래밍 방법론은 이전 단계의 최적해를 기억해서 전체 문제의 최적해를 찾는다면 욕심쟁이 방법론은 욕심을 부려서 모든 소문제의..

이번 포스팅은 동적 프로그래밍 방법론입니다. 방법론의 이름을 들으면 "??? 대체 무슨 방법론이야?" 라는 생각이 듭니다. 이름을 그대로 해석하면 이해를 할수가 없습니다. 동적 프로그래밍 방법론은 동적 계획법이라고 불리며 국소해를 저장하는 Table을 구축하고, 국소해를 저장/사용하는 알고리즘 방법론을 의미합니다. 아래 피보나치 수열을 구하는 방법을 보겠습니다. (너무 유명한 예제이지만, 이것만큼 숙련된 조교도 없습니다) #분할정복 방법을 사용한 피보나치수열을 구하는 함수 def fib_div(n): if n == 1: return 1 elif n == 0: return 0 result = fib_div(n-1) + fib_div(n-2) return result #동적 프로그래밍 방법을 사용한 피보나치..