밤낮개발

🚩 Introduction 스터디 중 코테에 가끔 등장하는 유형인 웹 브라우저 탐색 문제를 풀게 되었다. 구글링을 해도 답이 많지 않고, 푼 사람도 적은 문제라 도움이 될까 싶어 올린다. 📌 문제 https://www.acmicpc.net/problem/23294 23294번: 웹 브라우저 1 첫째 줄에 접속할 수 있는 웹페이지의 종류의 수 N, 사용자가 수행하는 작업의 개수 Q 와 최대 캐시 용량 C 이 순서대로 주어진다.(1 ≤ N, Q ≤ 2,000, 1 ≤ C ≤ 200,000) 둘째 줄에는 N개의 정수 CAPi www.acmicpc.net 📝 설명 간단히 뒤로 가기와 앞으로 가기에 있는 페이지 번호들을 각각 Deque 과 Stack 에 넣어서 풀었다. volume 이라는 변수로 현재 사용되는 캐..

💡Remark DFS 재귀 호출 시 변동이 있는 매개 변수를 넣을 때 주의해야 한다. 그 이유는 재귀 호출을 할 때에는 매번 하나의 root 에서 살을 붙이는 방식을 사용하는데, root 자체에 변화를 주면 안되고 root 에 살을 하나 붙인 값에 대해 재귀 호출하고, 다시 root 그대로에 다른 살 하나를 붙인 값을 재귀 호출하는 식으로 root 에 변화가 생겨서는 안되고 매개 변수에만 변화되는 모양을 추적할 수 있게 넣어주어야 하기 때문이다. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/42839 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 ..

📌 개요 위치에 따라 번호가 매겨져 있는 아파트들의 옥상에 5G 기지국을 설치하려고 한다. 5G 기지국은 기존에 설치되어 있는 4G 기지국과는 전파의 전달 범위가 다르다. 기존에 4G 가 설치되어 있는 아파트들의 목록을 담은 배열 stations 와 총 아파트의 개수 N, 그리고 5G 기지국을 설치했을 때의 전파 전달 범위를 나타내는 W 가 주어졌을 때, 모든 아파트에 전파를 전달하기 위해 설치해야 하는 기지국의 최소 개수를 구하여라. 예) N = 11, stations = [4, 11], W = 1 4번 아파트와 11번 아파트에 전파 전달 범위 1 의 기지국이 설치되어 있으므로, 전파를 전달받을 수 있는 아파트는 위 그림과 같이 3, 4, 5, 그리고 10, 11번 아파트이다. 나머지 1, 2, 6, ..

Longest Common Subsequence(LCS) 동적 계획법을 사용하는 대표적인 알고리즘으로, 문자열 두 개가 주어졌을 때 처음부터 끝 순서로 문자를 뽑아서 만들 수 있는 가장 큰 부분 문자열을 구하는 알고리즘이다. 🔍 동적 계획법 사용 이유 쉽게 생각할 수 있는 가장 큰 부분 문자열을 구할 수 있는 방식 중 하나는 각 문자열에서 부분 문자열을 모두 구한 후 중복되는 부분 문자열 중 가장 큰 문자열을 찾는 방법이다. 이 때 동적 계획법을 사용하면 이전까지의 기록을 참고해서 문자열의 각 문자 하나씩을 검사해 나가기 때문에 연산의 개수가 줄어든다. 💡 Note 부분 문자열을 하나씩 모두 찾아내는 완전 탐색 (Brute Force) 방법을 사용하기 때문에 문자열의 길이가 늘어날 수록 소요되는 시간이 ..

💡 Introduction 우선 직관적으로 문제 설명에 맞게 코드를 짜본다. 이후 리팩토링을 진행한다. 📢 문제 설명 요약 프로그래머스 레벨 3 문제로, 한 번에 하나의 일만 처리할 수 있는 디스크 컨트롤러에 소요 시간이 다양한 요청들이 각각 다른 시간에 들어올 때, 각 작업을 어떤 순서로 처리해야 요청된 작업들이 평균 대기 시간을 최소로 가질 수 있는지를 구하는 문제이다. 🔍 Hint 평균이 최소라는 것은 결국 합이 최소라는 의미이다. 합을 최소화하는 데에 집중해보자. 합이 최소화되기 위해서는 어떻게 해야 할까? 우선 디스크 컨트롤러의 동작 원리에 대해서 알 필요가 있다. 디스크 컨트롤러는 두 가지 일을 반복해서 한다: 모든 요청들을 나열 요청 하나를 선택해 처리 이 반복되는 동작들 중 1번 요청 나열..

💡 Introduction 지난 포스트에서는 예시 그래프를 통해 다익스트라 알고리즘 (Dijkstra's algorithm) 이 어떻게 동작하는지 살펴보았다. 이번 포스트에서는 다익스트라 알고리즘을 실제 프로그래밍 언어를 사용하여 구현할 준비를 한다. 💼 그래프의 표현 가장 먼저, 그래프를 어떻게 표현할지 생각해보자. 일단 각 정점들은 변수를 사용하고, 각 정점들과 그 사이의 거리를 다음과 같은 형식으로 표현할 수 있다: (정점 1, 정점 2, 거리) 그러므로, 지난 포스트에서 사용된 그래프는 중첩 리스트나 배열을 사용하여 다음과 같이 표현할 수 있다: [[A, B, 3], [A, C, 5], [B, D, 4], [C, D, 7]] 막상 이 방식은 A, B, C, D 와 같이 문자열 형태로 정점을 나타내..

💡 Introduction 다익스트라 알고리즘 (Dijkstra's algorithm) 은 탐욕법 (Greedy) 의 대표적인 응용 알고리즘이다. 이번 포스트에서는 다익스트라를 예시 그래프를 통해 설명하고, 다음 포스트와 그 다음 포스트를 이용해 직접 코드로 구현해본다. 🔍 다익스트라 알고리즘이란? 다익스트라 알고리즘은 가중 그래프 (Weighted Graph, 정점간의 거리가 나타나 있는 그래프) 에서 각 정점까지의 최단 거리를 찾아낼 수 있는 알고리즘이다. 바로 예시를 통해 설명하도록 하겠다. 📃 다익스트라 알고리즘 예시 먼저, 아래 사진의 왼쪽에 놓여진 것과 같은 그래프가 있다고 하자. 이 그래프를 분석하여 오른쪽 표에 쓰여진 두 종류의 정보를 파악할 수 있다. A 가 시작점일 때, A 는 자기 자..

에라토스테네스의 체 동작 원리 Introduction 아래 그림과 같이 N 이하의 모든 소수를 찾으려면 2부터 시작해서 모든 숫자의 배수들을 제외하면 된다. 어떤 숫자의 배수라는 것은 합성수이고 소수가 아니라는 의미이기 때문이다. 이 때, 배수를 제외하는 연산은 생각보다 많지 않다. 어차피 작은 숫자부터 시작해서 배수를 지우면 뒤로 갈수록 앞에서 이미 많이 걸러져서 제외할 숫자가 많이 남아있지 않기 때문이다. N 이하의 모든 소수를 에라토스테네스의 체로 걸러서 구하는 순서 1. 사이즈 N 의 배열에 2부터 시작해서 이하의 소수를 모두 구하고 싶은 숫자까지를 모두 넣는다. 주의할 점은 모두 숫자와 일치하는 인덱스에 넣어야 한다는 것이다. (2는 배열의 인덱스 2, 3은 배열의 인덱스 3, .... N 은 ..