ㅇㅅㅎ

[ 접근법 ] : 재귀적 해법은 부분문제에 대한 해법을 통해 완성됩니다. 따라서 많은 경우, 단순히 f(n-1)에 대한 해답에 무언가를 더하거나, 제거하거나, 아니면 그 해답을 변경하여 f(n)을 계산해 냅니다. 아니면 데이터를 반으로 나눠 각각에 대해서 문제를 푼 뒤 이 둘을 병합하기도 합니다. 👀 상향식 접근법 : 계산하면서 아래로 내려가는 형태를 말하며 간단한 경우들에 대한 풀이법을 발견하는 것으로부터 시작합니다. 핵심은 이전에 풀었던 사례를 확장하여 다음 풀이를 찾는 것입니다. 👀 하향식 접근법 : 출력형태를 만들어놓고 회수하는 형태로 어떻게 하면 N에 대한 문제를 부분 문제로 나눌 수 있을지 생각해 봐야 합니다. 나뉜 부분문제의 경우가 서로 겹치지 않도록 주의해야 합니다. 👀 반반 접근법 : 데..

[ 객체 지향 프로그래밍 ] 프로그램을 수많은 '객체(object)'라는 기본 단위로 나누고 이들의 상호작용으로 프로그램을 제작합니다. 여기서 객체란 하나의 역할을 수행하는 '메서드와 변수(데이터)'의 묶음입니다. [ 객체 지향 프로그래밍 요소 ] 👀 캡슐화 → 정보 은닉 : 변수와 함수를 하나의 단위로 묶는 것을 의미합니다. 👀 상속 → 재사용+확장 : 자식 클래스가 부모 클래스의 특성과 기능을 그대로 물려받는 것을 의미합니다. 👀 다형성 → 사용편의 : 하나의 변수, 또는 함수가 상황에 따라 다른 의미로 해석될 수 있는 것을 의미합니다. 오버라이딩(Overriding) : 부모 클래스에 정의되어 있는 메서드를 자식클래스에서 재정의하여 사용하는 것입니다. 오버로딩(Overloading) : 같은 이름을..

[ 소수 ] 소수는 약수가 1과 자기 자신뿐인 자연수입니다. 모든 자연수는 소수의 곱으로 나타낼 수 있다는 규칙이 있습니다. 👀 가분성(divisibility) 어떤 수 x로 y를 나눌 수 있으려면 x를 소수의 곱으로 분할하였을 때 나열되는 모든 소수는 y를 소수의 곱으로 분할하였을 때 나열되는 모든 소수들의 부분집합이어야 합니다. 즉, x/y를 만족하려면 모든 i에 대해서 j_i 2){ return false; } int sqrt = (int) Math.sqrt(n); for(int i=2; i

[ 손으로 비트 조작해보기 ] 비트 조작에 익숙하지 않다면 손으로 다음의 연습문제들을 풀어보는 것이 좋습니다. 비트는 1과 0만을 가지는 2진수로 +, -와 *의 경우 똑같이 연산하시면 됩니다. 연산자 기능 + 더하기 연산 - 뺴기 연산 * 곱셈 연산 & 비교하는 두 비트가 1이면 1, 그 외의 모든 경우는 0인 연산 (AND) | 비교하는 두 비트가 0이면 0, 그 외의 모든 경우는 1인 연산 (OR) ^ 비교하는 비트 같으면 0 다르면 1인 연산 (XOR) ~ 모든 비트 반전하는 연산(NOT) >> 비트 열을 오른쪽으로 이동 연산 2 1101 ^ (~1101) 1000 - 0010 1011 ^ 0101 1101 & (~0 >연산과 같습니다. ⭐ Java Code int repeatedArithmeti..

[ 트리의 종류 ] 👀 트리 : 노드로 이루어진 자료구조입니다. 트리를 재귀적으로 설명하면 다음과 같습니다. 하나의 루트 노드를 갖습니다. → 사실 그래프 이론에서는 하나의 루트 노드를 가질 필요는 없습니다. 루트 노드는 0개 이상의 자식 노드를 갖고 있습니다. 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고 이는 반복적으로 정의됩니다. ⭐ Node class Node{ public String name; public Node[] childern; } ⭐ Tree class Tree{ public Node root; } 👀 이진트리(binary tree) : 각 노드가 최대 2개의 자식을 갖는 트리 👀 이진 탐색 트리(binary search tree) : 모든 노드가 다음과 같은 특정 순서를 따르는..

[ 스택 구현하기 ] 👀 스택 : 제한적으로 접근할 수 있는 나열 구조로 LIFO(Last-In-First-Out)에 따라 자료를 배열합니다. 재귀 알고리즘을 사용할 때 유용하게 사용됩니다. ⭐ LIFO : 가장 최근에 추가한 항목이 가장 먼저 제거될 항목 ⭐ 재귀 알고리즘을 사용할 때 임시 데이터를 스택에 넣어놓고 재귀 함수 완료 후 스택에 넣어 두었던 임시 데이터를 빼는 형식으로 주로 사용됩니다. 👀 Java로 구현 public class MyStack{ private static class StackNode{ private T data; private StackNode next; public StackNode(T data){ this.data = data; } } private StackNode t..

👀 연결리스트 : 차례로 연결된 노드를 표현해주는 자료구조 장점 : 리스트의 시작 지점에서 아이템을 추가하거나 삭제하는 연산을 상수 시간에 할 수 있습니다. 단점 : 배열처럼 특정 인덱스를 상수 시간에 접근할 수 없습니다. [ 연결리스트 만들기 ] 아래의 코드에선 LinkedList 자료구조를 사용하지 않았습니다. 그리고 연결리스트에 접근할 때 head 노드의 주소를 참조하는 방법을 사용했기 때문에 여러 객체들이 동시에 연결리스트를 참조하는 도중에 head가 바뀌면 오류가 발생할 수 있습니다. ⭐ Java class Node { Node next = null; int data; public Node(int d){ data = d; } void appendToTail(int d){ Node end = ne..

[ 해시 테이블 ] : 효율적인 탐색을 위한 자료구조로서 키(key)를 값(value)에 대응 👀 구현 방식 1. 연결리스트와 해시코드함수 : 탐색 시간 O(1) 더보기 ✔️ 키와 값 삽입법 키의 해시 코드 계산 키의 자료형은 보통 int 혹은 long인데, 키의 개수는 무한한데 반해 int의 개수는 유한하기 때문에 서로 다른 두 개의 키가 같은 해시 코드를 가리킬 수 있습니다. 해시 코드를 이용하여 배열의 인덱스 계산 서로 다른 두 개의 해시 코드가 같은 인덱스를 가리킬 수도 있습니다. 키와 값을 해당 인덱스에 저장 배열의 각 인덱스에는 키와 값으로 이루어진 연결리스트가 존재합니다. 충돌에 대비해서 반드시 연결리스트를 이용해야합니다. ⭐ 충돌 : 서로 다른 두 개의 키가 같은 해시 코드를 가리키거나 서..

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다. ✔ 프로세서 구조 컴퓨터 구조의 발전 인텔 8086 (1981): 5 MHz (IBM PC에 처음 사용됨) 인텔 80486 (1989): 25 MHz (숫자를 상표로 사용할 수 없다는 법원 판결 때문에 i486이 됨) 펜티엄 (1993): 66 MHz 펜티엄 4 (2000): 1.5 GHz (약 30단계의 깊은 파이프라인) 펜티엄 D (2005): 3.2 GHz (이후 클럭 속도의 증가가 멈춤) 쿼드코어 제온 (2008): 3 GHz (하나의 칩의 코어 수가 성능의 주요 요소) 병렬 알고리즘의 문제점 프로세서는 계산할 데이터를 필요로 하나 SRAM은 4개보다 많은 메모리 요청을 병렬적으로 처리 불가합니다. ..

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다. ✔ 정의 P : 다항 시간에 풀 수 있는 모든 문제들의 집합 예시) 음수 가중치 사이클 탐지 ∈ P EXP : 지수 시간에 풀 수 있는 모든 문제들의 집합. 예시) n×n 체스 ∈ EXP 그러나 ∈/(속하지 않음) P → n×n 체스 주어진 보드 배열에서 누가 이기는가? R : 유한 시간에 풀 수 있는 모든 문제들의 집합 예시) 테트리스 ∈ EXP 그러나 ∈ P 인지는 모름 → 주어진 보드와 조각들에서 살아남기 정지 문제 : 컴퓨터 프로그램이 주어졌을 때, 그것이 한 번이라도 정지하는가? 계산 불가능 (∈ / R):이것을 푸는 알고리즘은 없다 (모든 입력값에 대해 유한 시간에 맞게 푸는 것) 결정 문제: 답..