sh1mj1_log

바로 문제를 풀어봅시다. 백준 2164번 - 카드2 2164번: 카드2 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제 분석하기 큐를 잘 이해하고 있는지를 묻는 문제입니다. 가장 위의 카드를 가장 아래에 있는 카드 밑으로 옮기는 동작은 큐의 선입선출이 떠오릅니다! 카드의 개수의 최대가 500,000 이므로 시간 복잡도의 제약도 크지 않습니다. 큐로 이 문제를 해결해봅시다. 손으로 풀어보기 poll 을 수행하여 맨 앞의 카드를 버립니다. 이어서 바로 add 을 수행해서 맨 앞에 있는 카드를 가장 아래로 옮..

코딩 테스트를 보다가 어떠한 문제의 답에서 Scanner 와 System.out.print 함수를 사용하지 않고 BufferedReader 와 BufferedWriter 을 사용하는 것을 발견했습니다. 그런데 왜 이 두 클래스를 사용해야 하는 것일까요? 그래서 InputStream 부터, InputStreamReader, BufferedReader 을 알아보려고 합니다. 물론 OutputStream, OutputSreamReader, BufferedWriter 도 알아보구요. 그리고 코딩테스트에서 BufferdReader 와 BufferedWriter 을 사용해야 하는 이유도 알아봅시다. InputStream / OutputStream 바이트 단위 입출력을 위한 최상위 입출력 스트림 클래스 InputSt..

Stack 스택은 삽입과 삭제가 LIFO(Last-in First-out = 후입선출) 로 이루어지는 자료구조입니다. LIFO 는 삽입과 삭제가 한쪽에서 만 일어나는 특징이 있습니다. top: 삽입과 삭제가 일어나는 위치 push: top 위치에 새로운 데이터를 삽입하는 연산 pop: top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산 peek: top 위치에 현재 있는 데이터를 단순 확인하는 연산. Stack 은 DFS(Depth First Search = 깊이 우선 탐색), 백트래킹 종류의 코딩 테스트에 효과적이므로 반드시 알아두어야 합니다. LIFO 는 개념 자체가 재귀함수 알고리즘 원리와 일맥상통하기 때문입니다. Queue 큐는 삽입과 삭제 연산이 FIFO(First-in First-out ..

'Do it! 알고리즘 코딩테스트 자바 편' 교재로 공부한 내용을 정리했습니다 슬라이딩 윈도우 슬라이딩 윈도우 알고리즘은 2개의 포인터로 범위를 지정한 다음 범위(window) 을 유지한 채로 이동(sliding) 하면서 문제를 해결한다. 위 문장만 읽어봐도 투 포인터 알고리즘과 매우 비슷하다는 것을 알 수 있을 겁니다! 원리도 간단하므로 바로 백준 문제 2개를 풀어보면서 윈도우 알고리즘의 개념과 원리를 공부해 봅시다! 백준 12891 번 https://www.acmicpc.net/problem/12891 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문..

'Do it! 알고리즘 코딩테스트 자바 편' 교재로 공부한 내용을 정리했습니다 투 포인터는 2개의 포인터로 알고리즘의 시간 복잡도를 최적화 시키는 알고리즘이다. 알고리즘이 매우 간단하여 문제를 풀면서 이해를 해봅시다. 백준 2018 번 https://www.acmicpc.net/problem/2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 1. 문제분석 먼저 시간 복잡도 분석으로 사용할 알고리즘의 범위부터 줄여야 한다. 주어진 N 의 최대값은 10,000,000 이다. 만약 이 ..

'Do it! 알고리즘 코딩테스트 자바 편' 교재로 공부한 내용을 정리했습니다 구간 합 구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 것이다. 코딩 테스트에서 자주 사용되므로 잘 알아둡시다. 먼저 합 배열이 무엇인지 정의합시다. 만약 배열 A 가 있을 때 합 배열 S는 아래와 같다. S[i] = A[0] + A[1] + A{2] + … A[i-1] + A[i] 즉, S[i] 는 A[0] 부터 A[i] 까지의 합이다. 합 배열은 기존 배열을 전처리한 배열이라고 할 수 있다. 만약 이렇게 합 배열을 구해 놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N) 에서 O(1) 으로 줄어든다. 예를 들어서 A[i] ~ A[j] 까지의 배열 합을 구해야 한다고 합시다. 합 배열 ..

'Do it! 알고리즘 코딩테스트 자바 편' 교재로 공부한 내용을 정리했습니다. 배열과 리스트 배열 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조 배열의 특징 Index 을 사용하여 값에 바로 접근할 수 있다. 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. 값을 삽입/삭제 하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요하다. 배열의 크기는 선언할 때까지 지정할 수 없으며 한 번 선언하면 크기를 늘리거나 줄일 수 없다. 구조가 간단하여 코딩 테스트에서 많이 사용한다. 리스트 값과 포인터를 묶은 ‘노드’를 포인터로 연결한 자료구조 리스트의 특징 인덱스가 없어서 값에 접근하려면 Head Pointer 에서부터 순서대로 접근해야 한다. 포인터로 연결되어 있으므로 데이터 ..