코딩테스트

백준 11720 문제해당 문제에서 입력되는 수의 최대 자리수가 100이다.만약 100자리의 수가 입력된다면 int형이나 long형으로는 해당 값을 담을 수 없다.따라서 String형으로 수를 받는다.split("") 메서드로 입력 받은 수를 각각의 숫자로 나누어 문자열

백준 1546 문제해당 문제는 모든 점수를 최대 점수로 나누고 100을 곱한 다음에 평균을 구하는 문제이다.위의 평균을 구하는 식은 (전체 점수의 합) × 100 ÷ 최대점수 ÷ 과목 수로 바꿀 수 있다.과목 수를 입력 받는다.과목 수만큼 반복문을 돌면서 각 점수를 입

백준 11659 문제한 줄에 최대 10만개의 많은 숫자가 들어올 수 있기 때문에 BufferedReader와 StringTokenizer를 사용0번째 인덱스를 없는 거라 생각하고 합 배열의 크기를 +1하여 선언한다.이전 합 배열 인덱스의 값과 현재의 값을 더하여 합 배

백준 2018 문제최대 n의 수 10,000,000 제한 시간은 2초로 O(n log n)은 시간 초과가 나기 떄문에 O(log n) 혹은 O(n)을 사용해야 한다.연속된 값의 합이기에 O(n)의 시간 복잡도를 가진 투 포인터 알고리즘을 사용한다.n도 연속된 값의 합이

백준 1940 문제배열의 값이 유니크하고, 사용된 값은 더 이상 사용하지 못한다면, 배열의 양 끝에 포인터를 두는 투포인터 알고리즘을 사용할 수 있다.투포인터 알고리즘은 O(n)의 시간 복잡도를 갖지만, 정렬이 필요하기에 정렬할 값들의 O(n log n)의 값을 확인한

백준 12891 문제배열을 한 칸씩 이동하면서 같은 길이의 배열의 값들을 비교하기에 O(n) 시간 복잡도를 가진 슬라이딩 윈도우 알고리즘을 사용하는 것이 적합하다.필요한 DNA 문자 최소 개수를 담는 checkArr 배열을 선언한다.현재 윈도우의 DNA 문자 개수를 담

백준 1874 문제입력된 수열이 스택 구조에 맞는지 확인하는 문제이다.수열의 개수를 입력받아 n 변수에 담는다.수열을 담을 수 있는 배열을 n의 크기만큼 선언한다.스택 구조에 맞는지 확인하기 위해 빈 스택을 생성한다.오름차순으로 스택에 값을 넣기 때문에 초기값인 num

백준 2164 문제이 문제는 Queue 자료구조에 대한 이해만 있으면 쉽게 해결할 수 있는 간단한 문제이다. 앞쪽으로만 값을 뺴고, 뒤쪽으로만 값을 더하기 때문에 선입선출(FIFO) 구조의 Queue 자료구조를 사용하면 된다.Scanner를 통해 n의 값을 입력 받는다

백준 11286 문제해당 문제는 우선순위 큐의 비교자를 수정하여 조건에 맞는 우선순위 큐를 구현할 수 있으면 해결할 수 있는 문제이다.Scanner를 통해 연산 횟수 n를 받는다.우선순위 큐를 생성하는데 매개변수로 Comparator 람다를 전달한다.Comparator

백준 10811 문제이 문제는 투포인터 알고리즘을 이용하여 주어진 범위의 양 끝의 인덱스를 서로 바꿔주고, 범위를 좁혀가면서 바꿔주면 된다.입력받은 범위값인 i와 j는 실제 인덱스보다 1씩 크기 때문에 -1를 해준다.역순으로 배치를 할 떄에 범위 i가 j보다 커질 수

백준 2750 문제해당 문제는 n의 길이가 최대 1000이며, 제한 시간이 2초로 시간 복잡도가 O(n2)인 알고리즘을 사용하여도 충분히 넉넉한 문제이다.시간 복잡도가 O(n2)인 버블 정렬을 사용해보았다.Scanner를 통해 입력될 수의 개수를 n으로 받는다.n만큼의

백준 1427 문제주어진 수의 각 자리수를 내림차순으로 정렬하는 문제인데 최대값이 10자리이기에 시간 복잡도O(n2)을 사용해도 무당하기에 선택 정렬을 사용해서 풀어보겠다.문자열로 주어진 수를 받는다.문자열 길이만큼 정수 배열을 만들다.substring(i, i + 1

백준 11724 문제노드의 개수를 n 변수에 담는다.에지의 개수를 m 변수에 담는다.방문 기록을 저장할 booleean형 배열 visited를 생성한다. (0은 사용하지 않을 것이기에 n+1길이로 생성)그래프 데이터의 인접한 노드들을 담을 인접 리스트(ArrayList

백준 2178 문제백준 2178 문제해당 문제의 n과 m의 최댓값은 100이고, 시간 제한은 1초이기에 어떠한 시간 복잡도의 알고리즘을 사용하여도 해결이 가능한 문제이다.따라서, 그래프 완전 탐색 알고리즘 중 DFS나 BFS 둘 중 아무거나 사용해서 풀어도 된다.하지만

백준 1920 문제백준 1920 문제해당 문제는 제한 시간이 1초이며 N의 최댓값이 100,000으로 O(n2) 시간 복잡도의 알고리즘을 사용하면 제한 시간을 초과하기 때문에 그 이하의 시간 복잡도를 사용해야 한다.N과 M이 최댓값이 100,000으로 동일하기 때문에

백준 11047 문제백준 11047 문제해당 문제는 그리디 알고리즘으로 풀 수 있도록 뒤의 동전의 가치가 앞의 나오는 동전의 가치의 배수가 된다는 조건을 부여했다. 즉, 동전을 최소로 사용하여 K를 만들기 위해서는 가장 가격이 큰 동전부터 차례대로 사용하면 된다.동전의

백준 1541 문제백준 1541 문제해당 문제는 주어진 식에 괄호를 사용하여 최솟값으로 만드는 문제이기에 - 뒤에 수들을 괄호로 묶어주면 되는 문제이다.문자열로 받은 식을 expression 변수에 할당한다.\-뒤에 수를 최댓값으로 만들어주기 위해 splie("-")으

백준 1929 문제백준 1929 문제소수 구하기(prime number) 문제는 에라토스테네스의 체의 원리로 쉽게 문제를 해결할 수 있다.자바의 배열의 인덱스는 0부터 시작하기 때문에 배열의 인덱스와 실제의 수를 맞춰주기 위해서 arr 배열의 크기를 n+1로 생성한다.

백준 1707 문제백준 1707 문제해당 문제는 인접한 노드가 같은 집합이면 안되는 이분 그래프인지 확인하는 문제이다.주어지는 그래프가 모두 연결되어있다는 조건이 없기 때문에 모든 노드에 대해 DFS을 통해 인접한 모든 노드를 확인해야 한다.DFS를 수행하다가 방문했던

백준 1717 문제백준 1717 문제해당 문제는 합집합 연산과 두 원소가 같은 집합에 포함되는지 확인하는 연산을 수행하라는 문제인데 두 원소가 같은 집합에 있는지 확인하는 알고리즘인 유니온 파인드를 사용하면 풀 수 있다.노드의 개수와 질의의 개수를 각각 n과 m으로 입

백준 2252 문제백준 2252 문제해당 문제는 학생을 노드로, 키 비교 데이터를 에지라고 생각하고 "답이 여러 가지인 경우에는 아무거나 출력한다." 라는 문장을 보고 위상 정렬이라고 눈치를 챈다면 쉽게 풀 수 있는 문제이다.노드의 수 n과 에지의 수 m을 입력 받는다

백준 11399 문제백준 11399 문제해당 문제는 인출 필요 시간이 짧은 사람순(오름차순)으로 정렬하여 총 인출 소요 시간을 최소로 줄여야한다.최대 1000개의 숫자가 들어올 수 있기 때문에 BufferedReader를 사용한다.사람의 수 n을 입력 받는다.인출 필요

백준 11050 문제백준 11050 문제해당 문제는 조합을 구하는 간단한 문제이며, nCk를 구해주면 된다.조합의 구하는 점화식인 D\[i]\[j] = D\[i - 1]\[j - 1] + D\[i - 1]\[j]를 사용하여 배열을 초기화 해주면 간단하게 풀 수 있다.행

백준 11726 문제백준 11726 문제해당 문제는 예시로 5개의 직사각형을 이용하여 타일을 채우는 방법을 보여준다. 이는 4개의 직사각형을 이용하여 타일을 채우는 방법에서 마지막에 직사각형을 하나 더 붙인 것과 동일하다. 그리고 4개의 직사각형으로 타일을 만드는 경우

백준 11660 문제백준 11660 문제해당 문제는 시간 제한 1초 안에 주어진 구간의 합을 구해야 한다.하지만 최악의 경우 n이 1024이고, m이 10만인 경우 2차원 배열은 이중 반복문으로 탐색을 해야 하기 때문에 n2 = 약 100만 \* 10만을 해야하기 때문

백준 10986 문제백준 10986 문제해당 문제는 연속된 부분 구간의 합이 m으로 나누어 떨어지는 구간 합의 갯수를 출력하는 문제이다.따라서 주어진 원본 배열의 합 배열에서 m을 나눈다. 나눈 다음에 나머지가 0이라면 처음부터 해당 값까지의 구간 합의 나머지가 0이기

백준 1253 문제백준 1253 문제해당 문제는 어떤 수를 기준으로 두 수의 합을 구해야하는 문제이다.이를 구하기 위해서는 삼중 반복문을 사용해야 하는데, 최악의 경우 n이 2000이면 시간 제한을 초과하게 된다.따라서 어떤 수를 구하는 반복문 안에서 시간 복잡도 O(

백준 11003 문제백준 11003 문제해당 문제는 이동하는 주어진 범위 내에서 최솟값을 구하는 문제이므로 슬라이딩 윈도우 알고리즘을 사용하면 되는 문제인데, 최솟값을 구하기 위해 정렬을 사용하면 시간 복잡도 O(n2 × log n)이 되기 때문에 시간 제한을 초과하게

백준 17298 문제백준 17298 문제해당 문제는 n의 최대 크기가 1,000,000이므로 반복문으로 오큰수를 찾으면 제한 시간을 초과하게 된다. 따라서 여러 아이디어를 생각하다가 스택으로 풀 수 있는 아이디어까지 도출해야 하는데 그 과정이 가장 어렵다.수열 개수 n

백준 1377 문제백준 1377 문제위 문제에서 C++로 작성한 버블 소트 알고리즘은 바깥 루프가 몇 번째 반복을 할 때swap()이 일어나지 않는지 구하는 알고리즘이다. 버블 정렬에서 swap()이 일어나지 않았다는 것은 정렬이 완료됐다는 뜻이다.그래서 해당 문제는

백준 11004 문제백준 11004 문제해당 문제는 n의 최대값이 5,000,000으로 시간 복잡도 O(n2)을 갖는 버블 정렬, 선택 정렬, 삽입 정렬을 사용하면 시간 초과가 된다.따라서 이 문제는 시간 복잡도 O(n log n)을 갖는 퀵 정렬을 사용하겠다. 그리고

백준 2751 문제백준 2751 문제해당 문제는 n의 최댓값이 1,000,000으로 시간 복잡도 O(n2)를 갖는 버블 정렬, 선택 정렬, 삽입 정렬을 사용할 경우에 시간이 초과한다. 따라서 투 포인터 개념을 사용하여 두 그룹을 병합하여 정렬하는 병합 정렬 알고리즘을

백준 1517 문제백준 1517 문제해당 문제는 버블 정렬을 할 때의 swap이 몇 번이 발생하는지 알아내는 문제이지만, n의 최댓값이 500,000으로 시간 복잡도가 O(n2)인 버블 정렬을 사용할 경우에 시간이 초과된다.따라서, 시간 복잡도가 O(n log n)인

백준 10989 문제백준 10989 문제해당 문제는 n의 최대 개수가 10,000,000으로 매우 크기 때문에 O(n log n)보다 더 빠른 알고리즘이 필요하다. 문제에서 주어지는 숫자의 크기가 10,000보다 작다는 것을 바탕으로 O(kn)의 시간 복잡도의 기수 정

백준 2023 문제백준 2023 문제해당 문제는 일의 자리부터 n의 자리까지의 숫자가 모두 소수로 이루어진 수를 구하는 문제이다.문제의 예시처럼 n이 4일 경우에 일의 자리 중에 소수인 2를 기준으로 2를 십의 자리로 갖는 수 중에 23이 소수이다.그리고 23을 백의

백준 13023 문제백준 13023 문제해당 문제는 모든 노드에 대해서 dfs를 수행하면서 재귀 호출마다 깊이를 더해서 깊이가 5가 되면 1를 출력하고 모든 노드를 돌아도 1이 출력되지 않으면 0을 출력하는 문제이다.노드 개수 n가 에지 개수 m을 입력 받아서 저장한다

백준 1260 문제백준 1260 문제해당 문제는 같은 그래프를 두고 DFS(깊이 우선 탐색), BFS(너비 우선 탐색)을 진행했을 때 각 탐색에 따른 방문 순서를 출력하는 문제이다.노드 개수를 n에 저장한다.에시 개수를 m에 저장한다.시작점을 v에 저장한다.그래프 데이

백준 1167 문제백준 1167 문제해당 문제는 주어진 트리의 지름(가장 긴 거리)를 구하는 문제이다.임의의 노드를 기준으로 가장 긴 노드는 BFS를 통해 구할 수 있는데, 이렇게 구한 노드는 트리의 지름을 구성하는 두 노드 중 하나이다.따라서, 임의의 노드에서 가장

백준 2343 문제백준 2343 문제해당 문제는 블루레이의 크기가 모두 같고 녹화 순서가 바뀌지 않아야 하므로 문제 조건이 이진 탐색 알고리즘을 선택하는 것이 좋다.블루레이에 첫 레슨부터 미자막 레슨까지 차례대로 저장하다 보면 저장한 블루레이 크기로 모든 레슨을 저장할

백준 1300 문제백준 1300 문제해당 문제는 이진 탐색으로 중앙값보다 작은 수의 개수를 세면서 범위를 절반씩 줄이는 방법으로 Bk값을 구하면 된다.다시 말하면 작은 수의 개수가 k - 1개인 중앙값이 정답이다.작은 수의 개수를 세는 아이디어가 이 문제를 푸는 열쇠이

백준 1715 문제백준 1715 문제해당 문제는 카드 묶음의 카드의 개수가 작은 순서대로 먼저 합치는 것이 전체 비교 횟수를 줄일 수 있는 방법이다.현재 데이터 중 가장 작은 카드의 개수를 가진 묶음 2개를 뽑아야 하고, 이 2개를 합친 새로운 카드 묶음을 다시 데이터

백준 1744 문제백준 1744 문제해당 문제는 가능한 한 큰 수들끼리 묶어야 결괏값이 커진다는 것을 알 수 있다.또한 음수끼리 곱하면 양수로 변하는 성질을 추가로 고려해 문제를 푸는 것이 좋다.수의 개수를 n으로 입력 받아 저장한다.양수를 저장할 그룹을 plusQue

백준 1931 문제백준 1931 문제해당 문제는 1개의 회의실에서 회의가 겹치지 않게 최대한 많은 회의를 배정해야 한다. 이떄 그리디 알고리즘을 사용할 수 있는데, 현재 회의의 종료 시간이 빠를수록 다음 회의와 겹치지 않게 시작하는 데 유리하다.그렇기 때문에 종료 시간

백준 1456 문제백준 1456 문제해당 문제는 최대 범위에 해당하는 모든 소수를 구해 놓고, 이 소수들이 입력된 A와 B 사이에 존재하는지 판단해 문제를 해결할 수 있다.입력에서 주어진 범위의 최댓값 1014의 제곱근인 107까지 소수를 탐색해야 한다.에라토스테네스의

백준 1747 문제백준 1747 문제해당 문제는 에라토스테네스의 체를 이용해 최대 범위에 해당하는 모든 소수를 구해 놓은 후 이 소수들의 집합에서 n보다 크거나 같으면서 펠린들모 수인 것을 찾아내면 되는 문제이다.펠린드롬 수를 판별하기 위해 소수의 값을 char 배열

백준 1016 문제백준 1016 문제해당 문제는 min의 값이 1,000,000,000,000으로 매우 큰 것 같지만 실제로 min과 max 사이의 수들 안에서 구하는 것이므로 1,000,000의 데이터만 확인하면 된다.제곱수 판별을 일반적인 반복문으로 구하면 시간 초

백준 11689 문제백준 11689 문제해당 문제에서 요구하는 GCD(n, k) = 1을 만족하는 자연수의 개수가 바로 오일러 피 함수의 정의이다. 즉, 오일러 피 함수를 잘 구현할 수 있는지 묻는 문제이다.어떤 수를 입력 받아 n에 저장한다.결괏값 result에 n을

백준 1934 문제백준 1934 문제최소 공배수는 A와 B가 주어졌을 때 A \* B / 최대 공약수를 계산하여 구할 수 있다. 결국 이 문제는 유클리드 호제법을 이용해 최대 공약수를 구한 후 두 수의 곱에서 최대 공약수를 나눠 주는 것으로 해결할 수 있다.테스트 케이

백준 1850 문제백준 1850 문제백준 1850 문제 예제해당 문제는 예제 입력 3과 같이 입력값이 크면 단순한 방법으로 최대 공약수를 찾기 어렵다. 하지만 예제를 잘 보면 규칙을 찾을 수 있는데, a와 b의 자릿수 차이만큼 1를 출력해주면 정답이다.일반적인 출력을

백준 1033 문제백준 1033 문제해당 문제에서는 n-1개의 비율로 n개의 재료와 관련된 전체 비율을 알아낼 수 있다고 한다. 이것을 그래프 관점으로 생각하면 사이클이 없는 트리 구조로 이해할 수 있다.이 내용을 바탕으로 임의의 노드에서 dfs를 진행하면서 정답을 찾