본문 바로가기

ALL

[백준] 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.. 더보기
정렬의 모든 것 (버블, 선택, 삽입) 1. 버블 정렬(1) 정의인접한 원소끼리 비교 후에, 정렬되어 있지 않다면, 두 원소의 위치를 swap한다.이런 식으로 정렬하게 되면 배열 혹은 리스트의 오른쪽부터 값들이 정렬되어 쌓이게 된다.예시 사진 출처: 블로그(2) 시간 복잡도$$O(n^2)$$2. 선택 정렬(1) 정의정렬이 되어있지 않은 범위 내에서의 최소값 혹은 최대값을 맨 오른쪽 혹은 맨 왼쪽으로 몰아넣는다.이후 정렬되지 않은 부분 내의 최소값 혹은 최대값을 다시 찾아 아까 몰아넣은 곳으로 또 몰아넣는다. 밑의 사진은 오름차순 정렬을 선택 정렬로 행한 것이고, 최소값을 오른쪽으로 몰아넣었다.사진 출처: 블로그(2) 시간 복잡도$$O(n^2)$$3. 삽입 정렬(1) 정의정렬된 범위 내에 현재 값을 삽입할 적절한 위치를 찾는다. (오름 차순, .. 더보기
[백준] 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.. 더보기
Java - 배열, ArrayList, LinkedList, Map 완벽 정리! 1. Array(1) 정의번호와 번호에 대응되는 값들로 이루어진 자료구조를 의미한다.번호만 알고 있으면, 해당 번호에 해당하는 값을 O(1)에 조회가 가능하다. (2) 특징ⓐ Index에 해당하는 값에 바로 접근할 수 있다. (값 조회에 빠르다.)ⓑ 배열은 선언할 때, 그 크기가 정해진다. 그 이후, 줄이거나, 늘릴 수 없다.ⓒ 따라서 중간에 값을 삽입하거나 삭제하기가 어렵다. 만약에 그러한 구현이 꼭 필요하다면, 빈 배열을 통해 변경사항이 반영된 배열을 새로 만들어야 한다.(3) 많이 쓰 함수ⓐ Arrays.asList(T..a): 배열을 ArrayList로 변환시켜준다. ⓑ Arrays.toString(): 배열을 문자열 형태로 변경해준다. 문자열 형태: [a,b,c,d...] → 출력할 때 .. 더보기

티스토리툴바