알고리즘/문제 풀이 썸네일형 리스트형 [백준] 11003 최소값 찾기 java 1. 문제 설명문제 링크2. 접근 방식슬라이딩 윈도우와 자료구조 덱큐를 이용한다. 해당 문제는 데이터의 개수가 이미 10^6이라서 O(n) 안에 문제를 해결 해야한다. 이 문제를 윈도우 안에 있는 값들을 최소값 정렬해서 풀려는 사람들이 있을지 모르는데, 정렬은 O(nlogn)이 들어서 시간초과가 난다.따라서 덱을 이용해 정렬의 효과를 내야한다. 덱큐의 조건은 다음과 같다. 현재 바라보고 있는 값을 덱큐에 넣을 예정이다.(1) 만약 덱큐의 꼬리의 있는 값보다 현재 넣으려고 하는 값이 작으면 꼬리에 있는 값을 제거한다.(2) 어짜피 슬라이딩 윈도우 기준 제일 오른쪽에 있는 값이 더 작다면 그것보다 왼쪽에 있는 값이 클 경우, 쓸모가 없다. 어짜피 슬리이딩 윈도우가 이동하는 내내, 현재 원소보다 상대적으로 왼.. 더보기 [백준] 1377 버블소트 JAVA 1. 문제 설명문제 설명2. 접근 방식해당 입력 값들로 오름차순 버블 정렬을 했을 때, 과연 외곽 Loop 몇 번만에 정렬이 완성될지 횟수를 출력하는 문제이다. 해당 문제를 버블 정렬를 직접 구현해서 푼다면, 데이터 크기가 500,000 이므로, 10^10이 되어 시간초과가 날 것이다. 따라서 다른 방법을 생각해야 한다. 값이 오른쪽에서 왼쪽으로 이동하는 것은 외곽 Loop 한 번당 최대 한 번 일어난다. 우리는 현재 조회 중인 원소와 오른쪽편 원소를 비교해서 왼쪽이 더 크면 자리를 바꾼다. 따라서 왼쪽에서 오른쪽 이동은 한번의 외곽 Loop 당 N번이 일어날 수 있지만, 오른쪽에서 왼쪽 이동은 한 번의 외곽 Loop 당 최대 1번이 일어난다. 이것을 이용해서 문제를 풀면 된다.제일 많이 오른쪽에서 .. 더보기 [백준] 17298 오큰수 JAVA 1. 문제 설명문제 링크2. 접근 방식0. 사전 세팅Node Class : 멤버 변수로 index와 value를 가지고 있다. index는 입력에서 해당 값이 나온 순서를 저장하고, value는 실제 값을 저장한다. NGE 배열 : index에 해당하는 입력 값의 오큰수가 무엇인지 저장한다. top : stack을 배열로 구현하였기 때문에 top이 어디인지 알려줄 변수로 사용했다. 1. 원리stack이 비어있으면 현재 조회 중인 입력값을 넣는다. stack이 비어있지 않은 경우 stack.top과 현재 조회 중인 입력값(A)를 비교한다.stack.top stack.top의 오큰수는 A이므로 NGE 배열의 top의 index에 A를 저장한다.stack.top의 오큰수는 정해졌음으로 pop하고, 그 다음.. 더보기 [백준] 11399 ATM 1. 문제 설명문제 링크2. 접근 방식삽입 정렬을 이용하여 문제를 풀어보았다.정렬된 영역에서 현재 값을 삽입할 위치 선택을 위해 단순 반복문을 사용하는 것보다 이진 탐색을 사용하는 것이 그나마 시간이 빠를 것 같아서, 이진 탐색을 이용했다.이진 탐색에서 중간 값보다 작았을 시, 클 시 start나 end에 그냥 mid를 더해줘서 무한 Loop에 빠지는 실수를 범했다.start = mid +1, end = mid -1로 해주어서 start= 0, mid = 1인 경우를 대비해줘야 한다. 3. 코드 분석import java.io.*;import java.util.ArrayList;import java.util.StringTokenizer;public class Main { public static vo.. 더보기 [백준] 1253 좋다 1. 문제 분석[문제 링크](https://www.acmicpc.net/problem/1253)2. 접근 방식배열의 양 끝에 포인터를 둔다. 현재 Good이 되는 수인지 검산 한다. (포인터 2개의 합이 현재 검산 중인 수보다 크면 오른쪽 포인터를 한 칸 내린다.) (포인터 2개의 합이 현재 검산 중인 수보다 작으면 왼쪽 포인터를 한 칸 올린다.)숫자는 음수도 가능하므로, 제약없이 전체에 대해서 계산 해야한다. 이는 O(n^2)의 시간 복잡도가 들지만, 계산해야할 총 데이터 수가 2000 이므로 10^3 이라 계산이 괜찮다. 3. 코드 분석import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;im.. 더보기 [백준] 2018 수들의 합 5 Java 풀이 1. 문제 설명[문제 링크](https://www.acmicpc.net/problem/2018)2. 접근 방식투포인터 문제 투 포인터 구간 안에 합을 변수 acc에 저장한다.acc acc > N 이면 왼쪽 포인터를 한 칸 움직여서 그 값을 acc에 더한다. 이렇게 오른쪽 포인터가 구간의 맨 끝에 도달할 때까지 반복하며 acc == N 인 경우를 센다.3. 코드 분석 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { public static void main(String[] args) throws IOException { BufferedRead.. 더보기 [백준] 11659 구간 합 구하기 4 쉬운 풀이 여러가지 풀이 java 1. 문제 설명문제 링크2. 접근 방식해당 문제는 주어지는수의 개수가 10^5 개이다. 이는 n^2만 해도 1억 번의 계산을 넘어서, 시간초과가 날 것이다. 만약 값을 입력 받으면서, 그 전에 받았던 입력들을 일일히 조회하여 구간합을 구한다면, 이는 n^2로 시간 초과가 난다. 누적 합 배열을 이용해 구간 합을 O(1) 안에 구한다.sum[] 이라는 배열을 만든다. sum[i]는 sum[0] ~sum[i]까지의 합이다.sum[i] = sum[i-1] + arr[i] (현재값) 으로 구할 수 있다. i ~ j 까지의 구간합을 구해야할 경우 (i 3. 코드 분석import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream.. 더보기 [백준] 구간 합 구하기 5 쉬운 풀이, 여러가지 풀이 java 1. 문제 설명문제 링크2. 접근 방식sum[i] [j] = (0,0) ~ (i,j) 까지의 합으로 나타냈다.i = 0 인 열은 이전 행의 최대 값을 저장하도록 해서, 누적합이 계속 이어지도록 만들었다.하지만 구간 합 (a,b) ~ (c,d)를 구하라 함은, a 그래서 나는 다음과 같이 구했다.다음과 같이 푸른색 형광펜에서 보라색 형광펜 값을 빼주고 그 결과들을 더 했다.3. 코드 분석import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { public static void main(String[] ar.. 더보기 이전 1 2 3 4 ··· 16 다음
