본문 바로가기

PS

[프로그래머스] 크기가 작은 부분 문자열 링크 문제 설명 입력으로 숫자로 이루어진 문자열 t와 p가 주어진다. t에서 p와 같은 길이의 부분 문자열들 중 p 보다 작은 수의 갯수를 구하는 문제이다. 제한사항 def solution(t: str, p: str) -> int: ... 1 ≤ p의 길이 ≤ 18 p의 길이 ≤ t의 길이 ≤ 10,000 t와 p는 숫자로만 이루어진 문자열이며, 0으로 시작하지 않습니다. 풀이 제한사항도 단순한 문제이다. 길이가 len(p)인 부분 문자열을 모두 구해 비교하면 된다. 제출 코드 def solution(t: str, p: str) -> int: return len([True for i in range(len(t) - len(p) + 1) if t[i:i + len(p)]
[프로그래머스] 숫자 변환하기 링크 문제 설명 입력으로 1 이상의 정수 x 와 y 가 주어진다. 주어진 아래 연산으로 x를 y로 만든다. x에 n을 더합니다 x에 2를 곱합니다. x에 3을 곱합니다. x를 y로 변환하는 최소 연산 횟수를 구한다. 변환할 수 없다면 -1을 반환한다. 제한사항 def solution(x: int, y: int, n: int) -> int: ... 1 ≤ x ≤ y ≤ 1,000,000 1 ≤ n < y 풀이 DP를 응용해 풀었다. 크기가 y+1인 배열을 만들어 INF로 초기화한다. +1은 직관적으로 값과 인덱스를 일치시키기 위함이다. 각 배열의 원소는 해당 인덱스까지 연산을 수행한 횟수를 나타낸다. 문제 입력으로 주어진 x=10, n=5, y=40을 예시로하면 아래 그림과 같다. 시작점인 DP[x] 는 ..
[프로그래머스] 호텔 대실 링크 문제 설명 입력으로 [입실 시간, 퇴실 시간] 쌍으로 이루어진 리스트가 주어진다. 예약 시간동안 그 방은 다른 사람이 사용할 수 없으며 청소시간이 있기 때문에 퇴실시간이 지난 후 10분 뒤에 새로운 손님을 받을 수 있다. 예약 목록이 주어졌을 때 필요한 최소 객실의 수를 구하는 문제이다. 제한사항 def solution(book_time: List) -> int: answer = 0 return answer 1 ≤ book_time의 길이 ≤ 1,000 book_time[i]는 ["HH:MM", "HH:MM"]의 형태로 이루어진 배열입니다 [대실 시작 시각, 대실 종료 시각] 형태입니다. 시각은 HH:MM 형태로 24시간 표기법을 따르며, "00:00" 부터 "23:59" 까지로 주어집니다. 예약 ..
[2156] 포도주 시식 문제 링크 배열에서 아래와 같은 규칙에 따라 수를 선택했을 때 최대값을 찾는 문제이다.포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.연속으로 놓여 있는 3잔을 모두 마실 수는 없다.2번 조건에서의 연속으로 3잔을 모두 마실 수 없다는 것이 중요하다.예시 입력은 6, 10, 13, 9, 8, 1이 주어졌다. 이를 배열로 표현하면 아래와 같다.개발 편의상 배열의 크기를 N+1로 설정했다.dp 배열을 만들어서 i번째 까지 선택한 값의 최대값을 저장한다.dp 배열의 i번째 원소를 업데이트하는 경우의 수는 다음과 같다.i-1과 i를 선택했을 경우i와 i-2를 선택했을 경우i를 선택하지 않을 경우이 세 조건을 통해 연속으로 3개의 수를 선택하지 않도록..
[13397] 구간 나누기2 문제 링크주어진 배열을 M개로 나누었을 때 구간의 점수들의 최댓값의 최솟값을 구하는 문제이다.예를 들어, 배열이 [1, 5, 4, 6, 2, 1, 3, 7] 이고, M = 3인 경우가 있다.이때, [1, 5], [4, 6, 2], [1, 3, 7]로 구간을 나누면 각 구간의 점수는 4, 4, 6점이 된다. 이때, 최댓값은 6점이다.만약, [1, 5, 4], [6, 2, 1], [3, 7]로 구간을 나누었다면, 각 구간의 점수는 4, 5, 4점이 되고, 이때 최댓값은 5점이 된다. 이 문제를 풀기 위해 아래의 방법으로 접근했다.먼저 최솟값을 설정하고, 이 최솟값을 만족하기 위해 배열이 몇 개로 나누어지는지 구한다.나누어진 배열의 갯수가 M보다 크다면 목표 최솟값을 높이고, M보다 작다면 목표 최솟값을 낮춘..
Overlapped Model 윈도우는 Overlapped I/O 모델을 사용하는데, 운영체제가 직접 입력 데이터를 유저 영역으로 복사하며, 복사가 완료된 시점에 통지를 해준다. 이 과정을 자세히 알아보자. 소켓은 기본적으로 블록/동기로 만들어진다. 여기서 데이터 입출력을 수행하는 동안 블록이 발생한다. 블록/논블록, 동기/비동기에 관한 설명은 링크를 참고. 이 모델로는 하나의 쓰레드에서 두 개 이상의 소켓을 다루기 힘들다. 하나의 소켓으로 데이터 입출력을 처리하는 동안 블록 되어 대기상태가 되기 때문이다. 이 모델을 사용하면서 두 개 이상의 소켓을 다루기 위해서는 멀티 쓰레드 기술을 사용해야 한다. 이 문제는 입출력 모델을 블록/비동기 또는 논블록/비동기를 사용하여 해결할 수 있다. 블록/비동기 모델을 사용하는 기술이 select ..
[알고리즘]배열의 부분 최대합 [알고리즘]배열의 부분 최대합주어진 배열에서 연속된 구간 중 합이 최대가 되는 곳을 찾는 문제이다. 다음과 같이 재열이 주어졌을 때, 2 ~ 4 구간의 합이 11로 최대값을 가진다. 이를 찾기 위한 첫 번째 방법은 배열을 순회하며 모든 구간의 합을 구하여 최대값을 찾는 것이다. 이를 코드로 표현하면 다음과 같다.xxxxxxxxxxint sol1(const vector& arr){ int max = INT_MIN; for (int i = 0; i = end) return arr[start];​ int mid = (start + end) / 2;​ //중앙에 걸친 부분합을 구한다. int sum = 0; int left = INT_MIN; for (int i = mid; i >= start; i--) { s..

티스토리툴바