BOJ 문제 풀기 (C++)

1로 만들기 문제: n에서 시작해서 1로 가는 최소 연산 횟수와 경로를 구하기. 사용할 수 있는 연산은:\-1/2 (짝수일 때만)/3 (3의 배수일 때만)di를 i를 만들기 위한 최소 연산 횟수, prei는 i를 만들기 위해 어떤 수에서 왔는지 기록한 경로 추적 배열로

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하기dn-1에서 세로로 한 줄을 더 넣는 방법2 x 1 세로 타일 한 줄을 맨 끝에 추가dn-2에서 정사각형을 하나 더 넣는 방법1 x 2 가로 타일 2개를 맨 끝에 추가 (세로 타일은 이미 1번에

이친수의 조건: 1\. 이친수는 0으로 시작하지 않는다.2\. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하기숫자가 0으로 끝나는 경우0을 맨 뒤에 추가1

연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하기i 번째 수를 포함하는 최대 연속합을 배열로 두기경우의 수 구하기이전까지의 연속합에 현재 수를 이어붙이는 경우이전 거를 다 버리고 새로 시작하는 경우"i 번째 수를 포함하는 최대 연속합을 배열로 두

수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하기di는 i 번째 수를 마지막으로 하는 증가 부분 수열 중에서 합이 가장 큰 값증가 조건을 만족하는 앞의 dj에 현재 수를 한 번 더해서 가장 큰 합을 고르기

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열의 길이 구하기BOJ 11055번과 비슷하게, O(N^2)의 방식으로 접근di는 i 번째 수를 마지막으로 하는 수열의 최대 길이증가 조건을 만족하는 배열에 + 1을 하여 최대 길이 갱신하기

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이P(1) ~ P(10): 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 N이 주어졌을 때, P(N)을 구하기!di = di-1 + di-5 di = di - 2 + di - 3 도 가능이 수열은 피보나치처럼

상담 완료하는데 걸리는 시간 T와 상담했을 때 받을 수 있는 금액 P가 주어졌을 때, 남은 N일 동안 받을 수 있는 최대 금액 구하기🔗 문제 링크오늘 날짜부터 퇴사 전까지를 역순으로 생각di를 i번째 날부터 퇴사일까지 벌 수 있는 최대 수익으로 두기퇴사 전까지 상담할

🔗 문제 링크di: i자리 수 중, 마지막 자리가 j인 계단의 개수j가 0이면 j-1 불가능, j가 9이면 j+1 불가능0으로 시작하는 수 없음answer가 누적되면서 mod 범위를 초과할 수 있음✅ 해결 방법answer가 mod 연산 안에서 유지될 수 있도록 해야

회의의 수 N과 N개의 시작/끝나는 시간이 주어지면 할 수 있는 회의의 최대 수 구하기🔗 문제 링크끝나는 순 기준 → 시작 시간 기준으로 정렬하여, 현재 있는 시간 다음에 올 수 있는 회의를 고르기pair를 (시작시간, 끝난 시간)이 아니라 (끝난 시간, 시작시간)으

로프들에 대한 정보가 주어졌을 때, 들어올릴 수 있는 물질의 최대 무게 구하기(병렬 연결로 물체 무게 나눌 수 있음)🔗 문제 링크오름차순 로프 정렬1 ~ n개의 로프 골랐을 때 각각 (i개 로프 중 가장 약한 애 \* i)를 하여 최대 무게 갱신입력 값 범위 체크w배

물건의 무게와 물건의 가치가 주어졌을 때 배낭에 넣을 수 있는 물건들의 가치합의 최대값 구하기🔗 문제 링크di는 i 무게였을 때의 최대 가치dj-w는 현재 물건인 w를 넣기 전 상황물건을 중복으로 넣지 않도록 역방향으로 순회하기현재의 물품을 넣을지 말지를 나누어서 최

수열의 수를 2개씩 묶어서 나올 수 있는 최대 합 구하기🔗 문제 링크양수는 내림차순 정렬 후 큰 것부터 곱하기음수는 오름차순 정렬 후 작은 것부터 곱하기1은 따로 관리하여 나중에 한 번에 더하기0은 남는 음수에게 곱해서 없애기.back()vector의 마지막 원소를

두 점 위치가 주어지고, 선의 총 길이 구하기 (겹치는 부분은 중복으로 세지 않음)🔗 문제 링크x와 y를 pair로 입력받아서 오름차순 정렬pair들을 순회하면서 겹치는 부분이 있으면 start와 end 값에 누적하고, 겹치는 부분이 없으면 새로운 start와 end

한 개의 멀티탭의 여러 개의 전자기기를 꽂을 때 최소한으로 코드 뽑기🔗 문제 링크해당 기기가 멀티탭에 꽂혀있는지 확인멀티탭 꽉 차지 않았으면 꼽고, 꽉 찼으면 3번으로 넘어감다음에 올 전자기기들을 보면서 제일 나중에 오는 전자기기를 빼기 (만약 중복되는 기기가 하나도

가장 큰 자릿수부터 작은 자릿수까지 감소하는 수 중에 N 번째 수 구하기🔗 문제 링크감소하는 수는 9876543210이 최대이기 때문에 미리 다 계산해놓고 N번째 수를 구하면 됨. (N이 감소하는 수 범위를 넘어가면 -1 리턴!)감소하는 수 구하는 방법 last di

nCm이 주어졌을 때, 0의 개수 구하기🔗 문제 링크0의 개수는 곧 2와 5의 조합이므로, nCm에서 있는 2와 5의 개수 중 최솟값을 구하면 됨nCm = n! / (m! \* (n-m)!) 공식과 각 팩토리얼에 특정 숫자가 몇 개 들어있는지 알아내는 함수를 이용하여

1부터 N까지의 수를 이어서 썼을 때 k 번째 숫자 구하기🔗 문제 링크1~N까지 썼을 때 몇 번째까지 왔는지 구하는 법✨ 길이 패턴 알아보기1~9: 9 \* 1 \* 110 ~ 99: 9 \* 2 \* 10 → 9 \* len(현재 숫자 길이) \* exp(현재 자릿

집합 안에 있는 수들 중 x,y,z 를 더해서 k가 될 때, k의 최대값 구하기🔗 문제 링크two 벡터에 모든 x + y를 저장x + y + z = k, 변형하면 x+y = k - z가 되므로 two 벡터 안에 k - z를 만족하는 수가 있는지 내림차순으로 확인하고

가지고 있는 랜선의 개수 K, 필요한 랜선의 개수 N이 입력될 때 랜선 최대 길이 구하기🔗 문제 링크길이 X로 잘랐을 때 N개 이상의 랜선을 만들 수 있는지 판단하는 함수를 만들기이분 탐색을 통해 만들 수 있는 랜선 길이 중 가장 긴 길이를 찾기mid 길이로 만들 수

여러 개의 우주들과 각 우주 속 행성의 크기가 주어졌을 때, 같은 패턴의 행성을 가지고 있는 우주 쌍의 개수 구하기🔗 문제 링크각 우주는 상대적인 순서만 중요 → 좌표 압축압축된 벡터를 map에 저장하여 빈도 수 계산같은 벡터가 n개 있으면 쌍의 수는 n\*(n-1)

두 용액을 혼합할 때, 전체 용액의 특성값이 0에 가장 가까운 조합을 구하기🔗 문제 링크용액은 정렬된 상태로 주어짐두 용액의 합이 0에 가까워야 함 → 투 포인터 (Two Pointers) 사용정렬된 배열에서 왼쪽은 음수 쪽, 오른쪽은 양수 쪽 → 점차 좁혀가며 탐색

합이 0인 네 정수의 쌍의 개수 구하기🔗 문제 링크"A+B+C+D = 0" → "A+B = -(C+D)" 를 이용하기lower bound와 upper bound를 이용하여 0을 만들 수 있는 쌍 세기오버플로우 발생하지 않게 int 대신 long long 이용binar

같은 원소가 K 개 이하로 들어있는 연속 수열의 최대 길이 구하기🔗 문제 링크같은 원소의 개수를 셀 수 있도록 아주 큰 배열 만들어놓기투 포인터를 사용하여 길이 갱신하기 (이전 기록 바탕으로)while문에서 다음 원소를 포함해도 k개 이하인지 봐야 하기 때문에 en이

수열 S에서 최대 K번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이 구하기🔗 문제 링크en을 오른쪽으로 확장하면서 수열을 늘려감만약 arren이 짝수라면: 그대로 수열 늘림만약 arren이 홀수라면:odd_count가 k보다 작다면

최종적으로 수강신청에 성공한 인원을 출력하는 프로그램🔗 문제 링크unordered_map을 이용하여 각 학생의 신청 순서 갱신unorderd_map을 vector로 변환하여 시간 순서가 빠른대로 오름차순 정렬과목의 가능 수강 인원 만큼만 앞에서부터 출력정렬을 위해 v

문제 설명 > 명소에 도착하기 위해 시계방향으로 최소 몇 칸 움직여야 하는지 구하기 🔗 문제 링크 핵심 아이디어 set을 이용하여 명소인 위치를 저장 (정렬 유지) 나머지 연산을 이용하여 원형 리스트 위치 연산 lower bound을 이용하여 가장 가까운 명소의

N번째 큰 수 찾기🔗 문제 링크최소 힙을 사용해 N개의 값만 유지하고, top()을 이용해 N번째 큰 수 찾기

그때그때 중간값을 구하기. 단, 짝수개일 경우 가운데 있는 2개의 숫자 중 작은 숫자를 구하기.🔗 문제 링크최대 힙으로 반으로 나눴을 때 작은 값들을, 최소 힙으로 반으로 나눴을 때 큰 값들을 저장함.최대 힙에서 중간값 출력하기!2개의 힙의 사이즈를 비교해서 한쪽으로

문제와 데드라인, 컵라면 개수가 주어졌을 때 받을 수 있는 컵라면의 최대 개수 구하기🔗 문제 링크vector pair로 데드라인 별로 오름차순 정렬컵라면의 개수를 저장할 최소 힙 만들기최소힙의 크기 = 여태까지 푼 문제 개수 = 여태까지 소모한 날들→ 최소힙의 크기와

이분 그래프인지 아닌지 판별하기🔗 문제 링크모든 정점을 A그룹(빨강) 또는 B그룹(파랑) 두 색으로 칠하기연결된 정점들은 반드시 다른 색이어야 함만약 색칠하다가 같은 색끼리 연결되면 → 이분 그래프 아님!변수 꼭꼭 잘 초기화하기! fill나 clear로 잘 초기화 하

무게가 중간이 될 수 없는 구슬의 개수 구하기🔗 문제 링크정방향 그래프 (더 가벼운 구슬들), 역방향 그래프 (더 무거운 구슬들) 로 나눠서 입력받기BFS로 각 정점별로 연결된 구슬들의 개수를 세서 절반인 n/2보다 크면 중간 값이 아니라는 것!

과장된 얘기를 할 수 있는 파티 개수의 최댓값 구하기🔗 문제 링크파티와 각 파티에 참석하는 사람들을 한 번에 입력 받고, 진실을 아는 사람들이 퍼지도록 함모든 작업을 끝낸 후 파티별로 진실을 아는 사람이 있는지 여부 세기!나처럼 무식하게 파티에 온 사람들 전부 다 이

트리의 개수를 세는 프로그램🔗 문제 링크트리의 개수 세는 법 -> 사이클이 있는지 확인하기! (하나라도 있으면 안됨)현재 cur에서 연결되어있는 nxt를 보면서 생길 수 있는 경우의 수방문 안함 -> 새로운 길로 계속 탐색방문 함 -> 부모임 -> 부모로 돌아가는 건

정점 U를 루트로 하는 서브트리의 정점에 속한 개수 출력🔗 문제 링크DP와 DFS를 조합해서 사용하기DFS 부모와 자기 자신을 넘겨서 역행하면 스킵(현재 노드의 서브트리 크기 = 자신 + 모든 자식들의 서브트리의 합)을 이용하여 DP 배열에 저장하기DFS를 한 번만

두 노드가 주어졌을 때 두 노드 사이의 거리 구하기🔗 문제 링크DFS를 매 입력마다 돌려서 거리 누적하기pair를 이용해서 {연결된 노드, 거리}를 저장vis 배열을 이용해서 이미 방문한 노드인지 확인현재 노드가 목적지 노드이면 멈추고 거리 리턴하기DFS에서 이 부분

모든 뉴런을 트리 형태로 만들기 위하여 필요한 최소 연산 횟수 구하기🔗 문제 링크‼️ N개의 뉴런을 모두 트리로 잇기 위한 최소한의 간선 개수 = N-1 ‼️DFS로 이미 연결되어있는 그룹 개수 구하기 (k)추가 간선 구하는 법k - 1 (k개의 그룹을 잇기 위해 k

부하들에게 연쇄적으로 칭찬이 전달될 때, 각 부하가 받은 칭찬 수 구하기🔗 문제 링크트리 배열, 칭찬 배열, 정답 배열 3개의 자료 구조로 해결하기DFS에서 다음 부하로 칭찬 누적할 때 (칭찬 배열 속 칭찬 + 여태껏 누적된 칭찬) 으로 넣기사장은 상사가 없으니 계산