이니의 공부일지

➡️ 도서 리뷰에 앞서... 안녕하세요!! 개발 도서 리뷰는 처음이네요ㅎㅎ 이 도서로 말할 것 같으면, 코딩테스트를 준비하시는 많은 분들께 추천하는 도서입니다!! 하지만, 너무 초급자에게는 어려울 수 있어요ㅜㅜ 내가 코딩테스트 문제를 어느정도 풀 수는 있는데, 어떤 문제의 어떤 조건을 유의깊게 살펴봐야 하며 이 문제를 풀 때는 어떤 방법이 가장 좋을지 감이 안잡히시는 분들에게 추천합니다!! 저도 직접 읽어보고 문제를 풀어보면서 실력을 키울 수 있었고, 감도 잡을 수 있었습니다ㅎㅎ ➡️ 도서를 읽기 이전의 내 실력 저는 (아마도) 비전공자에 가까울 것입니다. Python을 독학으로 배웠으며, 자료구조와 알고리즘 또한 코딩테스트라는 것을 알게 된 후로 백준에서 하나씩 풀면서 알게되었으니까요... 게다가 자료..

냅색 알고리즘이란? 한 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제 냅색 알고리즘을 나누는 기준 담을 수 있는 물건이 나뉠 수 있는가, 없는가? 담을 수 있는 물건이 나누어 질 때 분할가능 배낭문제(Fractional Knapsack Problem) 담을 수 있는 물건이 나누어질 수 없을 때 0-1 배낭 문제(0-1 Knapsack Problem) 냅색 알고리즘 예시 가방에 20kg까지 담을 수 있습니다. 현재 3가지 물건을 가지고 있을 때, 가치를 최대로 가지려면 어떤 물건들을 담아야 하나요? A : 가치 10, 무게 14kg B : 가치 7, 무게 10kg C : 가치 8, 무게 10kg..

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

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

버블 정렬(거품 정렬) 거품 정렬은 가장 단순한 정렬 알고리즘이다. 아이디어는 다음과 같다. 첫번째와 두번째 값을 비교하고, 두번째와 세번째 값을 비교하고, ... n-1번째와 n번째 값을 비교합니다. 이 과정에서 순서가 맞지 않은 값을 서로 교환해준다. 이런 절차를 정렬이 될 때 까지 반복한다. 코드를 작성하는 것은 어렵지 않지만, 상당히 비효율적인 알고리즘이기 때문에 성능이 다른 알고리즘에 비해 좋지 않다는 단점이 있다. 버블 정렬의 시간복잡도는 O(N2) 이다. 버블 정렬을 구현한 코드는 다음과 같다. n = int(input()) m = list(map(int, input().split())) for i in range(n): cnt = 0 for j in range(1, n): if m[j] >..

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

문제 양의 정수 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 # 최소 공배수 구하..

문제 1937년 Collatz란 사람에 의해 제기된 이 추측은, 주어진 수가 1이 될때까지 다음 작업을 반복하면, 모든 수를 1로 만들 수 있다는 추측입니다. 작업은 다음과 같습니다. 1-1. 입력된 수가 짝수라면 2로 나눕니다. 1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다. 2. 결과로 나온 수에 같은 작업을 1이 될 때까지 반복합니다. 예를 들어, 입력된 수가 6이라면 6→3→10→5→16→8→4→2→1 이 되어 총 8번 만에 1이 됩니다. 위 작업을 몇 번이나 반복해야하는지 반환하는 함수, solution을 완성해 주세요. 단, 작업을 500번을 반복해도 1이 되지 않는다면 –1을 반환해 주세요. 제한 사항 입력된 수, num은 1 이상 8000000 미만인 정수입니다. 입출력 예 n ..

문제 정수를 담고 있는 배열 arr의 평균값을 return하는 함수, solution을 완성해보세요. 제한 사항 · arr은 길이 1 이상, 100 이하인 배열입니다. · arr의 원소는 -10,000 이상 10,000 이하인 정수입니다. 입출력 예 arr return [1, 2, 3, 4] 2.5 [5, 5] 5 ▶ my code def solution(arr): answer = 0 for i in arr: answer += i answer /= len(arr) return answer ▶ 아이디어 각각의 배열의 원소를 더하고, 그것을 배열의 길이로 나누어 주었다.