이니의 공부일지

백트래킹이란? 현재 상태에서 가능한 모든 경로를 따라 들어가 탐색하다, 원하는 값과 불일치하는 부분이 발생하면 더 이상 탐색을 진행하지 않고 전 단계로 올라가는(방금 왔던 길을 되짚어가는) 알고리즘 백트래킹과 DFS의 차이 백트래킹 불필요한 탐색을 하지 않는다. DFS 모든 경우의 수를 탐색한다. 백트래킹 구현 완전탐색 기법인 BFS 와 DFS 로 모두 구현 가능 백트래킹의 특성(전 단계로 다시 올라가는) 때문에 DFS의 구현이 더 편하다. 한정 조건 이 가장 중요하다. 모든 경우의 수에서 한정 조건 을 만족하는 경우를 탐색 대표 문제 15649번: N과 M (1) 문제 자연수 N과 M이 주어질 때, 숫자 1부터 N까지 중복 없는 M개의 요소를 가진 수열을 구하자 💡 고려 사항 배열의 길이가 M을 넘지 ..

트리의 정의는 노드끼리 전부 연결되어 있으면서 사이클이 존재하지 않는 그래프이다. 트리는 두 지점의 연결 관계로 구성되어 있는데, 계층관계가 존재한다는 것이 특징이다. 우리는 하나의 연결 관계에서 위쪽에 있는 점을 부모라고 부르며, 아래쪽에 있는 점을 자식이라고 부른다. 그 외에도 추가적인 용어들은 다음과 같다. 노드: 각 지점을 의미합니다. 정점이라 부르기도 한다. 간선: 두 노드를 연결하는 선을 의미합니다. 에지라고 부르기도 한다. 루트 노드: 트리에서 맨 꼭대기를 의미한다. 부모, 자식: 트리에서 연결된 두 노드의 관계를 의미하는데, 더 위쪽에 있는 노드를 부모 노드, 아래쪽에 있는 노드를 자식 노드라고 부른다. 차수: 특정 노드를 기준으로, 자식의 수가 얼마나 되는지 의미한다. 깊이: 루트 노드와..

이진탐색 이진탐색은, 찾아야하는 수의 범위 중 가운데의 값과 찾고자 하는 값을 비교하여 대소관계에 따라 특정 구간으로 이동하는 것을 반복하는 것이다. 이진탐색을 사용하는 이유는 순차탐색보다 더 빠르기 때문이다. 실제 이진탐색의 시간복잡도는 O(logN)이다. 루프를 한 번 돌때 마다, 우리가 다루는 구간의 길이는 반으로 감소하고, 구간의 길이가 1이 될 때 까지 계속 반복해서 탐색하는 것을 볼 수 있다. 즉, 루프는 약 log2​N 번 돌게 된다. 루프 내부 연산의 시간 복잡도는 O(1)이기 때문에, 자연스럽게 시간복잡도는 O(1∗logN)=O(logN)이 되는 것을 볼 수 있다. O(N)과 O(logN)은 정말 큰 차이를 보인다. 만약, N이 4,294,967,296이라면, O(logN)의 시간복잡도를..

인덴트(들여쓰기) python의 대표적인 특징으로써 공백 4칸을 원칙으로 한다. 네이밍 컨벤션 python의 변수명 네이밍 컨벤션은 자바와 달리, 각 언어를 밑줄( _ )로 구분하여 표기하는 스네이크 케이스를 따른다. (스네이크 케이스는 일반적으로 모두 소문자로 표기하지만, 경우에 따라 시작 문자는 대문자로도 표기한다.) 타입 힌트 python은 동적 타이핑 언어이지만, 타입을 지정할 수 있는 타입 힌트 기능이 존재한다. ex) def fn(a: int) -> bool: 하지만, 동적으로 할당될 수 있으므로, 문자열에 정수를 할당하는 등의 사용은 지양해야 한다. 리스트 컴프리헨션 python은 map, filter와 같은 함수형 기능을 지원하며, 람다 표현식도 지원한다. ex) >>> list(map(l..

문제 자연수 n을 뒤집어 각 자리 숫자를 원소로 가지는 배열 형태로 리턴해주세요. 예를들어 n이 12345이면 [5,4,3,2,1]을 리턴합니다. 제한 조건 n은 10,000,000,000이하인 자연수입니다. 입출력 예 n return 12345 [5, 4, 3, 2, 1] ▶ my code def solution(n): answer = str(n)[::-1] ans = [] for i in answer: ans.append(int(i)) return ans ▶ 아이디어 문자열 뒤에 [::-1]을 붙여주면, 반대로 배열해줍니다.

문제 함수 solution은 정수 n을 매개변수로 입력받습니다. n의 각 자릿수를 큰것부터 작은 순으로 정렬한 새로운 정수를 리턴해주세요. 예를들어 n이 118372면 873211을 리턴하면 됩니다. 제한 조건 n은 1이상 8000000000 이하인 자연수입니다. 입출력 예 n return 118372 873211 ▶ my code def solution(n): answer = str(n) answer = ''.join(sorted(answer, reverse=True)) return int(answer) ▶ 아이디어 str은 a.sort()를 사용할 수 없다. 그러나 sorted만을 사용하기에는 결과 값이 '8', '7', '3', '2', '1', '1' 이 될 것이다. 그렇기 때문에, ''.join..

문제 임의의 양의 정수 n에 대해, n이 어떤 양의 정수 x의 제곱인지 아닌지 판단하려 합니다. n이 양의 정수 x의 제곱이라면 x+1의 제곱을 리턴하고, n이 양의 정수 x의 제곱이 아니라면 -1을 리턴하는 함수를 완성하세요. 제한 사항 n은 1이상, 50000000000000 이하인 양의 정수입니다. 입출력 예 n return 121 144 3 -1 입출력 예#1 121은 양의 정수 11의 제곱이므로, (11+1)를 제곱한 144를 리턴합니다. 입출력 예#2 3은 양의 정수의 제곱이 아니므로, -1을 리턴합니다. ▶ my code def solution(n): num = n**(1/2) if num == int(num): return (num+1)**2 else: return -1 ▶ my code ..

문제 정수를 저장한 배열, arr 에서 가장 작은 수를 제거한 배열을 리턴하는 함수, solution을 완성해주세요. 단, 리턴하려는 배열이 빈 배열인 경우엔 배열에 -1을 채워 리턴하세요. 예를들어 arr이 [4,3,2,1]인 경우는 [4,3,2]를 리턴 하고, [10]면 [-1]을 리턴 합니다. 제한 조건 · arr은 길이 1 이상인 배열입니다. · 인덱스 i, j에 대해 i ≠ j이면 arr[i] ≠ arr[j] 입니다. 입출력 예 arr return [4, 3, 2, 1] [4, 3, 2] [10] [-1] ▶ my code def solution(arr): if len(arr) == 1: return [-1] else: arr.remove(min(arr)) return arr ▶ 아이디어 rem..

문제 양의 정수 x가 하샤드 수이려면 x의 자릿수의 합으로 x가 나누어져야 합니다. 예를 들어 18의 자릿수 합은 1+8=9이고, 18은 9로 나누어 떨어지므로 18은 하샤드 수입니다. 자연수 x를 입력받아 x가 하샤드 수인지 아닌지 검사하는 함수, solution을 완성해주세요. 제한 조건 x는 1 이상, 10000 이하인 정수입니다. 입출력 예 arr return 10 true 12 true 11 false 13 false 입출력 예 #1 10의 모든 자릿수의 합은 1입니다. 10은 1로 나누어 떨어지므로 10은 하샤드 수입니다. 입출력 예 #2 12의 모든 자릿수의 합은 3입니다. 12는 3으로 나누어 떨어지므로 12는 하샤드 수입니다. 입출력 예 #3 11의 모든 자릿수의 합은 2..

문제 두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다. 제한 사항 두 수는 1이상 1000000이하의 자연수입니다. 입출력 예 n m return 3 12 [3, 12] 2 5 [1, 10] ▶ my code import math def solution(n, m): # 최대 공약수 구하기 for i in range(min(n, m), 0, -1): if (n % i == 0) and (m % i == 0): a = i break # 최소 공배수 구하..