분류 전체보기
[백준] 2470 두 용액 - Java
[백준] 2470 두 용액 - Java
2022.05.04해당하는 용액을 빠르게 찾아야 한다. 먼저 이분 탐색을 활용해 풀어보자. 용액의 특성값 합이 0에 가장 가까워야 한다. 용액에 대해 오름차순으로 정렬을 수행한 후, target을 -arr[i]로 설정하고 이분 탐색을 진행하자. 1. target이 특성값 배열의 최댓값보다 크면 R + 1을 반환한다. 2. 1의 경우가 아니면 target과 가장 근접한 요소의 인덱스를 반환한다. 이진 탐색 코드는 자주 사용되니, 정형화된 스타일을 익혀 두자. import java.util.*; import java.io.*; public class Mabn{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedRe..
[백준] 7795 먹을 것인가 먹힐 것인가 - Java
[백준] 7795 먹을 것인가 먹힐 것인가 - Java
2022.05.04원소를 하나하나 비교하고 있으면 시간 초과가 날 게 뻔하다. 이분 탐색을 통해 빠르게 비교하자. 이분 탐색을 할 때 배열의 인덱스에 주의하자. 0부터 시작하는 것 보다 1부터 시작하도록 조작한 후 이분 탐색을 수행했을 때 실수를 줄일 수 있더라... import java.util.*; import java.io.*; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int T = Integer.parseInt(br.readLine()); StringTokenizer st; for(int..
정렬 기본 - Java
정렬 기본 - Java
2022.05.03자바에서 정렬을 수행할 때는 Integer, char과 같은 Primitive 원소에 대해서는 Dual-Pivot Quick Sort를 사용하고, 객체를 정렬할 때는 Tim Sort를 사용한다. (내부 함수 사용 시) 왜 객체와 객체가 아닌 것에 대해 따로 정렬을 수행할까? 한 가지 방법으로 통일하면 일관성을 유지할 수 있어 이해하기 쉽지 않을까? 이 질문에 대해 답하기 위해서는 In-place와 Stable여부를 알아야 한다. 정렬 알고리즘이 In-place하다면, 정렬 과정에서 정렬을 수행하는 N에 비해 무시할 만한 개수의 메모리만 사용함을 의미한다. 정렬할 요소의 수가 10만개이고, 10만개의 요소를 정렬할 때 추가로 사용해야하는 메모리가 10이라면 무시할 만 하다고 할 수 있다. 다음으로, 정렬 ..
[백준] 1182 부분수열의 합 - Java
[백준] 1182 부분수열의 합 - Java
2022.05.02재귀함수를 사용해 백트래킹을 구현해서 풀 수 있는 문제이다. 백트래킹 알고리즘에서 가장 중요한 부분은 재귀함수의 올바른 정의이다. 재귀함수와 반복문잉 본직적인 차이가 없음을 이해하고 재귀함수를 정의하자.. 재귀적 스타일에 익숙해 지는 게 중요하다. 종료 조건 명시해두고, 인덱스를 하나씩 늘려 가며 "이렇게 작성하면 모든 경우를 셀 수 있겠다." 라는 믿음을 가지자. import java.util.*; import java.io.*; public class Main { static int N; static int S; static int ans; static int arr[]; public static void main(String[] args) throws IOException { BufferedRead..
[C] 배열의 포인터
[C] 배열의 포인터
2022.05.01지난번에 포인터의 배열을 포인터의 포인터로 바꿔서 표현할 수 있다는걸 배웠다. 그럼 이제 배열의 포인터에 대해 공부할 차례이다. 말 그대로 포인터 변수를 따라가면 배열이 나오는.. 그런 상황에서 배열의 포인터를 사용한다. 뒤에 [10]을 붙여서 주소를 통해 찾아간 값이 10의 크기를 가지는 char타입의 배열임을 명시해준다. 포인터의 배열과 배열의 포인터를 헷갈리지 말자. 괄호를 어떻게 붙이는가에 따라 두 가지가 갈린다. 예시를 통해 정리하자.
[C] 이중 포인터
[C] 이중 포인터
2022.05.01포인터 변수는 어떤 값의 주소를 담는 변수이다. 그러면 포인터 변수의 주소를 담는 값도 있지 않을까? 즉, 포인터의 포인터도 있지 않을까? 주소 1048로 찾아가면 double타입의 3.14가 있는데.. 주소 1072로 찾아가면 주소 1096이 있다. 주소는 혼자 사용하면 아무 의미가 없다. 의미가 생기려면 1096을 주소로 찾아갔을 때 얻을 수 있는 특정 값을 알 수 있어야 하지 않을까? 포인터의 포인터는 int ** d 처럼 타입과 * 두 개로 표현한다. 변수 d 는 * 타입. 즉, 주소 타입이고, 그 주소를 찾아가면 또 다시 주소가 나오고, 그 주소를 찾아가면 int값이 나온다.. 정도로 생각할 수 있다. 예제를 통해 확실하게 잡고 넘어가자. 포인터의 포인터가 존재함을 알았는데.. 그럼 포인터의 배..
[C] 다차원 배열 초기화
[C] 다차원 배열 초기화
2022.05.01정방형 배열의 형태를 지니게 하기 위해 남는 공간은 0으로 채워준다. 2차운 배열에서 row부분의 크기는 생략할 수 있다. (알아서 계산해준다.) 2차원 배열을 1차원 배열의 모음으로 해석할 수 있다. 1차원 배열에서 포인터를 사용해 배열을 다룬 것 처럼, 2차원 배열에서도 첫 번째 요소의 주소를 취할 수 있다. 문자열을 배열로 다룰 때 자주 사용된다. 3차원 배열도 크게 다른 부분은 없다. 지정할 때 높이 / row / column 순으로 지정함을 기억하자.
[C] 다차원 배열
[C] 다차원 배열
2022.05.01먼저 배열의 종류에 대해 알아보자. static배열과 Fixed Dynamic배열은 컴파일 할 때 배열의 최대 범위가 정해지지만, Dynamic배열은 배열의 최대 범위가 계속해서 변할 수 있다. (Java의 ArrayList와 비슷한데, 일단은 ArrayList도 배열이라고 개념적으로 생각하자.) 배열을 관리할 때는 Descriptor를 사용한다. Descriptor는 배열을 선언한 뒤 선언된 배열을 저장할 때 사용된다고 이해하면 되고, 컴파일 시에 사용된다. 즉, 메모리를 할당하는 코드를 생성하기 위해 Descriptor가 사용되고, 왼쪽 그림과 같은 정보를 지닌다. 컴파일 말고 런타임 과정에서도 Descriptor를 가질 수 있는데, Java를 생각하면 이해하기 쉽다. Java에서 배열을 다룰 때 i..
[백준] 15500 이상한 하노이 탑 - Java
[백준] 15500 이상한 하노이 탑 - Java
2022.05.01스택을 사용해서 풀 수 있는 문제이다. 기존 하노이 탑에서 조건이 많이 수정돼서 재귀를 사용할 필요가 없다. 1 2 3 세 개의 장대가 주어지고, 3번 장대에 탑을 쌓아주면 되는 상황이다. 1. 1번 장대에 걸린 요소들을 검사해 3번 장대에 들어갈 순서인지 확인하고, 맞으면 3번 아니면 2번으로 옮긴다. 2. 2번 장대에 대해서도 위와 같은 작업을 수행한다. 3. 3번 장대에 탑이 완성되면 마무리한다. import java.util.*; import java.io.*; public class Main { static StringBuilder sb; public static void main(String[] args) throws IOException{ BufferedReader br = new Buffe..
[백준] 11729 하노이 탑 이동 순서 - Java
[백준] 11729 하노이 탑 이동 순서 - Java
2022.05.01재귀를 사용해서 풀 수 있는 문제이다. 재귀함수.. 공부하고 있긴 한데 생각하고 구현하기가 참 어렵다.. 이렇게 작동하겠지? 라고 작성하는 정도는 어떻게 할 수 있을 것 같은데, 코드의 작동을 하나하나 따라가서 분석하는게 쉽지 않다.. 재귀는 dfs bfs 백트래킹 등등 여러 알고리즘에 활용되고, 중요한 테크닉이다. 꾸준히 관련된 문제 풀어보고 공부해서 익숙해져야겠다. import java.util.*; import java.io.*; public class Main { static StringBuilder sb; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new Input..
[백준] 17952 과제는 끝나지 않아! - Java
[백준] 17952 과제는 끝나지 않아! - Java
2022.05.01스택 자료구조를 사용해 하라는 대로 구현하면 풀 수 있는 문제이다. import java.util.*; import java.io.*; public class Main { static long arr_koong[] = new long[68]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); Stack stack = new Stack(); StringTokenizer st; int ans = 0; for (int i = 0; i < N; i++)..
[백준] 9625 BABBA - Java
[백준] 9625 BABBA - Java
2022.05.01dp를 이용해 풀 수 있는 간단한 문제이다. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int K = Integer.parseInt(br.readLine()); BABBA temp = new BABBA(1, 0); for(int i = 0; i