Over the limit

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

문제 설명 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다. 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요. 제한 조건 number는 1자리 이상, 1,000,000자리 이하인 숫자입니다. k는 1 이상 number의 자릿수 미만인 자연수입니다. 입출력 예 number k return "1924" 2 "94" ..

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 = ..

문제 설명 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요. 제한사항 numbers는 길이 1 이상 7 이하인 문자열입니다. numbers는 0~9까지 숫자만으로 이루어져 있습니다. "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다. 입출력 예 numbersreturn "17" 3 "011" 2 입출력 예 설명 예제 #1 [1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다. 예제 #2 [0, 1, 1]으로는 소수 [11, 1..

알고리즘 문제를 풀다보면 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)..