백준

CS/알고리즘

[BOJ 17609] 회문 - Java

2023.03.17

문제 https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 풀이 회문 검사 문자열의 시작(start), 끝(end) 각각에서 하나씩 인덱스를 조정하면서 회문 여부 검사 str[start] == str[end] ➡ 다음 탐색 str[start] == str[end] ➡ 회문이 아님 while의 종료 조건: end 인덱스가 start 인덱스보다 커질 때 문자열의 길이가 홀수인 경우도 있기 때문에 while 지속 조건으로 start = end 일때도 포함된다. 유사회문 검사 문자열의 ..

CS/알고리즘

[BOJ 12865] 평범한 배낭 - C++

2022.07.20

문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 이 문제는 대표적인 0-1 knapsack(배낭) 문제이다. 무게의 한계가 정해져 있을 때 최대의 가치를 가지도록 물건을 배낭에 넣으면 된다. 배낭에 물건을 넣는 경우(1), 넣지 않는 경우(0)로 문제가 작게 쪼개질 수 있다. 물건을 넣을 때는 무게와 가치를 모두 고려한다. 문제에서 각각의 물건의 무게와 가치는 다음과 ..

[BOJ 17609] 회문 - Java

[BOJ 12865] 평범한 배낭 - C++

티스토리툴바