본문 바로가기

전체 글348

백준 1461 c++ "도서관" -PlusUltraCode- https://www.acmicpc.net/problem/1461 [필자 사고]그리디 문제이다.필자는 우선순위큐를 이용하여 M개 만큼 빼는 형태로 해당 문제를 해결했다.음수와 양수를 따로 처리를 해줬고 절대값이 가장 큰 값은 복귀를 하지 않아도 되므로해당 부분은 따로 찾은 뒤 pop을 해결했다. 아래는 자세한 코드 해설이다.[코드 해설]구조 설명입력 받기 (Input)N개의 수를 입력받습니다.수를 절댓값과 부호(1: 양수, 0: 음수)로 저장해둡니다 (arr 벡터).양수는 plus_Queue에, 음수는 minus_Queue에 각각 저장합니다.plus_Queue는 큰 수가 우선 나오게 (오름차순)minus_Queue는 작은 수가 우선 나오게 (내림차순) 정렬합니다.전체 입력 중 가장 절댓값이 큰 수가 양.. 2025. 4. 29.
백준 15903 c++ "카드 합체 놀이" -PlusUltraCode- https://www.acmicpc.net/problem/15903 [필자 사고]그리디 알고리즘이다. 그리디 알고리즘이라고 다를건 없고 최선의 경우의 수로 푸는 문제이다.필자는 우선순의 큐를 이용하여 앞 2개의 숫자를 꺼내서 해당 문제에서 요구하는 방식대로 코드를 해결해 나갔다. 아래는 자세한 코드해설이다.[코드 해설]코드 설명:입력 받기:cin >> N >> M으로 N과 M의 값을 입력받습니다.N은 주어지는 숫자의 개수이고, M은 두 수를 더하는 연산을 몇 번 반복할지를 나타냅니다.우선순위 큐 초기화:priority_queue, cmp> pq는 우선순위 큐로, 기본적으로 priority_queue는 큰 값이 먼저 나오게 되어 있는데, 여기서는 cmp라는 비교자 함수를 사용하여 작은 값이 먼저 나오도록 .. 2025. 4. 10.
백준 16120 c++ "PPAP" -PlusUltraCode- https://www.acmicpc.net/problem/16120 [필자 사고]PPAP를 만나면 p로 바뀌는 어쩌면 탐욕적 알고리즘과 유사하다.결과를 이용하여 역추적하는 느낌?? 필자는 해당 문제를 stack 을 이용하여 문제를 해결했다. 특정 idx를 설정하여 해당 문자열이 현재 어느 위치인지 각인 시켜줬다.약간 구현 문제 같은 느낌이 들었다. 아래는 자세한 코드 해설이다.[코드 해설] 데이터 구조stack를 사용하여 문자를 하나씩 처리하며 상태를 저장합니다.Node는 문자와 해당 문자가 PPAP 패턴 중 몇 번째 위치인지를 나타내는 인덱스를 함께 저장합니다.예를 들어 P가 PPAP의 첫 번째 등장이라면 인덱스 1, 그 다음 P는 2, A는 3, 마지막 P는 4.핵심 변수flagIdx: 현재까지 발견.. 2025. 4. 7.
백준 1958 c++ "LCS 3" -PlusUltraCode- https://www.acmicpc.net/problem/1958 [필자 사고]LCS 에서 차원이 늘어난 문제이다.핵심 원리는 동일하다같은 문자열이 있으면 [i-1][k-1] 의 값에 1을 더해주고다른 문자열이면 그동한 만든 갯수의 최대값을 갱신하면서 오면 된다.다만 필자가 이 문제를 풀면서 실수한 점은 string str1 에서 str1.insert(0," "); 으로 앞부분에 빈공간을 넣어준뒤str1.size() 형태로 접근해야되는데 주의하자. 아래는 자세한 코드 해설이다.[코드 해설] DP 테이블 초기화세 개의 문자열이 각각 최대 길이 100이기 때문에, 크기가 101x101x101인 3차원 정수 배열을 만듭니다.이 배열의 각 위치는 dp[i][j][k]라고 했을 때,문자열 1의 i번째 문자까지, .. 2025. 4. 3.

티스토리툴바