명이나물 라이브러리

정렬 알고리즘Arrays.sort, Comparator, 문자열 정렬, 원본 배열 보존까지코딩테스트 문제를 풀다 보면 정렬은 정말 자주 등장한다.처음에는 정렬을 단순히 숫자를 오름차순이나 내림차순으로 나열하는 기능 정도로 생각했다.하지만 문제를 풀다 보니 정렬은 단순한 문법이 아니라, 데이터를 문제 풀이에 유리한 순서로 재배치하는 과정이라는 생각이 들었다.예를 들어 K번째 수를 찾거나, 구간이 겹치는지 확인하거나, 가장 큰 수를 만들거나, 좌표를 압축하는 문제에서도 정렬이 핵심으로 사용된다.이번 글에서는 Java 기준으로 정렬의 기본 문법과 코딩테스트에서 자주 나오는 정렬 유형을 정리해보려고 한다.1. 정렬이란?정렬은 데이터를 특정 기준에 따라 순서대로 배치하는 것이다.가장 기본적인 정렬은 오름차순 정렬..

할인 행사 - 고정길이 슬라이딩 윈도우로 풀기문제를 풀게 된 이유슬라이딩 윈도우를 공부한 뒤, 실제 문제에 적용해보기 위해 프로그래머스의 할인 행사 문제를 풀어봤다.이 문제는 10일 동안 할인하는 상품 목록을 확인해서, 내가 원하는 상품과 수량을 모두 구매할 수 있는 회원가입 날짜의 개수를 구하는 문제다.처음 문제를 봤을 때는 단순히 10일씩 잘라서 확인하면 될 것 같았다.하지만 직접 코드를 작성해보니, 단순 반복보다 고정길이 슬라이딩 윈도우로 푸는 게 더 깔끔하다는 걸 알게 됐다.문제 이해회원가입을 하면 가입한 날부터 10일 동안 할인 상품을 구매할 수 있다.예를 들어 내가 원하는 상품이 다음과 같다고 하자.want = ["banana", "apple", "rice", "pork", "pot"];num..

슬라이딩 윈도우코딩테스트를 준비하면서 이번에는 슬라이딩 윈도우 알고리즘을 공부했다.이름만 들었을 때는 조금 낯설었는데, 개념을 하나씩 정리해보니 생각보다 직관적인 방식이었다.말 그대로 창문을 옆으로 밀듯이, 일정한 구간을 유지하거나 조절하면서 배열이나 문자열을 탐색하는 방법이다.처음에는 투 포인터와 비슷해 보여서 헷갈렸다.특히 left, right를 같이 쓰는 문제들이 많다 보니, 이게 투 포인터인지 슬라이딩 윈도우인지 구분이 잘 안 됐다.공부하면서 내가 이해한 기준은 이렇다.고정 길이 구간 문제는 슬라이딩 윈도우로 접근하기 좋다.가변 길이 구간 문제는 left, right 포인터를 조절하는 투 포인터 방식으로 접근한다.다만 가변 길이 문제도 현재 구간의 상태를 유지하면서 이동하기 때문에,넓은 의미에서는..

투포인터 알고리즘1. 투포인터란?투포인터는 배열이나 리스트에서 두 개의 인덱스, 즉 포인터를 사용해 원하는 조건을 만족하는 값을 효율적으로 찾는 알고리즘 기법이다.보통 left, right 또는 start, end라는 이름의 변수를 사용한다.예를 들어 배열이 다음과 같이 있을 때,int[] arr = {1, 2, 3, 4, 5};두 개의 포인터를 사용해 특정 구간을 살펴보거나, 두 수의 합을 비교할 수 있다.[1, 2, 3, 4, 5] L R여기서 L은 왼쪽 포인터, R은 오른쪽 포인터다.2. 투포인터를 사용하는 이유배열에서 두 수를 고르거나, 연속된 구간의 합을 구하는 문제를 단순하게 풀면 보통 이중 반복문을 사용하게 된다.for (int i = 0; i 이 방식의 시간복잡도는 O(N..

연속된 부분 수열의 합 Java 풀이 — 투포인터로 시간초과 해결하기1. 문제 소개이번에 풀어본 문제는 프로그래머스 Lv.2 문제인 연속된 부분 수열의 합이다.문제에서는 비내림차순으로 정렬된 정수 배열 sequence와 정수 k가 주어진다.이때 합이 k가 되는 연속된 부분 수열을 찾아, 해당 구간의 시작 인덱스와 마지막 인덱스를 배열로 반환해야 한다.조건은 다음과 같다.부분 수열의 합은 k여야 한다.합이 k인 부분 수열이 여러 개라면 길이가 가장 짧은 수열을 선택한다.길이도 같다면 시작 인덱스가 더 작은 수열을 선택한다.처음에는 단순히 모든 구간의 합을 구하면 되지 않을까 생각했다.하지만 제한사항을 보고 완전탐색으로는 풀기 어렵다는 것을 알 수 있었다.2. 제한사항 확인문제의 제한사항은 다음과 같다.5 ..

https://www.acmicpc.net/problem/10026문제적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)예를 들어, 그림이 아래와 같은 경우에RRRBBGGBBBBBBRRBBRRRRRRRR적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하..

https://www.acmicpc.net/problem/1049 문제 Day Of Mourning의 기타리스트 강토가 사용하는 기타에서 N개의 줄이 끊어졌다. 따라서 새로운 줄을 사거나 교체해야 한다. 강토는 되도록이면 돈을 적게 쓰려고 한다. 6줄 패키지를 살 수도 있고, 1개 또는 그 이상의 줄을 낱개로 살 수도 있다. 끊어진 기타줄의 개수 N과 기타줄 브랜드 M개가 주어지고, 각각의 브랜드에서 파는 기타줄 6개가 들어있는 패키지의 가격, 낱개로 살 때의 가격이 주어질 때, 적어도 N개를 사기 위해 필요한 돈의 수를 최소로 하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 ..

문제 정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다. 2를 곱한다. 1을 수의 가장 오른쪽에 추가한다. A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자. 입력 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. 출력 A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다. 나의 풀이 풀이1 [BFS] # 10:42 ~ 11:28 A, B = map(int, input().split()) def multipy(x): return x * 2 def append(x): return int(str(x)+"1") from collections import deque q = deque([(A,1)]) r =-1 while..

https://www.acmicpc.net/problem/4796 문제 등산가 김강산은 가족들과 함께 캠핑을 떠났다. 하지만, 캠핑장에는 다음과 같은 경고문이 쓰여 있었다. 캠핑장은 연속하는 20일 중 10일동안만 사용할 수 있습니다. 강산이는 이제 막 28일 휴가를 시작했다. 이번 휴가 기간 동안 강산이는 캠핑장을 며칠동안 사용할 수 있을까? 강산이는 조금 더 일반화해서 문제를 풀려고 한다. 캠핑장을 연속하는 P일 중, L일동안만 사용할 수 있다. 강산이는 이제 막 V일짜리 휴가를 시작했다. 강산이가 캠핑장을 최대 며칠동안 사용할 수 있을까? (1 < L < P < V) 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고..