시간 제한과 시간 복잡도코딩 테스트의 제한 시간: 보통 `1~5초`1초에 실행 가능한 최대 연산 횟수: 약 `1억 번`알고리즘 선택 기준: 문제의 시간 제한을 고려하여 시간 복잡도를 분석하고 적절한 알고리즘을 선택해야 한다. 예시: N의 최대값이 100,000이고 제한 시간이 1초인 경우 - 허용 가능한 최대 연산 횟수: `1억 번`- 시간 복잡도가 O(N²)일 경우: - 연산 횟수 = `100,000 × 100,000 = 100억 번` - `1억 번을 초과하므로 사용 불가능`- 적절한 알고리즘 선택: O(N log N) 이하의 알고리즘을 고려해야 함 (예: 정렬 알고리즘, 이진 탐색 등) 1초에 최대 연산 횟수(최대 입력 크기) 시간 복잡도 최대 연산 횟수 O(N)약 1억번O(N^2)약..
코딩테스트/이론
경우의 수 경우의 수는 특정 사건에서 발생할 수 있는 가능한 결과의 총 가짓수를 의미한다. 예를 들어, 동전을 던질 때 앞면 또는 뒷면 중 하나가 나오므로 경우의 수는 2가지이다.주사위를 던지면 1부터 6까지의 숫자가 나올 수 있어 경우의 수는 6가지이다 합의 법칙합의 법칙은 두 사건이 동시에 발생하지 않을 때, 각 사건의 경우의 수를 더하여 전체 경우의 수를 구하는 방법이다.예를 들어, 한 개의 주사위를 던져 2의 배수 또는 5의 배수가 나오는 경우의 수를 구해보해보자.2의 배수가 나오는 경우: 2, 4, 6 → 경우의 수는 3가지5의 배수가 나오는 경우: 5 → 경우의 수는 1가지따라서, 2의 배수 또는 5의 배수가 나올 경우의 수는 3 + 1 = 4가지이다.이처럼 합의 법칙은 "또는", "~이거나"..
백준 코딩 테스트에서 입력 처리를 위해 BufferedReader를 사용하고 있다. 속도 면에서 유리하다는 이유로 사용했지만, 정확한 이유는 알지 못했다. 최근 피드백에서 Scanner를 사용하는 것이 유리한 경우도 있다는 이야기를 듣고, 이번 기회에 Scanner와 BufferedReader의 차이점을 알아보려 한다. 1. ScannerScanner 클래스는 java.util패키지에 포함된 클래스이다. 표준 입력(System.in)을 파싱 하여 기본 데이터 타입 및 문자열로 반환하는 기능을 제공한다. 특징java.util 패키지 안에 있다. (java.util.Scanner)공백 및 개행을 기준으로 읽는다. (토큰단위)기본 데이터 타입을 지원한다. (nextInt(), nextDouble() 등)버퍼의..
오늘 멘토링 시간에 코딩테스트 관련 정보를 알려 주실 때 간단하지만 간과하고 넘어갈 수 있는 요소인 출력문에 대해 이야기 해주셨다. 나같은 경우는 백준같은 출력문이 필요한 문제를 풀 때 출력문을 크게 고민하지 않고 풀다보니 막상 해당 질문을 받으니 뭐라 답변할 지 모르겠다. 그렇기 때문에 이런 기회에 정리를 해보고 문제 풀 때 의식적으로 고민해보도록 하자. 1. println괄호안 내용을 출력한 후 마지막에 개행 문자(\n) 가 포함되어 있어 자동으로 줄바꿈이 된다. 장점간결한 출력 가능줄바꿈을 자동으로 처리해 가독성을 유지System.out.println("Hello, World!");System.out.println("This is a new line.");Hello, World!This is a..
아스키 코드에서 각 문자에는 고유한 숫자 값이 할당되어 있다. 문자 '0'부터 '9'까지는 연속된 값으로 할당되며, 그 값은 다음과 같다.'0'의 아스키 코드 값: 48'1'의 아스키 코드 값: 49...'9'의 아스키 코드 값: 57이 연속적인 값의 특징을 활용하면, 문자와 숫자 간의 변환을 손쉽게 수행할 수 있다.예제: '1' → 숫자 1로 변환'1'의 아스키 코드 값은 49 이다.'0'의 아스키 코드 값은 48 이다.'1' - '0'를 계산하면, 49 - 48 = 1이 된다.결과적으로, 문자 '1'에서 '0'을 빼면 해당 문자를 숫자로 변환할 수 있다. 일반화된 규칙문자 '0'부터 '9'까지의 숫자로 변환하려면int 숫자 = 문자 - '0';이 방법은 모든 숫자 문자를 정수 값으로 변환할 때 유효하..
1. 자연수 N의 자리수 합 구하기정수 N의 각 자리수를 더하려면, 숫자를 10으로 나누고 나머지를 이용하는 방법을 사용한다.public static int sumOfDigits(int n) { int sum = 0; while (n > 0) { sum += n % 10; // 마지막 자리수 더하기 n /= 10; // 마지막 자리 제거 } return sum;}n % 10 : 자연수 n의 마지막 자리수를 가져온다. 예) 123 % 10 = 3 n /= 10 : n에서 마지막 자리수를 제거한다. 예) 123 / 10 = 12 2. 문자열 S의 각 자리수 합 구하기문자열 S의 각 자리수를 더하려면, 문자열의 각 문자를 숫자로 변환하여 합산한다.p..
StringBuilder 활용 자바에서 문자열을 뒤집는 가장 쉬운 방법을 StringBuilder를 활용하는 것이다. StringBuilder는 다양한 메서드를 지원해 주는데 그중 하나가 문자열을 반대로 변환시켜주는 reverse() 메서드이다.String str = "Hello World";String tmp = new StringBuilder(str).reverse().toString();System.out.println(tmp);// dlroW olleH주의할점을 toString 메스드로 String으로 반환시켜야 한다는 것이다. 반복문 사용하기 문자열을 문자 배열로 변환한 후, 배열을 뒤집고 다시 문자열로 변환하는 방법이다.String original = "Hello, World!";char[] ..
문자열 문제를 풀다 보면 문자열에서 어떤 특정 부분을 찾거나 다른 문자열로 치환해야 되는 경우가 많이 있다. 문자 대소문자 변환 메서드 toUpperCase(), toLowerCase()도 치환 메서드 중 하나이다. 문자 찾기와 바꾸기 문자열 내 특정 부분을 찾는 메서드와 바꾸는 메서드를 알아보자.문자열 포함여부를 검사하는 메서드메서드반환형내용contains(CharSequence s)boolean전달받은 문자열이 원본 문자열에 있는지 검사startsWith(String prefix)boolean원본 문자열이 전달받은 문자열로 시작하는 지 검사 endWith(String suffix)boolean원본 문자열이 전달받은 문자열로 끝나는지 검사indexOf(String str)int 원본 문자열이 전달받..
문자열은 문자의 배열이다. 자바에선 문자는 작은 따옴표('), 문자열은 큰 따옴표(")를 사용해서 나타낸다. char character = 'H';String string = "Hello"; 문자열에서 문자 가져오기자바에서 문자열을 나타내는 String 클래스는 내부적으로 문자의 배열을 통해 표현된다. 그렇기 때문에 문자열 내 문자를 가져오는 방법을 제공한다. String.charAt(int index);String.toCharArray();String.charAt() 메서드는 주어진 인덱스에 있는 문자를 Char 형식으로 반환한다. 반면 String,toCharArray() 메서드는 모든 문자가 들어있는 char[] 형식의 데이터를 반환한다. 주로 문자열을 문자배열 형태로 반복문을 돌릴 때 사용된다. ..
인프런 김태원 님 강좌를 듣고 정리한 내용입니다. 냅색 문제? 짐 싸기 문제 또는 배낭 문제라고 불리며 범위가 늘어날수록 시간초과의 위험이 있어 DP(동적 계획법)으로 푸는 경우가 많다. 서로 다른 가치를 지닌 보석의 종류가 주어지고 가방에는 담을 수 있는 무게제한이 있을 때 보석을 최대한의 가치로 가방에다 담는 문제로 많이 출제된다. 즉, 여러 물건이 있을 때 특정한 조건을 만족하는 조합을 구하는 문제이다. 강의에서는 두가지 방법으로 냅색문제를 푸는 방법을 제공한다. 1. 문제 종류나 보석의 종류가 무한개 있을 때는 앞에서부터 해결한다. 2. 개수가 정해져 있을 때, 종류마다 한 개씩 존재, 유한개면 뒤에서부터 해결한다. 강의에 나온 예제를 두가지 방법으로 각각 풀어보자. 1. 동전교환(최소갯수 구하기..
