본문 바로가기

algorithm

백준 12865 - 평범한 배낭 2024. 9. 23. 문제 : https://www.acmicpc.net/problem/12865 풀이과정이 문제는 짐을 쪼갤 수 없는 0-1배낭 문제이다. 물품의 수 N(1 ≤ N ≤ 100)와 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 점화식으로 표현하면 아래와 같다.dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)"i번째 순번까지 물건을 담았고 j만큼의 무게가 실렸을 때 최대 가치" 를 의미한다. 1. dp[i-1][j] : 배낭에 물건을 넣지 않는다는 의미이다.i번째 물건을 넣지 않고, 그 이전 물건까지 넣은 j ..
백준 14501 - 퇴사
백준 14501 - 퇴사 2024. 9. 22. 문제 : https://www.acmicpc.net/problem/14501  풀이과정 DP를 통해 점화식을 구하되, N+1일째를 초과하는지 확인 후 거꾸로 저장해야 한다.  점화식을 아래와 같이 정의할 수있다.dp[day] = max(dp[day+1], dp[day + T[day]] + P[day]) 1. 여기서 dp[day]란 day에서 시작해서 퇴사일까지 얻을 수 있는 최대값을 의미한다.즉, dp[0] 는 0일부터 퇴사일까지의 최대값을 의미한다. (1일이 아닌 0일부터 시작한다고 가정한다.)2. max 조건식 첫번째 값인 dp[day+1] 의 의미는, 아무것도 하지 않고 넘어가는 날 을 의미한다.예를들어 마지막 두 날짜인 dp[6] 또는 dp[5]는 실행할 수 없으므로dp[6] = (6+1)날짜부터..
AWS - k8s Ingress 통한 Application Load Balancer(ALB) 생성 보호되어 있는 글입니다.
ata 보호되어 있는 글입니다.
7 보호되어 있는 글입니다.
[프로그래머스] - "숫자의 표현" C++ / 구현 2022. 9. 21. 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/12924 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 조건 연속되는 자연수의 합 중 주어진 N의 값과 일치하는 개수를 구해야 합니다. 1,3,4 처럼 연속되지 않는 자연수의 합은 제외됩니다. 풀이과정 1. (N+1) / 2 까지가 연속으로 더할 수 있는 최대 범위입니다. 그 이후는 무시해도 좋습니다. N = 51을 만든다고 가정해보면, (51+1) / 2 = 26입니다. 25+26 = 51이 되며 N을 벗어나지 않지만, 그 이후에는 26+..
[프로그래머스] - "빛의 경로 사이클" C++ / dfs
[프로그래머스] - "빛의 경로 사이클" C++ / dfs 2022. 7. 19. 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/86052 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이과정 # 해석 각 좌표마다 S L R 중 하나가 적혀있고, 그에 따라 빛이 움직이면서 처음 빛을 쐈던 위치로 돌아왔을 때의 이동 거리와 가능한 사이클의 개수를 구하는 문제입니다. - 위의 그림에서, 1번 방향으로 빛을 쏘기 시작했다면 결국 돌고 돌아서 16번을 이동한 다음 돌아오게 됩니다. - 또한 빛이 이동하다가 끝에 도달했다면 반대쪽 끝으로 다시 돌아오게 됩니다. - 입력 예시가..
[프로그래머스] - "튜플" C++ / 구현 / map 2022. 7. 18. 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/64065 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이과정 # 해석 '(' 과 ')' 그리고 ',' 과 숫자로 이루어진 문자열이 주어질 때, 튜플을 찾는 문제입니다. 입출력의 예는 다음과 같습니다. "{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{20,111},{111}}" [111, 20] "{{123}}" [123]..

티스토리툴바