알고리즘(6)
-
BOJ 19566) c++ 수열의 구간 평균
시간 제한 - 1s 메모리 제한 - 256MB 풀이 1. 부분 수열의 합 / 부분 수열의 길이 = 해당 부분 수열의 평균임을 이용해 풀이 (N까지의 누적합 / N = 평균) 2. (N까지의 누적 합 - x까지의 누적 합) / (N - x) = x부터 N까지의 평균 인덱스 0 1 2 3 4 5 6 배열 1 1 1 1 1 1 누적합 0 1 2 3 4 5 6 평균 0 1 1 1 1 1 1 위 테이블에서 6까지의 평균은 당연히 1이다. 만일 찾으려는 값이 1이라면, 이를 만족하는 구간은 모든 구간인 N * (N + 1) / 2인 21이 나와야 함(1:1, 1:2, 1:3, 1:4, 1:5, 1:6, 2:2, 2:3 ••• 6:6) 3. 누적합을 구하고 평균을 계산해 해당 값이 나온 횟수를 구해준다. 4. 평균을..
2023.01.21 -
BOJ 2629) c++ 양팔 저울
시간 제한 - 1s 메모리 제한 - 128MB 풀이 1. 구슬과 추를 활용해 무게를 재는 방법 1.1) 그림 1을 식으로 나타내면 구슬 + 추a + 추b == 추x + 추y ?로 표현 가능 1.2) 그림 2를 식으로 나타내면 구슬 == 추x + 추y ?로 표현 가능 -> 방정식의 성질을 이용해 1.1의 식을 구슬 == 추x + 추y - 추a - 추b와 같이 나타냄으로 두 식을 같게 생각할 수 있음 2. 1번의 추1부터 추n까지의 조합을 이용해 만들 수 있는 무게 중 구슬의 무게가 있으면 비교 가능하다고 판단 가능 입력 추의 수 N, N개의 추 구슬의 수 M M개의 구슬 자료구조 dp 테이블을 만들까했지만 추를 이용해 만들 수 있는 무게의 집합을 표현하기에 set 자료구조가 좋다고 판단함 추n-1개의 se..
2022.12.23 -
BOJ 1332) c++ 풀자
시간 제한 - 2s 메모리 제한 - 128MB 풀이 1. 처음에는 무조건 1번을 풀어야 함 2. 최소, 최대 값의 차이가 각 단계의 해가 되기 때문에 Memorization을 사용이 어려움 ex) 10 5 15 0 20 ...의 경우, 10 다음에 5/ 15 어떤 문제를 푸는 것이 최적인지 알기 어렵다. 각 단계까지의 depth, 최대 값, 최소 값을 기준으로 기록하면 최대 1000 * 1000 * 50의 3차원 벡터가 생겨 128MB 메모리를 초과함 3. 따라서 brute force로 진행하되 백트래킹 최적화로 덜 계산하는 편이 좋겠다고 생각함 입력 총 문제의 갯수(N)와 최대-최소 간 기준 값(V) 흥미도 X0 X1 X2 .. Xn 자료구조 각 문제의 흥미도를 담기 위한 int형 배열 로직 1. 맨 ..
2022.12.21 -
BOJ 11666) 워크스테이션 배정
시간 제한 - 10s 메모리 제한 - 256MB 풀이 기본적인 개념은 잠금해제를 하지 않고 사용할 수 있는 컴퓨터를 pool로 관리한다는 개념에서 시작 컴퓨터의 사용 종료와 종료 후 락이 걸리는 시간을 오름차순으로 관리한다. 이미 락이 걸린 컴퓨터는 항상 다시 잠금을 해제해야하기 때문에 연구원의 입실 시간을 기준으로 이미 락이 걸린 컴퓨터는 전부 관리 목록에서 제거해준다. 만약 종료가 된 이후의 컴퓨터이고 연구원의 시작시간이 락이 걸리기 전이라면 해당 컴퓨터는 잠금을 다시 해제하지 않고 절약할 수 있다. 입력 연구원의 수 n과 사용 종료 후 잠금이 걸리는 시간까지의 길이 m이 입력되고 연구원의 입실과 입실 이후 사용 시간이 n회 입력된다. 자료구조 연구원의 입장 시간과 사용 시간을 입력받을 형 배열 먼저..
2022.09.23 -
CS 50 - 컴퓨터 과학과 컴퓨팅 사고
컴퓨터 과학이란 무엇인가? 컴퓨터 과학이란 문제 해결에 대한 학문으로, 정보 자체보다는 정보의 수집, 전달, 축적, 가공 등에 대해 다루는 기계, 즉 컴퓨터를 다루는 학문이다. 실생활에서 컴퓨터 과학과 컴퓨터 공학에 대해 헷갈려하는 사람들이 많은데, 컴퓨터 과학은 응용수학과 전산학 이론 등 자연 과학의 Theory를 다루는 학문이라면, 컴퓨터 공학은 그 Theory를 이용해 실제 application을 만들어내는 학과라고 생각하면 쉽다. 컴퓨팅 사고 binary, 2진법 만약 당신이 "123"이라는 글자를 본다면 본능적으로 백의 자리 1, 십의 자리 2, 1의 자리 3이라는 계산을 해서 10진수 123으로 읽을 것이다. 당신도 모르는 사이 100 * 1 + 2 * 10 + 3 * 1 => 100 + 20..
2021.07.16 -
42CURSUS) push_swap (과제 정리)-1
What Push Swap push swap은 껨이당. a, b 두 개의 스택을 가지고 시작하며, a에는 중복되지 않는 양 || 음수를 담고 b는 비워둔다. 목표는 a스택에 오름차순(작은 수부터 큰 수로)으로 정렬하는 것이다. 게임은 아래의 동작들로 수행됨 sa : a의 첫 번째 값과 두 번째 값 교체(값이 하나거나 없으면 동작하지 않음) sb : b의 첫 번째 값과 두 번째 값 교체(값이 하나거나 없으면 동작하지 않음) ss : sa & sb pa : b의 가장 앞의 요소를 a에 push 해줌.(b가 없으면 동작 X) pb : a의 가장 앞의 요소를 b에 push 해줌.(a가 없으면 동작 X) ra : a의 모든 요소를 1만큼 앞으로 이동 시키고, 맨 위의 값을 맨 뒤로 넘긴다. rb : b의 모든 요..
2021.07.15