자바

[백준]1874번 스택으로 오름차순 수열 만들기

문제설명 더보기 문제 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다. 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라. 입력 첫 줄에 n (1 ≤ n ≤ 100..

[알고리즘] 슬라이딩 윈도우(sliding window) 알고리즘 이란?

슬라이딩 윈도우 슬라이딩 윈도우 알고리즘은 연속되는 투 포인터와 알고리즘과 유사하지만 부분 배열의 길이가 고정적이다. 고정적인 틀을 오른쪽으로 밀어 오면서 틀 안에 있는 값들을 부분배열이라고 생각하면 된다. 투 포인터 알고리즘은 두 개의 포인터를 이동하기 때문에 2개의 변수가 필요하지만 슬라이딩 윈도우 알고리즘은 부분 배열의 길이를 고정적으로 하기 때문에 1개의 변수만 필요하다. 설명 아래 노란색 칸이 3의 고정길이를 가지는 부분 배열이라 가정, 주어진 문제가 부분 배열의 합을 구하는 것이라 하면 오른쪽으로 한 칸 옮기더라도 옮기기 전 부분 배열과 옮기고 난 후에 겹치는 부분이 존재한다. 즉 기존 구간에서 빠지게 되는 가장 왼쪽 칸의 값은 삭제하고 새 구간에 포함되는 값을 추가하면 된다. 예시 2가지 긴..

[백준] 1253번 '좋은 수' 구하기

문제설명 더보기 문제 N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다. N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라. 수의 위치가 다르면 값이 같아도 다른 수이다. 입력 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) 출력 좋은 수의 개수를 첫 번째 줄에 출력한다. 문제풀이 시간복잡도 N의 최대 개수가 최대 2000이라 가정해도 좋은 수 하나를 찾는 알고리즘의 시간복잡도는 N^2보다 작아야 한다. 따라서 알고리즘의 시간 복잡도는 최소 O(nlongn)이어야 한다. 따라서 투 포인터 알고리즘을 사용하면..

[백준] 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을 입력받아 가지수를 출력하는 프로그램을 작성하시오. 입력 첫 줄에 정수 N이 주어진다. 출력 입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오 문제풀이 package doit_java; import java.io.Buffered..

[알고리즘]Prefix sum 알고리즘이란?

누적합(Prefix sum)란? 나열된 수의 누적된 합을 말한다. 배열의 일부 구간에서 대한 합을 매우 빠르게 구할 수 있게 해준다. N개의 원소로 이루어진 배열이 주어졌을 때 반복문을 통해 부분 배열의 합을 구하려면 O(N)이 걸리는데, 누적합을 이용하면 부분합을 0(N+M)으로 구할 수 있다. 설명 1차원 배열 arr을 순차 탐색하면서 sum 배열을 만들어주면 된다. 활용법 arr의 i항부터 j항 까지 합을 S(i,j)라고 하자. 이때 S(ij) = sum[j] - sum[i-1]이다. S(2,4) = S[4]=S[1]이다. 쉽게 생각하면 참고문제) https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 ..

[JAVA]Call by value와 Call by referenece

함수의 호출 방식에는 Call by value와 Call by reference가 있다. "값에 의한 호출" , "참조에 의한 호출" 차이가 있다. 예제를 통해 알아보자, Call by value package JAVA; public class CallByValue { int value; public static void swap(int x, int y){ int temp =x; x=y; y=temp; } public static void main(String[] args) { int a=10; int b=20; System.out.println("Swap() 호출 전: a=" +a+",b=" +b); swap(a,b); System.out.println("Swap() 호출 후: a=" +a+",b=" ..