본문 바로가기

분류 전체보기854

구현 코딩 테스트에서 구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다. 어떤 문제를 풀든 간에 소스코드를 작성하는 과정은 필수이므로 구현 문제 유형은 모든 범위의 코딩테스트 문제 유형을 포함하는 개념이다. 우리가 알고리즘 문제를 해결할 때, 문제를 읽고 문제 풀이 방법을 고민한다. 고민 끝에 문제에 대한 정확한 풀이 방법이 떠오르면 바로 정답 처리를 받을 수 있나? 그렇지 않다. 생각해낸 문제 풀이 방법을 우리가 원하는 프로그래밍 언어로 정확히 구현했을 때 비로소 정답 처리를 받을 수 있다. 이를 위해 프로그래밍 언어의 문법을 정확히 알고 있어야 하며 문제의 요구사항에 어긋나지 않는 답안 코드를 실수 없이 작성해야 한다. 흔히 문제 해결 분야에서 구현 유형의 문제는 '풀이를 떠올리는 것은 쉽지.. 2021. 11. 4.
백준 1931 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; import java.util.StringTokenizer; public class Main1931 { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); //회의 수 N int[][] ti.. 2021. 11. 3.
백준 11047 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main11047 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); // 동전의 종류 N i.. 2021. 11. 2.
그리디 (Greedy) 그리디 알고리즘은 단순하지만 강력한 문제 해결 방법이다. 이 알고리즘 유형은 국내 알고리즘 교재에서 단어 그대로 번역하여 탐욕법으로 소개된다. 이름에서 알 수 있듯이 어떠한 문제가 있을 때 단순 무식하게 탐욕적으로 문제를 푸는 알고리즘이다. 여기서 탐욕적이라는 것은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미한다. 그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 코딩테스트에서 만나게 될 그리디 알고리즘의 문제 유형은 앞으로 다루게 될 알고리즘과 비교했을 때 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형이라는 특징이 있다. 반면 이후에 공부할 정렬, 최단 경로 등의 알고리즘 유형은 이미 그 알고.. 2021. 11. 1.
백준 5585 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main5585 { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); //지불할 돈 N N = 1000 - N; int coinType[] = {500, 100, 50, 10 ,5, 1}; int cnt = 0; for(int i=0; i 2021. 11. 1.
복잡도 복잡도는 알고리즘의 성능을 나타내는 척도이다. 복잡도는 시간 복잡도와 공간 복잡도로 나눌 수 있다. 시간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미한다. 공간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다. 동일한 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을 수록 좋은 알고리즘이다. 복잡도를 측정함으로써 다음의 2가지를 계산할 수 있다. 시간 복잡도 : 알고리즘을 위해 필요한 연산의 횟수 공간 복잡도 : 알고리즘을 위해 필요한 메모리의 양 시간 복잡도 시간복잡도를 표현할 때는 빅오 표기법을 사용한다. 빅오 표기법을 간단히 정의하자면 가장 빠르게 증가하는 항만을 고려하는 표기법이다. 다시 말해 함수의 상한만을 나타.. 2021. 11. 1.

티스토리툴바