kittae 님의 블로그

스택(Stack)이란?"쌓다", "쌓아 올리다"라는 뜻의 용어로, 데이터를 저장하고 관리하는 선형 자료 구조이다.LIFO(Last In, First Out) 형태로 마지막에 들어간 데이터가 가장 먼저 나오는 특성을 가지고 있다.예시로 접시나 상자 쌓기와 유사한 형태라고 생각하면 된다. 스택의 주요 특징은?LIFO(Last In, First Out)가장 마지막에 추가된 데이터가 가장 먼저 제거된다.한쪽 끝에서만 작업 수행데이터 삽입, 삭제가 스택의 맨 위(top)에서 이루어진다. 스택의 주요 연산은?1. push or add스택에 데이터를 추가한다.Stack stack = new Stack(); stack.push(10); // 스택에 10 추가stack.add(20); // 스택에 20 추가..

스택을 입문하기 좋은 매우 쉬운 문제다! 필자는 3년 전 C++로 코딩테스트 문제를 많이 풀었을 때, 거의 대부분 배열을 stack, vector으로 구현했었다.그래서 그런지 오랜만에 회고하는데도 큰 무리 없이 쉽게 푼 것 같다! 메모리 제한과 시간제한은 충분하다고 판단했다!  나의 구현 로직이다1 X: 정수 X를 스택에 넣는다. (1 ≤ X ≤ 100,000) -> push2: 스택에 정수가 있다면 맨 위의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다. -> pop3: 스택에 들어있는 정수의 개수를 출력한다. -> size4: 스택이 비어있으면 1, 아니면 0을 출력한다. -> empty5: 스택에 정수가 있다면 맨 위의 정수를 출력한다. 없다면 -1을 대신 출력한다. -> peekfor 문 사..

쉬운 문제였다! 로직을 생각해봣을 때, 무언가 int형 배열을 쓰는 거 보다 String으로 문자를 입력받아 charAt()을 사용하여 Character 배열로 내림차순 하는 게 낫다고 생각했다! 시간제한과 메모리제한은 n이 1,000,000이란 점에서 걱정했지만 2초라는 점에서 O(n^2)까진 가능할 거라고 판단했다. 내가 생각한 로직이다.1. string으로 문자를 받음2. 해당 문자를 charAt()으로 다시 배열로 변경3. 해당 n의 크기가 1억개이니 Collections.sort(); -> Collections.sort는 O(n log n)을 보장하기 때문! [최종 코드]import java.io.*;import java.util.*;public class Main { public stat..

매우 쉬운 문제였지만, 의문이 들었던 문제였다! 먼저 시간제한은 2초, 메모리 제한은 256MB라는 점에서, 테스트 케이스가 1,000,000개이기 때문에 그냥 일반 sort를 해도 된다고 생각이 들었다.  그래서 처음에는 Arrays.sort를 했을 때와 Collection.sort의 차이점을 확인해 봤다. [최종코드 - Arrays.sort]import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n..

구현 자체는 매우 쉬운 문제이다! 시간 제한과 메모리 제한은 테스트 개수가 적기 때문에 상관없다고 판단했다. 내가 생각한 로직이다.내림차순 구현이 간단한 ArrayList 사용 (Collections.reverseOrder())내림차순 후 arr.get(k-1)로 k번째 배열 추출 [최종 코드]import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new S..

정렬을 안다면 매우 쉬운 문제다! 시간 제한과 메모리 제한은 상관없다고 판단했다. 내가 생각한 로직이다sort 후 평균값(n.size() / 2) + 1의 값 출력(중앙값) 사실 고정된 수이기 때문에 arr[2]를 사용해도 되지만, 그래도 알고리즘이기 때문에 위 로직처럼 했다! 그리고 고정된 값이기 때문에 ArrayList 대신 배열을 사용했다! [최종 코드]import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in..

매우 쉬운 문제이다! 수는 중복되지 않는다는 점에서 HashSet을 안쓰고 ArrayList or 배열로 풀 수 있다고 판단했다! 로직은 쉽기 때문에 넘어가겠다! 이번에는 정렬에 기본을 쌓기 위해 3가지 문제를 풀었다!1. ArrayList2. 배열3. Hash Set[최종코드 - ArrayList]import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseIn..

생각보다 생각을 많이 한 문제인 것 같다. 브루트포스 문제이기 때문에 해당 알고리즘만을 사용해야된다는 강박에 시달려 해당 알고리즘 생각에 지연이 생겼다. 주어지는 N의 수가 매우 짧기 때문에 시간 제한과 메모리 제한은 상관없다고 판단했다! 내가 생각한 로직은 이렇다.3키로 or 5키로먼저 5키로로 다 나누고, 만약에 %3이 안되면, +5한다음 %나누기.안되면 -1 되면 기존 로직 구현 [최종 코드]import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Input..

매우 쉬운 문제다!3년 전에 알고리즘을 모르고 단순히 반복분과 중첩문만을 가지고 문제를 풀었던 시절이 있었다. 그때는 c++로 했었는데 티어가 높아질 수 록 매 문제마다 시간 초과 문제가 생겼던 기억이 난다. 지금 다시 확인해 보니깐, 내가 풀었던 알고리즘은 실제로 있는 브루트포스란 알고리즘이었다!! (말 그대로 무식한 힘)  시간 복잡도는 N이 100이라는 점에서 시간 제한과 메모리 제한은 여유롭다고 판단했다! 구현 로직for (int i = 0; i   [최종코드]import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { Buffered..

브루트포스란?Brute: 무식한Force: 힘  쉽게 설명하자면 무식한 힘을 갖는 알고리즘을 뜻한다. 완전탐색으로 답을 찾는 알고리즘이며, 해당 알고리즘은 반복문과 조건문을 사용한다!어떻게 동작하는가?가장 유명한 문제로는 자물쇠 문제가 있다.모든 수를 탐색하여 자물쇠를 푸는 비효율적이면서도 100% 정확도를 자랑하는 브루트포스의 대표적인 문제이다.// 실제 비밀번호 (예: 1234)int actualPassword = 1234;// 4중 for문을 사용하여 모든 4자리 비밀번호를 탐색for (int i = 0; i  시간 복잡도는?단일 루프: O(n)중첩 루프: O(n^2)3중 루프 이상: O(n^k) (k는 중첩된 반복문의 수)이므로 경우의 수가 많아질 수록 비효율적이다.공간 복잡도는?별도의 메모리 사..