코딩 블로그

최신 글

• [JAVA][백준][G2] 1377번 버블 소트 https://www.acmicpc.net/problem/1377 📒 문제버블 소트 알고리즘을 다음과 같이 C++로 작성했다.bool changed = false;for (int i=1; i A[j+1]) { changed = true; swap(A[j], A[j+1]); } } if (changed == false) { cout 위 소스에서 N은 배열의 크기이고, A는 정렬해야 하는 배열이다. 배열은 A[1]부터 사용한다.위와 같은 소스를 실행시켰을 때, 어떤 값이 출력되는지 구해보자. ● 시간 제한 / 메모리 제한2 초 / 128 MB 입력첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터.. 2025.12.29
• [JAVA][백준][B2] 수 정렬하기 https://www.acmicpc.net/problem/2750 📒 문제N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. ● 시간 제한 / 메모리 제한 1 초 / 128 MB 입력첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.출력첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 입출력 예# 입력1552341# 출력112345 알고리즘 분류구현정렬💻 소스코드import java.io.*;import java.util.*;public class Main { public static void main(Str.. 2025.12.15
• [JAVA][백준][S1] 절댓값 힙 구현하기 https://www.acmicpc.net/problem/11286 📒 문제절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다. 배열에 정수 x (x ≠ 0)를 넣는다.배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.프로그램은 처음에 비어있는 배열에서 시작하게 된다. ● 시간 제한 / 메모리 제한 2 초 / 256 MB 입력첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 .. 2025.12.05
• [JAVA][백준][S4] 카드2 https://www.acmicpc.net/problem/2164 📒 문제N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 .. 2025.12.04
• [JAVA][백준][G4] 오큰수 https://www.acmicpc.net/problem/17298 📒 문제크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다. 예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다. ● 시간 제한 / 메모리 제한 1 초 / 512 MB 입력첫째 줄에 수열 A의 크기 N (1 .. 2025.12.03
• [JAVA][백준][S3] 1874번 스택으로 수열 만들기 https://www.acmicpc.net/problem/1874📒 문제스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다. 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을.. 2025.12.02
• [JAVA][백준][P5] 11003번 최솟값 찾기 https://www.acmicpc.net/problem/11003 📒 문제N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. ● 시간 제한 / 메모리 제한 2.4 초 / 512 MB 입력첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000) 둘째 줄에는 N개의 수 Ai가 주어진다. (-109 ≤ Ai ≤ 109)출력첫째 줄에 Di를 공백으로 구분하여 순서대로 출력한다. 입출력 예# 입력112 31 5 2 3 6 2 3 7 3 5 2 6# 출력11 1 1 2 2 2 2 2 3 3 2 2 알고리즘 분류자료 구조우선순.. 2025.12.01
• [JAVA][백준][S5] DNA 비밀번호 https://www.acmicpc.net/problem/12891 📒 문제평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA”는 DNA 문자열이 아니지만 “ACCA”는 DNA 문자열이다. 이런 신비한 문자열에 완전히 매료된 민호는 임의의 DNA 문자열을 만들고 만들어진 DNA 문자열의 부분문자열을 비밀번호로 사용하기로 마음먹었다.하지만 민호는 이러한 방법에는 큰 문제가 있다는 것을 발견했다. 임의의 DNA 문자열의 부분문자열을 뽑았을 때 “AAAA”와 같이 보안에 취약한 비밀번호가 만들어 질 수 있기 때문이다. 그래서 민호는 부분문자열에서 등장하는.. 2025.11.28
• [JAVA][백준][G4] 1253번 좋아 https://www.acmicpc.net/problem/1253 📒 문제N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.수의 위치가 다르면 값이 같아도 다른 수이다. ● 시간 제한 / 메모리 제한 2 초 / 256 MB 입력첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)출력좋은 수의 개수를 첫 번째 줄에 출력한다. 입출력 예# 입력1101 2 3 4 5 6 7 8 9 10# 출력18 알고리즘 분류자료 구조정렬이분 탐색두 포인터💻 소스코드import j.. 2025.11.25
• [JAVA][백준][S4] 1940번 주몽 https://www.acmicpc.net/problem/1940 📒 문제주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다. 갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을.. 2025.11.06
• [JAVA][백준][S5] 2018번 수들의 합 5 https://www.acmicpc.net/problem/2018 📒 문제어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다. 예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다. N을 입력받아 가지수를 출력하는 프로그램을 작성하시오. ● 시간 제한 / 메모리 제한 2초 / 32MB입력첫 줄에 정수 N이 주어진다.출력입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 .. 2025.11.06
• [JAVA][백준][G3] 10986번 나머지 합 https://www.acmicpc.net/problem/10986📒 문제수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다. 시간 제한 / 메모리 제한 1초 / 256MB입력첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103) 둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109)출력첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다. 입출력 예# 입력15 31 2 3 1 2# 출력17 알고리즘 분류수.. 2025.11.05
• [JAVA][백준][S1] 11660번 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 📒 문제N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.1234234534564567여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오. 시간 제한 / 메모리 제한1 초 / 256MB입력첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 102.. 2025.10.24
• [JAVA][알고리즘] 구간 합 구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 이다. 코딩 테스트에서 사용 빈도가 높기 때문에 알아두면 좋다. 구간 합은 누적합이라고도 하는데, C#으로 누적합을 정리해둔 글이 있으니 참고해도 좋을것 같다.해당 게시글엔 2차원 배열의 누적합도 정리해 두었다. [알고리즘] 누적합 (Prefix Sum)누적합(Prefix Sum)은 배열 또는 리스트 등에서 일정 구간의 합을 빠르게 계산하기 위한 방법이면서 동적 계획법(DP)의 형태 중 하나이다.기본적인 방식은 각 요소까지의 누적합을 계산하여 이를 배twd0622.tistory.com구간 합 이론구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야한다. 배열 arr이 있을 때 합 배열 sumArr은 다음과 같다... 2025.10.21
• [JAVA] 형 변환 String형 → 숫자형(int, double, float, long, short)String sNum = "1234";int i1 = Integer.parseInt(sNum);int i2 = Integer.valueOf(sNum);double d1 = Double.parseDouble(sNum);double d2 = Double.valueOf(sNum);float f1 = Float.parseFloat(sNum);float f2 = Float.valueOf(sNum);long l1 = Long.parseLong(sNum);long l2 = Long.valueOf(sNum);short s1 = Short.parseShort(sNum);short s2 = Short.valueOf(sNum); 숫자형(in.. 2025.10.20
• [JAVA] 이차원 ArrayList로 그래프 표현 코딩 테스트 문제에서 그래프 관련 알고리즘이 자주 등장한다. 이때 그래프 구조를 표현 하는데 많이 사용하는 것이 이차원 ArrayList 이다. 이차원 ArrayList의 선언부터 활용하끼 3단계로 나눠 설명하겠다. 그래프의 대한 내용은 아래 포스팅을 참고하면 된다. [자료구조] 그래프 (Graph)그래프라고 하면 원 그래프나 막대 그래프, 혹은 수학의 y=f(x) 그래프가 생각날 수 있다.하지만 컴퓨터 과학에서 사용하는 그래프는 좀 다르다. 이번 포스팅에서는 컴퓨터 과학에서 말하는 그래twd0622.tistory.com01. 이차원 ArrayList 선언과 초기화그래프의 에지를 표현하는 클래스를 만들어 두었다.class Edge{ int endNode; int value; public.. 2025.10.20
• [JAVA] 다중 조건 정렬 (Comparable, Comparator) 코딩테스트 문제를 풀 때 여러 기준에 따라 데이터를 정렬해야 하는 상황이 나오기도 한다.예를 들어 성적을 정렬할 때 영어 점수를 기준으로 하되, 영어 점수가 같으면 수학 점수를 기준으로 할 수 있다.이때 다중 조건 정렬을 사용하면 여러 기준을 동시에 적용하여 원하는 순서대로 데이터를 정렬할 수 있다. 자바에는 Comparable과 Comparator 인터페이스를 사용하여 다중 조건 정렬을 구현할 수 있다.Comparable 인터페이스영어 점수를 우선 기준으로 하고, 영어 점수가 같을 경우 수학 점수로 정렬하도록 구현한 Comparable 인터페이스 예시이다.public class Score implements Comparable{ int english; int math; public Score(int .. 2025.10.17
• [알고리즘] 나누기 연산의 분배 법칙 코딩 테스트에서 정답의 나머지 값을 요구하는 경우가 종종 있다. 이 문제에는 자료형의 표현 범위를 넘지 않게 유도하고 나머지 연산의 원리를 알고 있는지 묻는 의도가 담겨 있다.나머지 연산은 나눗셈을 제외하고 덧셈, 뺄셈, 곱셉의 분배 법칙이 성립된다.예시 값: A = 20, B = 6, C = 3 ● 덧셈의 분배 법칙 성립 → (A+B) % C == (A%C + B%C) % C(20+6) % 3 = 26 % 3 = 2(20 % 3 + 6 % 3) % 3 = (2+0) % 3 = 2 ● 뺄셈의 분배 법칙 성립 → (A-B) % C == (A%C - B%C) % C(20-6) % 3 = 14 % 3 = 2(20 % 3 - 6 % 3) % 3 = (2-0) % 3 = 2 ● 곱셈의 분배 법칙 성립 .. 2025.10.15
• [알고리즘] 인덱스 해싱 코딩 테스트에서 가장 많이 사용하는 자료구조는 배열이다. 보통 배열을 사용할 때 인덱스로 데이터에 접근한다. 인덱스는 일반적으로 몇번째 데이터인지 나타내는 역할을 한다. 하지만 상황에 따라 인덱스에 해싱(hashing)개념을 적용하여 단순한 위치가 아니라 특정한 의미를 지닌 값으로 활용하면 문제 해결을 더 쉽게 할 때도 있다. arr[1]의 의미몇 번째 데이터인지 순서를 의미하는 경우 → 첫 번째 데이터를 저장숫자값으로 의미를 부여하는 경우 → 1이라는 값이 몇 개 있는지를 저장인덱스 해싱 적용 예시예를 들어 1000보다 작은 자연수 10,000,000개를 1초 안에 정렬해야 하는 상황이라고 가정해보자. 데이터의 양이 많아서 일반적인 방법으로는 1초안에 정렬하기 어렵다.하지만 인덱스를 값 자체로 활용하면.. 2025.10.15
• [알고리즘] 시간 복잡도 알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다. 일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측한다. 어떤 코딩테스트 문제에서 제한시간을 2초로 주어졌다면, 2억 번의 연산안에 해당 문제를 해결해야 한다는 말이다. 시간 복잡도 유형빅-오메가(Ω(n)) : 최선(best case)의 연산 횟수를 나타낸 표기법빅-세타(Θ(n)) : 보통(average case)의 연산 횟수를 나타낸 표기법빅오(O(n)) : 최악(worst case)의 연산 횟수를 나타낸 표기법다음 예시로 0~99 사이의 무작윗값을 찾아 출력한다고 했을때, // 0~99 사이 값 무작위 선택for findNumber = (int)(Math.random() * 100);for(int i = .. 2025.10.14