Step-by-Step

처음에는 ArrayList를 이용해서 배열을 넣고, 완전 탐색을 이용하였다 하지만 시간 초과 + 정답 오류 가 계속 반복되어 나타나는 걸 보고 구글링을 시도하였다.....(최후의 수단) 제한 조건을 자세히 보면 number의 값이 1,000,000자리까지 나올 수 있는데, 완전 탐색을 이용하면 최악의 경우에 1,000,000C999,999의 경우의 수가 나올 수 있기 때문에 절대 사용 금지이다 풀이 방법은 다음과 같다 class Solution { public String solution(String number, int k) { StringBuilder sb = new StringBuilder(); int idx = 0; int max = 0; for(int i=0; i

큐(Queue) FIFO(First In First Out) 특성을 가진 자료구조 데이터가 들어오는 위치는 가장 뒤로 후단(Rear or Back)이라 하고, 데이터가 나가는 위치는 가장 앞인 전단(Front)이다 스택에서는 삽입, 삭제 모두 top을 통해서 이루어지는데, 큐에서는 front에서 삭제, rear에서 삽입을 담당한다 큐의 추상자료형(Abstract Data Type; ADT) - 입력 : 엔큐(Enqueue) - 출력 : 디큐(Dequeue) ※ 간혹 스택과 동일하게 Push,Pop을 쓰기도 하고, Push,Pull을 사용하기도 한다 큐의 종류 1. 선형 큐 - 1차원 배열을 정의한다 - 삽입, 삭제를 위한 변수인 front와 rear을 만든다 - front와 rear의 초기값은 -1이다 ..

순환(Recursion) 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법 가장 대표적인 예시로 정수의 팩토리얼을 구현한 함수가 있다 int factorial(int n) { if(n

스택(Stack) LIFO(Last In First Out) 특성을 가진 자료구조 메모리에 들어오는 데이터 위치가 메모리 말단(Top Pointer)이고 쓰기 위해 내보내는 데이터 역시 메모리 말단을 거친다 스택의 추상자료형(Abstract Data Type; ADT) - 입력연산 : 푸시(Push) - 출력연산 : 팝(Pop) - 조회연산 : 피크(Peek) ※ 조회연산은 탑 포인터가 가리키는 데이터를 조회만 할 뿐 탑의 순번(인덱스)은 변화시키지 않는다 스택의 Push, Pop 과정 1. Push - 먼저 Top Pointer의 값을 증가 시킨 후, 증가시킨 Top의 위치에 데이터를 넣는다 2. Pop - 먼저 데이터를 꺼낼 Top의 위치를 다른 변수(인덱스)에 별도로 저장한 후, Top의 위치를 감..

데이터(data) 프로그램에서 데이터(data)는 처리의 대상이 되는 모든 것 데이터 타입(data type) 데이터의 집합과 데이터에 적용할 수 있는 연산의 집합 즉 데이터 타입 = 객체(Object) + 객체 간의 연산(Operation) 이 된다 ※ 예로 C언어에는 int라는 데이터 타입을 제공하는데, int 데이터 타입에서 데이터는 "정수의 집합"이고, 연산은 "정수 간 연산"을 의미한다 추상 데이터 타입(abstract data type; ADT) 새로운 데이터 타입을 추상적,수학적으로 정의한 것 자료 자체의 형태와 그 자료에 관계된 연산들을 "수학적으로만" 정의한 것 데이터 타입의 정의가 그 데이터 타입의 구현으로부터 분리된 데이터 타입 ※ 즉 추상 데이터 타입에서 데이터나 연산이 무엇(wha..

그동안 까먹었던 내용을 복습도 하고, 기본을 다질 겸책을 펼치게 되었다 공부한 내용들을 잊지 않게 블로그에 차근차근 정리하기로 했다! 자료구조(Data Structure) 프로그램에서 자료들을 정리하는 여러가지 구조들 프로그래밍에서 데이터를 구조적으로 표현하는 방식과 이를 구현하는 데 필요한 알고리즘에 대해 논하는 기초 이론 ※ 컴퓨터의 대부분 프로그램에서 자료(data)를 처리하고 있고, 자료들은 자료 구조(data structure)를 사용하여 표현되고 저장된다 알고리즘(Algorithm) 컴퓨터로 문제를 해결하기 위한 단계적인 절차나 방법 문제와 컴퓨터가 주어진 상태에서 문제를 해결하는 방법을 정밀하게 장치가 이해할 수 있는 언어로 기술한 것 좁은 의미로 자료구조 내에서 기본적인 연산을 하기 위한 ..

국내에서 디즈니 플러스(Disney+)가 공식 서비스를 시작하였다. 디즈니 플러스는 2019년에 디즈니가 출시한 가입형 온라인 스트리밍 OTT 서비스로 같은 부류로 넷플릭스와 왓챠 등이 있다. 기사를 읽고 OTT에 대해 더 자세히 조사해보았다. OTT(Over The Top)? - 직역하자면 "Top=셋톱박스"고 "Over=~를 넘어"로 Over The Top은 셋톱박스라는 하나의 플랫폼에 종속되지 않고 PC, 스마트폰, 태블릿 컴퓨터, 콘솔 게임기 등 다양한 플랫폼을 지원한다는 의미이다. - 사전에 따른 정의는 인터넷을 통해 언제 어디서나 방송/프로그램 등의 미디어 컨텐츠를 시청(소비)할 수 있는 사용자 중심적인 서비스이다. 대개 하나의 컨텐츠를 다양한 플랫폼에서 시청(소비)할 수 있는 실시간 방송과 ..

IT분야의 기사를 읽다가 'NFT' 기술이 화재가 되어 있는 것을 발견하였다 NFT란? 블록체인 기술을 이용해서 디지털 자산의 소유주를 증명하는 토큰 일단 블록체인 기술은 분산 컴퓨터 기술 기반의 데이터 위변조 방지 기술이다. 중앙 서버 없이 클라이언트 컴퓨터들끼리 직접 통신하는 P2P 방식을 기반으로 하여 소규모 데이터들이 체인 형태로 무수히 연결되어, 블록이라는 분산 데이터 저장 환경에 관리 대상 데이터를 저장함으로써 누구도 임의로 수정할 수 없고 누구나 변경의 결과를 열람할 수 있게끔 만드는 기술이다. + 기존에 전자화폐로 거래할 때 중앙 서버에 거래 기록을 보관하는 것과는 달리, 블록체인은 모든 사용자에게 거래 기록을 보여주며 서로 비교해 위조를 막는다. 각 블록은 발견된 날짜와 이전 블록에 대한..

탐욕 알고리즘(Greedy Algorithm) 최적해를 구하는 데에 사용되는 근사적인 방법 여러 경우 중 하나를 결정해야 할 때마다 그때마다 최적의 방법을 선택하여 최종 해답에 도달하는 방법 매 순간마다 최적의 선택을 하더라도 최종적 해답이 최적이라는 보장은 없다 (각 순간의 지역적 선택이 최적일지는 몰라도 전역적으로 봤을때는 최적의 선택이 아닐 수 있다) 탐욕 알고리즘 적절한 사용 탐욕 알고리즘은 아래 두 경우에 사용할 때 좋은 해결방안이 된다 탐욕 선택 속성(Greedy Choice Property) : 매 순간의 탐욕적인 선택이 최종 답의 최적의 선택이 됨 최적 부분 구조(Optimal Substructure) : 부분 문제를 최적화하는 것이 전체를 최적화하는 것임 즉 탐욕 알고리즘을 사용할 때는 ..

동적계획법(Dynamic Programming : DP) 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계기법 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 최적부분구조와 같은 문제에서 효과를 발휘함 ★ 최적 부분 구조(Optimal Substructure) 문제의 최적 해결 방법은 부분 문제에 대한 최적 해결 방법으로 구성 동적계획법 사용 동적 계획법을 적용하기 위한 예시를 가져왔다 여기서 조건은 f(a,b) = f(a-1,b) + f(a,b-1) (a,b>=1) f(0,0) = 1 자연수 n에 대하여 f(n,0)=f(0,n)=1 여기서 주목해야 하는 점은 f(1,1)이다 f(2,2)는 f(1,2)와 f(2,1)의 합으로 나타낼 수..