코딩 블로그
-
[알고리즘] A* (에이 스타) 알고리즘
오늘 포스팅할 알고리즘은 A* (에이 스타)알고리즘이다,A*(에이 스타)는 그래프의 최단 경로 문제를 해결하는 알고리즘으로 다익스트라 알고리즘을 발전시킨 것 입니다. 다익스트라 알고리즘은 시작점에서 각 정점에 이르는 최단 경로를, 시작점에서 가까운 정점부터 결정한다. 그러다 보니 종점에서 멀어지는 방향에 있는 정점들의 최단 경로도 결정하게 되는데 이 계산은 결국 사용되지 않기 때문에 불필요한 계산이 된다. A*는 이를 방지하기 위한 알고리즘이다. 다익스트라 알고리즘을 잘모른다면 아래의 포스팅을 보고 오는 것을 추천한다. [알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm)오늘 포스팅할 내용은 다익스트라 알고리즘으로 앞서 포스팅했던 벨먼-포드 알고리즘과 마찬가지로 그래프의 최단 경로를 구하..
2025.02.07
-
[알고리즘] 누적합 (Prefix Sum)
누적합(Prefix Sum)은 배열 또는 리스트 등에서 일정 구간의 합을 빠르게 계산하기 위한 방법이면서 동적 계획법(DP)의 형태 중 하나이다.기본적인 방식은 각 요소까지의 누적합을 계산하여 이를 배열에 저장해 두는 것이다. 이후 특정 구간의 합을 구할때 저장해둔 배열을 사용한다. 더보기동적계획법(DP, Dynamic Programming)여기서 동적계획법을 간단히 설명하면 DP, 즉 Dynamic Programming의 줄임말로 기본적인 아이디어는 하나의 큰문제를 여러 개의 작은 문제로 나누어서 해결하고 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것이다.DP는 특정한 알고리즘이 아닌 문제해결 패러다임으로 해당 이름은 큰 의미가 없이 지어졌다고 한다. 누적합 조건 누적합은 배열의 값들이 변..
2025.02.10
-
[C#] List 검색 메서드 (Contains(), Exists(), Find())
C# List는 List에 특정 값이 존재하는지 확인하는 메서드가 여러개 있다.그중 Contains(), Exists(), Find()에 대해 알아보겠다. Contains vs Exists vs Find List.Contains(T)단순히 매개변수의 내용을 포함하는 요소가 List에 있는지 여부를 확인한다.있으면 True, 없으면 False를 반환한다.List.Exists(Predicate)특정 값을 찾기 위한 조건과 일치하는 요소가 List에 포함되어 있는지 여부를 확인한다.있으면 True, 없으면 False를 반환한다.List.Find(Predicate)특정 값을 찾기 위한 조건과 일치하는 요소가 List에 처음으로 검색된 요소를 반환한다.검색되지 않으면 T형식의 기본값이 반환된다.아래 클래스는 이..
2025.01.09
-
[알고리즘] 너비 우선 탐색, BFS(Breadth-First Search) 코드 구현
너비 우선 탐색에 대한 개념은 아래 포스팅을 참조하면 된다. [알고리즘] 너비 우선 탐색 (BFS, Breadth-First Search)이번 포스팅은 그래프를 탐색하는 알고리즘 중 하나인 너비 우선 탐색(BFS)에 대해 알아보려고한다. [자료구조] 그래프 (Graph)그래프라고 하면 원 그래프나 막대 그래프, 혹은 수학의 y=f(x) 그twd0622.tistory.com 너비 우선 탐색은 Queue(큐)를 이용해서 코드로 구현할 수 있다. C# 코드를 통해 BFS를 구현해 보겠다.큐(Queue)를 이용한 반복 구현너비 우선 탐색은 Queue를 이용해서 구현할 수 있으며, 한 정점을 방문하면 인접한 정점을 모두 Queue에 담고 Queue에 담긴 정점을 꺼내 Queue에 담긴 모든 노드를 방문할 때 ..
2025.02.17
-
[C#] 대문자, 소문자로 변환하기 (ToUpper(), ToLower())
1. 문자열 대문자로 변환대문자 변환은 ToUpper 메서드를 사용하면 된다. 2. 문자열 소문자로 변환소문자 변환은 ToLower 메서드를 사용하면 된다.string abc = "abc";abc = abc.ToUpper();Console.WriteLine(abc); // ABCabc = abc.ToLower();Console.WriteLine(abc); // abc 영문을 제외하고 숫자나 다른 문자들은 그대로 나온다.string a11b = "a11b";Console.WriteLine(a11b.ToUpper()); // A11B개인적으로는 회사 업무할 때 사용자들이 입력 값을 이나, 다른 플랫폼에서 가져온 데이터들의 컬럼 이름을 비교 할때 첫글자를 대문자로 한다던가, 전부 대문자로 한다던가, 카멜케이스..
2025.06.19
-
[C#][프로그래머스][Lv2] JadenCase 문자열 만들기
프로그래머스 > 코딩테스트 연습 > 연습문제 > JadenCase 문자열 만들기 https://school.programmers.co.kr/learn/courses/30/lessons/12951 📒 문제JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 단, 첫 문자가 알파벳이 아닐 때에는 이어지는 알파벳은 소문자로 쓰면 됩니다. (첫 번째 입출력 예 참고) 문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는 함수, solution을 완성해주세요. 제한사항s는 길이 1 이상 200 이하인 문자열입니다.s는 알파벳과 숫자, 공백문자(" ")로 이루어져 있습니다.숫자는 단어의 첫 문자로만 나옵니다.숫자로만 이루어진 단어는 없습니다.공백문자..
2024.11.01
-
[C#][프로그래머스 > 코딩테스트 기초] 더 크게 합치기
프로그래머스 > 코딩테스트 연습 > 코딩 기초 트레이닝 > 더 크게 합치기https://school.programmers.co.kr/learn/courses/30/lessons/181939 📒 문제연산 ⊕는 두 정수에 대한 연산으로 두 정수를 붙여서 쓴 값을 반환합니다. 예를 들면 다음과 같습니다. 12 ⊕ 3 = 123 3 ⊕ 12 = 312 양의 정수 a와 b가 주어졌을 때, a ⊕ b와 b ⊕ a 중 더 큰 값을 return 하는 solution 함수를 완성해 주세요. 단, a ⊕ b와 b ⊕ a가 같다면 a ⊕ b를 return 합니다. 제한사항1 ≤ a, b 입출력 예abresult991991898898 입출력 예 설명 입출력 예 #1a ⊕ b = 991 이고, b ⊕ a = 919 입니다..
2024.07.23
-
[자료구조] 그래프 (Graph)
그래프라고 하면 원 그래프나 막대 그래프, 혹은 수학의 y=f(x) 그래프가 생각날 수 있다.하지만 컴퓨터 과학에서 사용하는 그래프는 좀 다르다. 이번 포스팅에서는 컴퓨터 과학에서 말하는 그래프에 대해 알아보도록 하겠다.현재 차근차근 해보자는 생각에 기초 공부를 하는 중이다. 좀 더 자세한 내용은 다른 글에 작성하거나 추후 글을 수정하는 방향으로 작성해 보겠다. 틀린 내용이 있거나 궁금한게 있다면 편하게 댓글 남겨주시면 감사하겠습니다!📝 그래프 개념원으로 그려진 것은 정점 혹은 노드(N, node)라고 한다. 그리고 정점과 정점을 이은 선분을 간선(E, edge)라고 한다.즉, 그래프란 몇개의 정점이 간선으로 연결되어 있는 것을 말한다.💡 그래프 예시그래프를 사용하면 세상의 다양한 것들을 표현할 수 ..
2025.01.15
-
[C#] char에서 int로 변환 (int to char)
1. int형과 연산char를 바로 int형으로 바꿔주면 아스키코드의 인덱스 기준으로 변환 되기 때문에숫자로 된 문자를 int형으로 바꿀때 문자 '0'을 빼주면 된다.char x = '5';int y = x - '0';Console.WriteLine(y); // 5
2024.08.27
-
[알고리즘] 선택 정렬 (Selection Sort)
이번에 공부할 내용은 선택 정렬(Selection Sort)이다.현재 차근차근 해보자는 생각에 기초적인 부분을 공부하고 있다. 좀 더 구체적인 내용은 다른 글에 작성하거나 추후 글을 수정하는 방향으로 해보겠다.틀린 내용이 있거나 궁금한게 있다면 편하게 댓글 남겨주시면 감사하겠습니다.📌 개념선택 정렬(Selection Sort)은 수열에서 최솟값을 찾아서 가장 왼쪽의 숫자와 교체하는 작업을 반복하여 정렬한다.수열에서 최소값을 찾을 때는 선형 탐색을 사용한다. [알고리즘] 선형 탐색 (Linear Search)선형 탐색은 매우 간단한 알고리즘이다.다른 개념을 공부할 때 자주나와서 먼저 공부하려고 한다. 현재 차근차근 해보자는 생각에 기초적인 부분을 공부하고 있다. 좀 더 구체적인 내용은 다른twd0622...
2024.08.13
-
[JAVA][알고리즘] 구간 합
구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 이다. 코딩 테스트에서 사용 빈도가 높기 때문에 알아두면 좋다. 구간 합은 누적합이라고도 하는데, C#으로 누적합을 정리해둔 글이 있으니 참고해도 좋을것 같다.해당 게시글엔 2차원 배열의 누적합도 정리해 두었다. [알고리즘] 누적합 (Prefix Sum)누적합(Prefix Sum)은 배열 또는 리스트 등에서 일정 구간의 합을 빠르게 계산하기 위한 방법이면서 동적 계획법(DP)의 형태 중 하나이다.기본적인 방식은 각 요소까지의 누적합을 계산하여 이를 배twd0622.tistory.com구간 합 이론구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야한다. 배열 arr이 있을 때 합 배열 sumArr은 다음과 같다...
2025.10.21
-
[JAVA] 이차원 ArrayList로 그래프 표현
코딩 테스트 문제에서 그래프 관련 알고리즘이 자주 등장한다. 이때 그래프 구조를 표현 하는데 많이 사용하는 것이 이차원 ArrayList 이다. 이차원 ArrayList의 선언부터 활용하끼 3단계로 나눠 설명하겠다. 그래프의 대한 내용은 아래 포스팅을 참고하면 된다. [자료구조] 그래프 (Graph)그래프라고 하면 원 그래프나 막대 그래프, 혹은 수학의 y=f(x) 그래프가 생각날 수 있다.하지만 컴퓨터 과학에서 사용하는 그래프는 좀 다르다. 이번 포스팅에서는 컴퓨터 과학에서 말하는 그래twd0622.tistory.com01. 이차원 ArrayList 선언과 초기화그래프의 에지를 표현하는 클래스를 만들어 두었다.class Edge{ int endNode; int value; public..
2025.10.20
-
[디자인패턴] 싱글턴(Singleton) 패턴
싱글턴(Singletion) 패턴은 애플리케이션 전체에서 특정 클래스의 인스턴스가 오직 하나만 존재하도록 보장하는 디자인 패턴이다.싱글턴 패턴 예시아래의 예시는 웹API를 호출하는 기능의 일부로, 싱글톤으로 해당 기능을 호출하게 만들었다.public class WebApi{ private static readonly WebApi _oInstance = new WebApi(); public static WebApi Instance { get { return _oInstance; } }} private static readonly WebApi _oInstance = new WebApi();static: _oInstance가 특정 객체 인스턴스에 속하지 않고, WebA..
2025.09.29
-
[알고리즘] 구현 (Implementation)
구현 알고리즘(Implementation Algorithm)이란, 어떤 특별한 공식이나 방법이 아닌 코딩테스트 문제 해결을 위한 개념으로, 단순히 머릿속에 있는 알고리즘을 소스코드로 풀어내는 과정을 말한다. (Problem-Thinking-Solution) 어떤 문제를 풀든 소스코드를 작성하는 과정은 필수이기 때문에 대부분의 알고리즘 문제가 '구현 문제'이다. 그 중 구현이 어렵거나 초점에 맞춰져있는 문제들이 있다. 즉, 풀이를 떠올리는 것이 쉽지만 소스코드로 옮기기 어려운 문제가 구현문제 라고 생각하면 된다. 예시실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제문자열을 특정한 기준에 따라서 끊어 처리해야하는 문제적절한 라이브러리를 찾아서 사용해야 하는 문제알고리즘은 간단한데, 코드가 길어지..
2025.02.11
-
[C#] 열거형 Enum
열거형 Enum열거형은 서로 관련 있는 상수들의 집합을 정의한 것 이다. 숫자에 특정한 명칭을 붙여주어 의미를 쉽게 이해할 수 있게 하는 용도로 사용된다. 예를 들어 프로그램에서 사과, 바나나, 오렌지의 세 과일을 사용하고 싶은데 각각 0, 1, 2라는 숫자를 부여한다면 나중에 1이 무엇을 의미하는지 이해하기 어려울 수 있다. // 0 == apple, 1 == banana, 2 == orangeint[] fruit = { 0, 1, 2 }; 이럴 때 enum을 사용하면 보기 편한 코드를 작성할 수 있다.enum Fruit{ apple, // 0 banana, // 1 orange // 2}enum 사용법enum은 기본적으로 위에 Fruit 예시 처럼 enum 이름 { } 형태로 중..
2024.12.16
최신 글
-
[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
