Over the limit

Iterator 란? Iterator란 자바의 인터페이스이다. 기능은 다양한 집합체(Map, List, Set)으로부터 정보를 얻어내는 것이다. Iterator 객체는 컬렉션 개체의 iterator() 메서드를 호출하여 얻어올 수 있다. 사용가능 객체 ArrayList arr = new ArrayList(); Vector vec = new Vector(); Iterator 객체 얻기 Iterator it0 = arr.iterator(); Iterator it1 = vec.iterator(); +) while문을 통해 객체 얻기 (하단의 Iterator 메소드 이용) while(it0.hasNext()){ String st=(String)it0.next(); } for문을 통해 객체 얻기 for(Membe..

시간 복잡도란? 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미한다. 문제를 풀다보면 실행시간안에 알고리즘이 마치지 않았다고 정답으로 체크하지 않는 경우를 볼 수 있다. 따라서 시간 복잡도를 잘 체크하여 문제를 풀어야 한다. 빅오 표기법 원하는 답이 나오지 않는다면 최대 얼마만큼의 시간이 걸릴까를 측정하기 위해 사용하는 것이 빅오 표기법이다. (Big-O) 입력데이터(n)에 따라 어떤 결과가 나올지, 각각의 함수를 통해서 알 수 있다. 시간 복잡도의 대표적인 종류 1 : 입력자료의 수에 관계없이 일정한 실행시간 갖음 Log N : 입력자료의 수에 따라 시간이 조금씩 증가함 - 주로 큰 문제를 일정한 크기를 갖는 작은 문제로 쪼갤 때 나타나는 유형 ex)이진 탐색 N : 입력 자료의 수에 따라 ..

DFS(Depth First Search) 스택을 사용하며, 인접 행렬 또는 인접 리스트로 구현한다. 깊이 우선 탐색 방법으로서, 정점을 탐색하다가 어느 정점과 그 이웃들까지 모두 방문한 상태라면 돌아와서 다른 경로에 뻗어있는 정점을 방문하고 이를 반복하는 방법이다. 모든 노드를 방문하고자 할 때 (ex. 완전 탐색 알고리즘) dfs를 사용하는 것이 좋다. 자기 자신을 호출하는 순환 알고리즘의 형태 트리 순회(전위, 중위, 후위) 는 모두 DFS의 한 종류 그래프 탐색의 경우 방문한 노드를 반드시 표시 (안하면 무한루프 빠질 위험 있음) DFS 인접 리스트 구현 : 연결 리스트에 정점과 간선을 넣어 인접 리스트를 만들자 LinkedList[] adjList = new LinkedList[n+1]; for..

ArrayList란? ArrayList란 크기가 가변적으로 변하는 선형리스트 이다. 일반적으로 생각하는 배열의 인덱스 특징을 가졌으면서도, 크기가 유동적으로 변하는 특징을 가졌다. ArrayList 선언 ArrayList = new ArrayList(); ArrayList members = new ArrayList(); //Student 객체만 사용가능 ArrayList num = new ArrayList(); //int타입만 사용가능 ArrayList num2 = new ArrayList(); //타입 파라미터 생략 가능 ArrayList num3 = new ArrayList(10); //초기용량 지정 ArrayList list2 = new ArrayList(Arrays.asList(1,2,3)); /..

클래스, 상속, 접근제한, 함수 중복을 활용하고객체지향의 특성을 알고 제대로 적용하는 것을 주안으로 작성한 재고 관리 프로그램이다.       #include#includeusing namespace std;void f(char c = ' ', int line = 1); //함수 중복void f(char c, int line) { //함수 중복 for (int i = 0; i amount = amount; } string getName() { return name; } bool getempty() { return empty; }};class small : public Size{ //Size 클래스와 상속관계public: small() { this->name = "small"; this->amount = ..

알고리즘 문제를 풀다보면 Hash(해시) 카테고리를 보기 마련이다. 또한 해시 개념은 암호학에서도 빈번히 등장한다. 여기서 해시가 무엇인지 정확히 짚고 넘어가도록 하자. 해시란? 임의의 크기를 가진 데이터를 고정된 데이터의 크기로 변환시키는 것을 말한다. 이를 이용하면 데이터를 보다 더 쉽게 다루며 검색과 저장이 아주 빠르게 진행된다. 해시함수란? 임의의 길이의 문자열을 받아서 고정 문자열로 바꾸어주는 함수이다. 이때, 함수를 구현하는 방법에 따라서 서로 다른 임의의 문자열이 같은 고정 문자열로 되기도 하며 이러한 부분을 충돌이라고 한다. (H(s1)=H(s2)) 함수에 넣고 나온 결괏값을 후에 인덱스로 사용한다. //문자열을 받아서 정수로 반환하는 해시 함수의 예제 int hash(const char*..

스택 (Stack) 스택은 LIFO, Last-In-First-Out 의 후입 선출 구조로 이루어져 있다. 오직 top을 통해서만 접근이 가능하며 push를 통해서 삽입, pop을 통해 삭제를 할 수 있다. 활용예시 웹 브라우저 방문기록 (뒤로가기) 실행 취소 (Ctrl+Z) 후위 표기법 수식의 괄호 검사 큐 (Queue) 큐는 FIFO, First-In-First-Out 선입 선출 구조로 이루어져 있다. 스택은 한 곳을 통해서만 삽입 및 삭제가 이루어지는 점에 반하여 큐는 한 쪽에서는 삽입, 다른 쪽에서는 삭제가 이루어지며, 삭제(dnQueue)만 수행되는 곳을 프론트(front)/삽입(enQueue)만 수행되는 곳을 리어(rear)라고 한다. 활용예시 프린터의 인쇄 대기열 프로세스 관리 BFS 콜센터..

AES 복호화 알고리즘은 아래와 같이 구성되어 있다. 박스안에 있는 내용은 Inverse Shift rows, Inverse Sub Bytes, Add Round Key, Inverse mix cols 순인데 마지막 박스(마지막 라운드)에서는 Inverse mix cols이 존재하지 않는다는 점을 유의하자. Ciphertext ↓ Add Round Key ↓ Inverse Shift rows ↓ Inverse Sub Bytes ↓ Add Round Key ↓ Inverse mix cols ↓ Inverse Shift rows ↓ Inverse Sub Bytes ↓ Add Round Key ↓ Inverse mix cols ↓ Inverse Shift rows ↓ Inverse Sub Bytes ↓ Add..

이진 트리 삽입을 위해서는 먼저 탐색을 수행하는 것이 필요하다. 같은 key값을 같는 노드가 없음과 동시에, 탐색에 실패한 그 위치가 새로운 노드를 삽입하는 위치가 되기 때문이다. 아래는 자연어 버전의 이진 탐색 트리 삽입 알고리즘이다. insert_node(T,z) 1.트리 T에서 z에 대한 탐색을 먼저 수행한다. 2.탐색이 실패하면 탐색이 끝난 지점에 노드 z를 삽입한다. key 탐색이 성공하면 이미 key가 트리 안에 존재하는 것이고, 탐색 키가 중복되는 것이므로 삽입이 불가능하다. 하지만 key가 트리 안에 없다면 어디선가 탐색이 실패로 끝날 것이다. 그 위치가 key가 있어야 할 곳이 된다. 매개 변수 root는 이진 탐색 트리의 루트 노드를 가리킨다. 삽입 함수에서는 루트 노드 포인터가 변경되..

힙(Heap)정의, 힙 추가 연산 (tistory.com) 저번 힙 정의에 이어서, 이번엔 힙 응용에 관해 다뤄본다. Heap Application : Heap Sort, Prioirty Queue 우선순위 큐란? 노드 반환(dequeue) 시에 큐에서 우선 순위가 가장 높거나 혹은 가장 낮은 노드를 먼저 반환 하는 큐 큐 개념만 알고나서 덥석 이 문제 풀었다가 큐의 응용 버전인 Priority Queue인 것을 알고 당황했던 문제 추가...! [C++] 프로그래머스 - 디스크 컨트롤러 / 우선순위 큐 (tistory.com) 힙 정렬이란? 순서 없이 배열된 데이터들을 값에 따라 순서대로 재배열하는 것 -오름차순(ascending)정렬 : 값이 증가하는 순서대로 배열하는 것 (ex. 10->20->30)..