분류 전체보기(196)
-
문자열 탐색 - 가장 짧은 문자거리
문자열 s와 문자 t가 주어졌을 때, 문자열 s의 각 문자가 t와 떨어진 최소거리를 구하는 문제이다. 내 풀이 생각한 풀이 방법은 다음과 같다. 먼저 문자열 s에서 t가 위치한 인덱스를 배열에 저장을 한다. 그리고 문자열을 순회하면서 문자열의 각 문자마다 t의 인덱스가 저장된 배열을 순회하며 인덱스끼리의 차이를 구해 최솟값을 구하는 것이다. function solution(s, t) { const result = []; const tmp = []; [...s].forEach((c, i) => { if (c === t) tmp.push(i); }); [...s].forEach((_, i) => { let min = Number.MAX_SAFE_INTEGER; tmp.forEach((n) => { min =..
2024.01.20 -
구현 - 분수찾기
백준 1193 1/1 1/2 1/3 1/4 1/5 … 2/1 2/2 2/3 2/4 … … 3/1 3/2 3/3 … … … 4/1 4/2 … … … … 5/1 … … … … … … … … … … … 다음과 같이 무한히 큰 배열에서 X가 주어졌을 때, X번째 분수를 구해야한다. 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 가정한다. 무한히 큰 배열이 주어졌기 때문에 배열을 만들어서 푸는 문제가 아니라 규칙을 찾아 수식을 세워 구하는 문제이다. 내가 구해야하는 것을 정리하면 다음과 같다. 1. X가 어느 범위에 속하는지 구해야한다. 1 2 6 7 15 … 3 5 8 14 … … 4 9 13 … … … 10 ..
2024.01.17 -
슬라이딩 윈도우 - 개념정리
슬라이딩 윈도우 슬라이딩 윈도우는 일정 크기의 윈도우를 옆으로 밀면서 결과값을 도출해야할 때 사용하는 알고리즘이다. 백준 21921 찬솔이는 블로그를 시작한 지 벌써 N일이 지났다. 요즘 바빠서 관리를 못 했다가 방문 기록을 봤더니 벌써 누적 방문 수가 6만을 넘었다. 찬솔이는 X일 동안 가장 많이 들어온 방문자 수와 그 기간들을 알고 싶다. 찬솔이를 대신해서 X일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는지 구해주자. 입력 첫째 줄에 블로그를 시작하고 지난 일수 N와 X가 공백으로 구분되어 주어진다. 둘째 줄에는 블로그 시작 1일차부터 N일차까지 하루 방문자 수가 공백으로 구분되어 주어진다. 출력 첫째 줄에 X일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라..
2024.01.16 -
투 포인터 알고리즘 - 개념정리
투포인터 알고리즘 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 목표값을 구하는 테크닉이다. 흔히 2,3,4,5,6,7번 학생을 지목해야 할 때 간단하게 2번부터 7번까지의 학생이라고 부르는 것과 같은 개념이다. 완전탐색으로 구현할 경우 O(n^2)의 시간복잡도를 투포인터를 사용하면 O(n)으로 성능 향상이 가능하다. 1️⃣ 두 배열 합치기 오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램 을 작성하세요. ▣ 입력설명 첫 번째 줄에 첫 번째 배열의 크기 N(1
2024.01.16 -
브루트 포스 - 뒤집은 소수
문제 자체는 간단하다. 배열의 모든 요소를 뒤집어 소수인지 판단하고, 소수이면 출력하는 문제이다. 예를 들어 52라는 값이 들어오게 되면, 25로 뒤집은 다음에 해당 숫자가 소수인지 판단하기 위해서 1부터 25까지 차례대로 25에 나눈다. 이때 나머지가 0인 수가 존재한다면, 해당 자연수는 25의 약수이다. 최종적으로 1과 자기자신인 25를 제외하고 약수가 존재하게 된다면 25는 소수가 아니게된다. 간단한 이 문제를 정리하는 이유는 바로 순회할 때 1부터 25까지 모두 순회할 필요가 없기 때문이다. 예시를 16으로 바꾸어 설명해보자. 1 X 16 = 16 2 X 8 = 16 4 X 4 = 16 8 X 2 = 16 16 X 1 = 16 약수들의 조합으로 16을 다음과 같이 표현할 수 있다. 이때 4 X 4..
2024.01.15 -
브루트 포스 - 졸업 선물
문제 선생님은 올해 졸업하는 반 학생들에게 졸업선물을 주려고 합니다. 학생들에게 인터넷 쇼핑몰에서 각자 원하는 상품을 골라 그 상품의 가격과 배송비를 제출하라고 했습니다. 선생님이 가지고 있는 예산은 한정되어 있습니다. 현재 예산으로 최대 몇 명의 학생에게 선물을 사줄 수 있는지 구하는 프로그램을 작성하세요. 선생님은 상품 하나를 50% 할인해서(반 가격) 살 수 있는 쿠폰을 가지고 있습니다. 배송비는 할인에 포함되지 않습니다. 문제 설명 ▣ 입력설명 첫 번째 줄에 반 학생수 N(1
2024.01.12