akaSonny

위의 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 (7) 부터 시작하여 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램 작성. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 오른쪽에 있는 것 중 하나만 선택 가능. 삼각형의 크기는 1 이상 500이하, 각 정수들의 범위는 0 이상 9999 이하 입력 조건 : 첫째 줄에 삼각형의 크기 n이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. 출력 조건 : 합이 최대가 되는 경로에 있는 수의 합 출력 이 부분 챕터를 푸는 중이라 그런지 문제 보자마자 푸는 방법을 깨달아서 뿌듯했당 .. ㅎㅋ 먼저, 계산한 값들을 저장할 새로운 배열을 만들어야 한..

피보나치 수열 : $a_{n+2} = a_{n+1} + a_n$, $a_1=1, a_2=1$ 1. 재귀함수 def fibo(x): if x == 1 or x == 2: return 1 return fibo(x-1) + fibo(x-2) 원래는 피보나치 수열은 이렇게 재귀함수로 표현하는게 국룰인 줄 알았다,, 그런데 이렇게 하면 시간 복잡도가 $O(2^N)$으로 N이 늘어나면 연산량이 지수적으로 늘어난다. 따라서 연산량을 줄일 수 있는 다른 방법 필요 다음 소개할 코드는 메모이제이션 (Memoization) 기법을 사용한다. 한 번 구현한 결과를 메모리 공간에 메모해두고 호출하여, 반복된 연산을 피하는 방법 2. 재귀함수2 d = [0] * 100 def fibo(x): if x == 1 or x == 2..

코딩테스트 스터디를 하면서 이번에 공부하게 된 이진 탐색에 대해 정리하려고 한다. 개념 자체는 엄청 간단하고 bisect라는 모듈이 있기 때문에 직접 구현하지 않아도 된다. 하지만 나는 몰라서 직접 구현했지.. 후후... 아래의 개념 포스팅은 책을 참고하였습니다. (책 구매 링크) 1. 순차 탐색 말 그대로 우리가 찾고자 하는 대상을 앞에서부터 하나씩 순차적으로 확인하는 방법 시간만 충분하다면 무조건! 찾을 수 있음 우리가 알고 있는 for문, count 메서드 등이 여기에 해당 시간 복잡도는 O(N) , 즉 N이 엄청 커지면 엄청 오래 걸린다는 단점 .. 2. 이진 탐색 이진 탐색을 하기 위해서는 시작점, 끝점, 중간점이 필요 → 찾으려는 대상과 중간점을 비교해가며 탐색하는 방법 중간점과 비교하기 때문..

데이터 처리할 때 datetime 모듈을 상당히 많이 쓰는데, 맨날 쓰고 까먹고 검색하고 무한 반복이라 내가 자주 쓰는 것들 정리용 포스팅 1. datetime to string : strftime 메소드 이용 (f: format) import datetime date = datetime.datetime(2021, 12, 28) date_string = date.strftime("%Y-%m-%d") date_string # 출력 : '2021-12-28' 2. string to datetime : strptime 메소드 이용 (p: parse) import datetime date = datetime.datetime.strptime('2021-12-28', '%Y-%m-%d') date # 출력 : da..