nsbg 🌞

문제상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.각각의 상담은 상담을 완료하는데 걸리는 기간 $T_{i}$와 상담을 했을 때 받을 수 있는 금액 $P_{i}$로 이루어져 있다.N = 7인 경우에 다음과 같은 상담 일정표를 보자.1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 ..

문제에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.이 알고리즘은 다음과 같다.2부터 N까지 모든 정수를 적는다.아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오. 입출력 예시 풀이에라토스테네스의 체는 굉장히 유명한 유형임에도 불구하고 볼 때마다 새로운 느낌이다. 풀이를 완전히 외워두던가 해야겠다. 아래는 문제를 보고 내 머릿속에 떠올랐던 생각들이다. ◾ 지워진 숫자가 몇 번째인지 세기 위한 변수가 필요함 → cnt 변수 정의 ◾ cnt를 정..

문제크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다. 임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.  예를 들어, 아래와 같은 지..

문제 서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까? 입출력 예시 풀이입출력이 굉장히 간단하고 solved.ac 기준 티어도 높진 않지만 내 기준 흥미로운 문제여서 정리해둔다. 문제와 예시가 짧긴 했으나 이해하는 데에 오래 걸리지는 않았다. 문제를 보자마자 내 머릿속에 떠오른 생각은 아래와 같다. Step. 1) S를 어떻게 구성할 것인가?N을 최대로 만들기 위해서는 작은 수들부터 고려해야 한다. 즉, 몇 개의 숫자를 더해 200을 만드려고 할 때 99, 101 조합보다는 5, 10, 25, ..., 90과 같은 조합이 좋은 것! Step. 2) 작은 수들부터 고려하는 방법은?여기서 DP 개념이 살짝 얹어지게 되는데ㅡ 일단 1부터 순서대로 계속 수를 더해나가는..

문제다솜이는 은진이의 옆집에 새로 이사왔다. 다솜이는 자기 방 번호를 예쁜 플라스틱 숫자로 문에 붙이려고 한다.다솜이의 옆집에서는 플라스틱 숫자를 한 세트로 판다. 한 세트에는 0번부터 9번까지 숫자가 하나씩 들어있다. 다솜이의 방 번호가 주어졌을 때, 필요한 세트의 개수의 최솟값을 출력하시오. (6은 9를 뒤집어서 이용할 수 있고, 9는 6을 뒤집어서 이용할 수 있다.) 입출력 예시 풀이처음에 문제랑 입출력 예시 보자마자 금방 풀 줄 알았는데 또 스스로를 과대평가해버린 것이었음. 질문 게시판과 구글링으로 힌트 얻은 후에야 제출할 수 있었다. 힌트 보면 아~ 하는데 그 과정을 내 힘으로 떠올리는 게 왜이렇게 어려울까 🥲 일단 내가 생각해본 풀이 방식들은 아래와 같다.아이디어 1) 문자열 단순 확인① f..

문제지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 ..

문제 입출력 예시 개인적으로는 '입출력 예 #2'가 까다로웠다 🥲 풀이처음에는 x=s[0]으로 미리 할당해놓고 s[1:]을 for문 돌리면서 문자 하나하나를 x와 비교하는 방식을 썼다. 이 방법으로 하니까 s 길이가 1일 때 인덱스 에러가 계속 떴는데, 인덱스 에러가 도저히 안 잡혀서 아예 생각을 다시 했다. 핵심은 '시작 문자를 정해주지 않는 것'이었다. for문 안에서 x, x_cnt, not_x_cnt 초기화하는 부분이 한 번 더 나오는 게 불편하지만 이건 더 줄일 수가 없는 부분이라서 어쩔 수 없었다. def solution(s): answer = 0 x_cnt = 0 not_x_cnt = 0 x = '' for alphabet in s: i..

문제 입출력 예시 풀이핵심은 양쪽에서 접근할 수 있는 deque을 사용하는 것과 반복문을 빠져나오는 시점을 정해주는 것이었다. 반복문 탈출 조건을 놓치면 무조건 오답이 나오기 때문! ※ 기본 아이디어: 원소 총 합이 큰 리스트에서 작은 리스트로 원소를 옮김 1️⃣ 특정 TC에서 실패한 코드(11번, 28번) 1. 각 queue를 deque으로 바꾸고 리스트 총 합을 미리 구해둔다. 2. sum(queue1), sum(queue2)을 비교하면서 큰 곳에서 작은 곳으로 값 이동 → 큰 곳에서 popleft()3. 값이 이동할 때마다 cnt += 14. 두 리스트의 합이 같아지면 break 위의 로직대로 했고 크게 잘못된 부분이 없다고 생각했는데 특정 TC에서 계속 실패하길래 고민을 꽤나 했다. '질문하기'에..

문제 입출력 예시문제를 요약하면 '내 왼쪽 인근에 있으면서 나보다 높은 탑의 인덱스 출력'이라고 할 수 있겠다. '인근'이라는 표현을 쓴 이유는 높이가 4인 다섯번째 탑처럼 왼쪽에 있는 탑들 중 나보다 높은 탑이 여러 개인 경우가 있을 수 있기 때문이다. 7보다 더 높은 탑이 있지만 4가 쏜 레이저 신호는 이미 7에 닿았으므로 7의 인덱스 번호+1을 출력하면 된다. 풀이☝ 첫 번째 시도(시간 초과)import sysfrom collections import dequeN = int(input())tower = list(map(int, sys.stdin.readline().split()))received = [0]for i in range(1, N): candidate = deque(tower[:i])..

초보자의 마음으로 다시 시작하는 알고리즘 공부 🙂 문제 입출력 예시어려운 문제는 아니지만 입출력 결과를 짚어보자. 1) 1 3 → 1층 3호에 사는 사람 수 구하기1층 3호에 살려면 0층 1호~3호 사람을 다 데려와서 살아야 하고 0층은 각 호에 호실 번호만큼의 인원이 산다고 했기 때문에 1+2+3=6을 출력한다. 2) 2 31층 1호~3호 인원 총합 = 0층 1호+(0층 1호+0층 2호)+(0층 1호+0층 2호+0층 3호)=1+3+6=10 아이디어1) 근본 = 0층모든 k층 n호를 0층으로 표현하는 방법을 떠올렸는데 굳이 다 풀어서 계산할 필요가 있나 싶어서 패스 2) 규칙 찾기수학&구현 파트는 규칙만 찾으면 생각보다 금방 풀리는 경우가 많아서 규칙을 찾아보려고 했지만 내가 내린 판단은? 규칙 없음!..