알고리즘 문제풀이

틀린 부분 : 연산 횟수를 더 줄일 수 있었는데 그렇지 못했음.틀린 이유 : 소수를 구하는 방식에 이런게 있는줄 미처 생각 못했다...

틀린 부분 : 특정 자리수와 그 다음 자리수를 비교만 하고 첫째 자리 수를 비교하지 않았다.틀린 이유 : i와 i+1을 비교하게 되면 마지막엔 i와 0번째 자리를 비교해야 하는걸 깜빡했다 ㅎㅎ다음 자리수와 같지 않다는걸 가정한다면 굳이 빼기를 해주지 않아도 되겠다...

치팅시트 ^_^

기발한 방법을 기록해둠

이진탐색보다 if ~ in ~으로 포함 여부만 확인하는것이 더 효율적일수도 있다. (단, 배열을 집합화 했을때에만...) 참고자료

틀린 부분 : 전체 반복문을 돌리려고 했으나, 재귀함수를 이용하면 훨씬 간단하다.틀린 이유 : 2, 3, 1 +2와 -2 그 다음 인덱스에서 +3 -3 이렇게 두 경우의 수를 계속 가지치기 해나가면 되는데 이는 재귀함수로 표현할 수 있다.

문제 링크

틀린 부분 : if price > p틀린 이유 : 문제 이해를 잘못함;; 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.\-> 가격이 떨어졌다면 가격이 떨어진 지점까지의 거리를 구해야함.deque 참고자료문제 링크

스택의 아주 좋은 예시 문제라서 기록해둔다!1\. 닫는 괄호는 반드시 열린 괄호 다음에 나와야하고, 2\. 등장한 열린 괄호 갯수보다 닫힌 괄호가 많아선 안된다.즉 열린 괄호를 스택에 쌓아두고 닫힌 괄호가 나올때마다 스택에서 뽑아내면서 조건을 확인해봐야 한다.

각 장르 별 재생 수 총합을 담은 딕셔너리 1개, 각 장르 별 인덱스, 재생 수 를 리스트로 담은 딕셔너리 1개, 총 두 개의 딕셔너리를 구성해야함.딕셔너리에서 value를 이용한 정렬, 여러 리스트 간 특정 인덱스(1)를 이용한 정렬은 sorted 함수와 lambda

손으로 직접 수열을 적어가며 규칙을 찾는것이 포인트이다.편의상 거리의 제곱근이 1.5보다 작으면 1.4로, 1.5보다 크면 1.6으로 적었다.거리의 제곱근이 정수면 횟수는 2n-1.거리의 제곱근의 소수부가 0.5보다 작으면 2 X (거리의 제곱근의 정수부)거리의 제곱근

머리쓰지말고 때로는 단순한 생각이 답일때가 있다... 규칙 찾아보려다가 공책만 다 썼다...문제 링크

유클리드 호제법을 이용한다...두 수 a와 b (a > b)가 있다고 할 때, a와 b의 최대공약수 G1은 b와 a%b(a를 b로 나눈 나머지)의 최대공약수 G2와 같다. 반복해서 진행할때 오른쪽 값이 0이 되었을때 왼쪽 값이 곧 최대공약수이다.ex) 32, 24 ->

재귀 함수를 이용해서 풀면된다. 최하단 원판을 제외하고는 모두 보조 기둥을 거치고 목표 기둥에 가므로 2번씩 움직이고, 최하단 원판은 한번만 움직이면되므로 움직이는 횟수는 2^n - 1 이다.문제 링크

완전 탐색을 하면 시간 초과가 되어서 이분 탐색을 한다.이분 탐색은 start가 end보다 더 커질때까지 진행한다.문제 링크

깊이 우선 탐색. 한 갈래를 정해서 바닥까지 내려간 후, 다시 루트 노드로 올라와 그 다음 갈래로 내려감.DFS는 스택으로 구현.인접노드를 나타내는 딕셔너리를 미리 만들어두고 진행해야만 함.

동적계획법은 재귀 함수의 단점을 보완할 수 있는 방법이다.재귀 함수는 결과를 구할때 구했던 값을 또 구하기 위해 같은 과정을 반복한다.예를들어 피보나치 함수를 생각해보자.fibo(1) = 1fibo(2) = 1이다.fibo(3) = fibo(1) + fibo(2) 이다

배열에 새로운 값이 계속 들어오는데, 최대값이나 최소값이 필요하다면 heap을 쓰는것이 좋다.heap은 최대값과 최소값을 자동으로 계속 만들어주는 자료구조이기 때문!파이썬에서 heap은 import heapq 로 사용한다.heap의 최소값은 heap의 0번째 인덱스이고

DFS는 스택, BFS는 큐를 기반해서 작성한다.DFS와 BFS는 모두 노드 간의 연결 상태를 파악할 수 있는 무언가가 필요한데, 나는 딕셔너리가 편하다.출력 양식(작은 수부터 탐험하는 양식)을 맞추기 위해서는 DFS에서는 딕셔너리의 value를 reverse sort

분할 정복, 재귀 함수를 이용하여 푸는 문제색종이 한 섹션 안에 있는 모든 요소가 같지 않으면 4분할 해서 스스로를 다시 호출함.이때 갈라진 4개의 함수에 매개변수를 어떻게 넣어야할지 잘 생각해야함!색종이 한 섹션 안에 있는 모든 요소가 같아지면 바로 return 해주

5C2 같은 조합의 모든 경우의 수를 나열하는 문제인데 이게 결국 DFS 문제였다...!4C2라고 할때 아래와 같은 수열을 출력해야 한다.1 21 31 42 32 43 4제시해주는 횟수만큼 for문이 돌아야하는데 이는 재귀적 표현이다.github commit문제 링크

재귀함수의 개념은 이해가 되고, 문제풀이 아이디어도 떠오르는데 코드로 표현하는게 어렵다...반복 안에 반복을 구현할때 재귀 함수를 쓰는데, 안쪽 반복을 재귀적으로 표현해야 한다.github commit문제 링크

재귀 함수를 쓰는 문제이다.하지만 최대 300개의 계단이 있을수 있다고하니, 재귀 함수를 썼을때 너무 깊게 들어가서 시간초과가 난다.이럴때 동적 계획법을 적용시킨다.github commit문제 링크

두 원, 두 원의 중심과 임의의 점 사이의 거리 이렇게 주어졌을때 두 원 사이에 접점이 생길 수 있는지를 알아보는 문제이다.원을 그려보면서 접점이 무한, 0개, 1개, 2개인 경우를 생각해본다.접점이 하나라고 가정해보면...그 경우의 수는 외접할때와 내접할때가 있다.이