분류 전체보기
-
백준 5557번: 1학년 (Python/Java)Algorithm/Algorithm Problem 2022. 4. 9. 17:45
https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 접근 점화식만 제대로 찾는다면 어렵지 않게 풀 수 있는 문제다. 예제를 통해 풀이를 생각해보자. 총 열한 개의 숫자가 주어지고, 숫자 배열은 [8, 3, 2, 4, 8, 7, 2, 4, 0, 8, 8]이다. 여기서 배열의 가장 마지막 수는 연산을 통해서 '만들어야 하는 숫자'지 실제 연산에 쓰이는 숫자가 아니다. 즉, 우리가 실제로 쓸 숫자 배열은 마지막 인덱스 숫자를 뺀 [8, 3, 2,..
-
백준 24524번: 아름다운 문자열 (Python/Java)Algorithm/Algorithm Problem 2022. 3. 30. 22:18
https://www.acmicpc.net/problem/24524 24524번: 아름다운 문자열 첫째 줄과 둘째 줄에 영어 알파벳 소문자로만 이루어진 문자열 $S$와 $T$가 각각 주어진다. ($1\leq \left|S \right|\leq 10^6$, $1\leq \left|T \right|\leq 26$, $\left|T \right|\leq \left|S \right|$, $\left|S \right|$와 $\left|T \ www.acmicpc.net 접근 만들 수 있는 단어를 찾기 위해 몇 번씩이나 주어진 문자열을 반복 탐색하는 것은 비효율적이고 연산이 늘어난다. 이런 연산을 줄이기 위해 최대한 주어진 문자열 탐색을 줄이도록 하겠다. 이번 풀이에서는 문자열을 딱 한번 탐색할 것이다. 그만큼 아..
-
백준 6068번: 시간 관리하기 (Python/Java)Algorithm/Algorithm Problem 2022. 3. 28. 22:33
https://www.acmicpc.net/problem/6068 6068번: 시간 관리하기 성실한 농부 존은 시간을 효율적으로 관리해야 한다는 걸 깨달았다. 그는 N개의 해야할 일에 (1= 0){ System.out.println(thisTime); }else{ System.out.println(-1); } } } 후기 포스팅하며 풀이과정을 살펴보다가 생각난 건데, 사실 위 코드에는 굉장히 쓸데없는 정렬이 들어가 있다. 사실 정렬은 '끝내야 하는 시간의 내림차순'으로만 정렬하면 된다. 근데 위 코드에선 끝내야 하는 시간이 같다면 걸리는 시간을 기준으로 다시 내림차순을 해줬다. 전혀 필요 없는 연산이다. 정렬하면 뭐할 거냐, 1+2나 2+1이나 같은 건데 굳이 정렬을...? 왜 그랬냐 물어본다면, 어....
-
이분탐색 (Binary Search)Algorithm/Algorithm Categories 2022. 3. 27. 18:06
기본 개념 배열 내의 특정 값을 찾는 기초적인 알고리즘이다. 특정 값을 찾기 위해 모든 데이터를 순차 탐색을 하는 것이 아니라 탐색 범위를 반씩 줄여나가며 탐색을 진행한다는 특징을 가지고 있다. 여기서 중요한 점은 배열이 정렬되어 있어야 한다는 점이다. 특정 조건을 토대로 범위를 절반씩 줄여나가기 때문에 정렬되지 않은 배열에서 이분 탐색은 사용할 수 없다. 이분 탐색을 구현할 때 변수를 보통 세 가지를 사용한다. start, mid, end 세 가지 변수를 통해 현재 탐색 범위의 시작은 start, 탐색 범위의 끝은 end, 그 중간 값은 mid로 사용한다.(물론 변수 명은 개인에 따라 바뀔 수 있다). 이 세 변수를 통해 찾으려는 데이터와 중간 값 위체에 있는 데이터를 반복적으로 비교해서 특정 값을 찾..
-
Tree(트리)Computer Science/Data Structure 2022. 3. 27. 17:18
Tree(트리)의 개념과 특징 트리 자료구조란? 트리는 그래프의 한 종류로, 한개 이상의 node(노드)들이 나무가지처럼 연결된 자료구조를 의미한다. 하나의 루트 노드와 0개 이상의 자식 노드를 가진 방향성 있는 그래프를 트리라고 한다. 트리의 특징 하나의 root node(루트 노드)를 가진다 루트 노드는 0개 이상의 자식 노드를 가진다 자식 노드는 또 각자 0개 이상의 자식 노드를 가지고 있고 이는 반복적으로 정의된다 즉, 트리는 재귀적인 구조를 가지고 있다 트리는 노드와, 노드를 연결하는 edge(간선)으로 구성된다. 트리는 DAG(Directed Acyclic Graphs, 방향성이 있는 비순환 그래프)의 한 종류다. 때문에 트리에는 cycle(사이클)이 존재하지 않는다. 즉, 같은 노드를 거치지..
-
자바 가상 머신(Java Virtual Machine, JVM)이란?Programming Language/Java 2022. 3. 27. 15:18
Java Virtual Machine의 개념 정의 자바 컴파일 과정을 살펴본 사람들이라면 JVM이라는 개념이 어느 정도 익숙할 것이다. JVM은 '자바 컴파일러에 의해 생성된 자바 바이트 코드를 실행시키기 위한 가상머신'을 의미한다. JRE(Java Runtime Environment, 자바 런타임 환경)에 포함되어 있다. 즉, '코드를 실행하고, 해당 코드에 대한 런타임 환경을 제공하는 프로그램에 대한 사양'이다. 개발자들은 '어떤 기기 상에서 실행되고 있는 프로세스, 특히 자바 앱에 대한 리소스를 대표하고 통제하는 서버'를 지칭하기도 한다. 우리가 흔히 '자바는 OS에 독립적인 언어'라고 하는데 그렇게 될 수 있는 이유가 바로 이 JVM의 존재다. 즉, 그게 어떤 OS든지 JVM이 돌아가는 환경이라면..
-
백준 17828번: 문자열 화폐 (Python/Java)Algorithm/Algorithm Problem 2022. 3. 27. 13:53
https://www.acmicpc.net/problem/17828 17828번: 문자열 화폐 첫 번째 줄에 문자열의 길이 N(1 ≤ N ≤ 5,000,000)과, 문자열의 가치를 나타내는 정수 X(1 ≤ X ≤ 500,000,000)가 공백으로 구분되어 주어진다. www.acmicpc.net 접근 사전 순으로 가장 빠른 문자열을 구하라는 말은 A부터 Z까지 순서대로 문자가 들어가야 한다는 뜻이다. 하지만 문자열 길이는 정해져 있고, 가장 처음에 A 하나 넣고 그 뒤에 조합될 수 있는 모든 경우의 수를 비교하기에는 연산이 비상식적으로 늘어날 것이 분명하다. 때문에 조금 더 과감해졌다. 모든 문자열을 A로 채워 넣었다. 예시를 살펴보자. 만일 길이가 5인 문자열을 통해 가치를 7로 만들어야 한다고 생각해보..
-
자바 컴파일 과정Programming Language/Java 2022. 3. 26. 21:17
자바는 'OS에 독립적'이라는 특징이 있다. 풀어서 설명하자면 자바로 작성된 코드는 OS가 무엇인지와 상관없이 실행할 수 있다는 뜻이다. 이것이 가능한 이유는 JVM(Java Virtual Machine)이다. 이제 JVM의 어떤 기능으로 인해 OS에 독립적으로 실행될 수 있는지 자바의 컴파일 과정을 통해 알아보도록 하자. 자바 컴파일 과정 개발자의 자바 소스코드 작성(.java파일) 자바 컴파일러(Java Compiler)가 javac라는 명령어를 수행한다. javac는 소스코드를 자바 가상 머신(Java Virtual Machine, JVM)이 이해할 수 있는 바이트 코드(.class 파일)로 컴파일하는 명령어다. 이 바이트 코드는 아직 JVM만 읽을 수 있고 컴퓨터는 이해하지 못하는 반기계어 상태이..