김챠챠의 개발기록

투포인터투 포인터(two-pointer)란, 선형 자료구조(배열, 리스트 등)에서 위치(index)를 가리키는 변수(=포인터) 두 개를 사용하여 탐색 범위를 효율적으로 좁혀나가는 알고리즘 풀이 기법이다. 위와 같이 정렬되어있는 배열에서 두 수의 합이 6이 되는 쌍을 탐색하는 문제가 있다고 가정하자. 우리가 생각할 수 있는 가장 기본적인 아이디어는 이중 for문을 사용한 완전탐색(brute-force)으로, 이러한 경우 O(N^2) 의 시간복잡도 내에 문제를 해결할 수 있게 된다. 그러나 만약 배열의 길이가 너무 길다면 단순 완전탐색으로는 주어진 시간 내에 문제를 풀 수 없을 수도 있다. 따라서 시간을 조금 줄이기 위해, 조금 다른 방식으로 문제에 접근해보자. 숫자 쌍을 찾을 때, 한 숫자가 정해졌다면 특..

동적 배열동적 배열동적 배열(Dynamic Array) : 동적 할당(dynamic allocate)를 통해, 크기를 변경할 수 있도록 한 배열의 일종일반적인 자료구조에서 리스트(list) 라고 하면 대부분 동적 배열을 의미index를 이용한 데이터 접근이나 탐색과 같은 배열의 형태와 장점을 그대로 유지내부적으로 배열로 구현되므로 캐시 메모리 적중률 이 높음◆ 동적 할당(dynamic allocate)컴파일 단계에서 크기를 미리 정해주는 배열과는 달리, 런타임 단계에서 크기에 따라 메모리를 가변적으로 배치하는 것을 의미한다. Java는 모든 객체의 메모리값을 JVM이 동적 할당해준다.동적 배열과 복잡도시간복잡도접근 / 변경 : O(1)인덱스를 이용해 해당 데이터에 바로 접근하고 변경할 수 있음삽입 / 삭..

배열배열 배열(Array) : 데이터(원소; element)를 메모리 상에 연속하게 배치하여 논리적 / 물리적 구조가 일치하는 선형 자료구조동일한 자료형의 원소들만 저장 가능인덱스(index ; 순서값) 를 통해 O(1)라는 빠른 시간 내에 idx 번째 원소에 접근 / 변경할 수 있음연속한 메모리 주소를 필요로 하므로, 원소의 자료형과 크기가 정해지면 변경할 수 없음캐시 메모리 적중률 이 높아  최적화 성능이 우수함 ◆ 캐시 메모리 적중률(cache hit rate)컴퓨터는 자주 이용할 것 같은 자료를 캐시 메모리(Cache memory) 라는 공간에 따로 저장하여 성능을 향상시키는데, 적중률 이란 캐시 메모리에 저장되어 있을 확률을 의미한다. 적중률이 높기 위한 3가지 조건을 지역성(locality)의..

자료구조자료구조자료구조(data structure) : 효율적인 관리를 위해 특성이나 상호 관계 등에 따라 구조화시킨 데이터, 혹은 그의 집합체대부분의 프로그래밍 언어는 자료형(data type) 을 통해 자료구조를 정의원시 자료형자료를 특성에 따라 효율적으로 메모리에 저장하기 위해 분류한 기준프로그래밍 언어 차원에서 지원되는 기본적이고 독립적인 자료구조 추상 자료형(ADT : Abstract Data Type)다수의 원시 자료형들을 효율적으로 관리하기 위해 정의된 자료구조구성하는 원시 자료형과 필요한 연산 등을 수학적/논리적으로 정의해놓은 집합체※ 자료구조가 논리적으로 정의 및 설계된 용어라면, 자료형은 각 프로그래밍 언어에서 정의된 실제적 형식이다. 예를 들어 Java 는 인터페이스(혹은 추상클래스)..

두개의 포인터를 두고 포인터를 움직이면서 탐색하는 방법중 하나주로 아래 두가지 상황에서 많이 쓰임1. 특정 조건을 만족하는 두 수개구간 [s, e] (특히 배열)에서 s는 0, e는 n-1에서 서로 가까워진다.https://www.acmicpc.net/problem/3273투포인터의 기본 아이디어는 다음과 같다."정렬된 선형 자료구조"이며, "특정 조건을 만족시키는 두수"가 있다면, 그외의 숫자는 만족시킬수 없다이다. 예를 들어 아래의 배열에서 더해서 10이 되는 숫자를 찾는다고 쳐보자[2,1,8,3,7,4]우리야 눈으로 3과 7, 2와 8이 보이지만 컴퓨터는 그런거 모른다.저걸 완전탐색으로 찾는다고 생각해보면, 총 15번의 비교가 일어난다. N개의 쌍이 있다면 O(N^2)다.근데 3과 7, 2와 8을 ..

지난번에 알아본 Scanner는 편리하게 입력을 받을 수 있는 장점이 있으나, 속도가 느리다는 단점이 있었다. 백준 등의 알고리즘 사이트에서는 보통 실행속도의 증가를 위해서 BufferedReader와 BufferedWriter를 사용하여 입출력을 하는 경우가 있다.입력 : BufferedReaderBufferedReader는 Java.io 패키지에서 제공하는 클래스로, 버퍼(Buffer)를 사용해서 입력을 한번에 받음으로써 시간을 획기적으로 줄일 수 있다. next() 입력된 값 중 한글자를 반환한다.nextLine() 입력된 값 중 개행(enter)으로 구분된 전체 줄을 반환한다.  BufferedReader 는 Scanner 에 비해 훨씬 빠른 입력속도를 자랑하며, 실제로 BufferedReader..

지난번에 알아봤던 System의 표준 입력 메서드인 System.in.read()는 여러모로 사용하기 불편했다. 따라서 Java에서는 쉽게 입력 받을 수 있는 방법인 Scanner를 추가적으로 제공한다.이 외에도, 대량의 문자열을 모아서 빠르게 출력하기 위한 표준 방법인 StringBuilder도 함께 소개한다.입력 : ScannerScanner 는 Java5부터 제공된 표준 입력 클래스로, Java.util 패키지에 존재한다. Scanner는 내부적으로 정규표현식(regex)를 사용하여 읽은 문자를 토큰화시키고, 메서드에 따라 타입을 변환하여 입력받을 수 있다.nextInt()입력된 값 중 정수 토큰을 반환한다.nextDouble()입력된 값 중 실수 토큰을 반환한다.next()입력된 값 중 띄어쓰기(..

APS를 풀 때 가장 간단한게 사용할 수 있는 입출력 메서드는, Java의 System 클래스에서 제공하는 메서드들이다.출력 : System.outSystem.out 은 System 클래스에서 제공하는 정적 필드로, PrintStream 타입의 Java 표준 출력 스트림이다. 여기서 스트림이나 PrintStream 이 무엇인지 하나하나 설명할 수는 없으니, 그냥 "출력"에 관여하는 가장 기본적인 클래스라고 생각하면 된다. System.out에서 가장 중요한 메서드는 print() 로, 문자열을 콘솔창에 출력한다.System.out.println()입력받은 인수를 모두 출력하고 개행한다.System.out.print() 입력받은 인수를 모두 출력하고 개행하지 않는다.System.out.printf()입력받..