본문 바로가기
반응형

알고리즘11

[cpp 알고리즘] 백준 19844 단어 개수 세기 [백준] 19844 단어 개수 세기 cpp 풀이알고리즘: 구현, 문자열https://www.acmicpc.net/problem/19844 문제 요약문제가 너무... 어렵게 적혀있는 것 같다. 해야하는 것을 쉽게 정리하자면먼저 띄어쓰기와 -(하이픈)을 기준으로 “단어”를 쪼갠다.각각의 “단어”에서, 위처럼 줄어들었을 가능성이 있는 경우(즉, c', j', n', m', t', s', l', d', qu'로 시작하고 어포스트로피 뒤 글자가 모음인 경우) 이 단어들을 한 번 더 분리해 준다.핵심은 여기서 '(어포스트로피) 앞에는 단어(c,j,n,m,t,s,l,d,qu) 가 있어야 하고, '(어포스트로피) 뒤에는 모음(a,e,i,o,u,h)로 시작하는 단어가 오면 된다. =>  ' 앞에는 단어 단위로, ' 뒤에.. 2024. 7. 15.
[cpp 알고리즘] 백준 4396 지뢰 찾기 [백준] 4396 지뢰 찾기 cpp 풀이알고리즘: 구현https://www.acmicpc.net/problem/4396 문제 요약 N*N의 지뢰 판이 주어지고, M개의 지뢰가 있다. - 입력1) 온점(.)은 지뢰가 없고, 별표(*)는 지뢰가 있는 지점이다.- 입력2) 이미 열린 칸은 영소문자x로, 열리지 않은 칸은 온점(.)으로 표시된다. - 출력) (1) 지뢰가 없으면서 열린 칸은 0~8 사이의 숫자, (2) 지뢰가 있는 칸이 열렸으면 지뢰가 있는 모든 칸을 별표(*)로, (3) 다른 모든 지점은 온점(.) 으로 표현해야 한다. 문제를 이해하는 것과 주어진 테스트코드로 이해는 쉬웠으나, 몇 가지 경우에 대해 더 생각해 봐야 한다...😒풀이 정리(1) 우선 N*N의 기본 지뢰 판을 만들고, 온점(.)과.. 2024. 7. 8.
[cpp 알고리즘] 백준 1744 수 묶기 [백준] 1744 수 묶기 풀이 그리디 알고리즘, 정렬, 많은 조건 분기 문제 출처: https://www.acmicpc.net/problem/1744 문제 요약 - 길이가 N인 수열이 주어졌을 때, 두 수를 곱하거나 그대로 둘 수 있다. 이 수들을 모두 더한 값들 중 최댓값을 구하면 된다. 풀이 정리 1. 일단 오름차순으로 정렬한다. 2. 숫자 1을 기준으로 3가지 경우로 나뉘어진다. (1) 1보다 작은, 0이거나 음수인 경우 -> 앞쪽(작은 수)부터 두 수를 곱해서 최종 결과 값에 더하면 된다. (2) 1인 경우 -> 곱하는 데 사용하지 않고, 더하면 된다. (3) 1보다 큰 양수인 경우 -> 뒤쪽(큰 수)부터 두 수를 곱해서 최종 결과 값에 더하면 된다. 3. (1)의 경우 혹은 (3)의 경우가 홀.. 2023. 11. 11.
[cpp 알고리즘] 백준 1629 곱셈 [백준] 1629 곱셈 cpp 풀이 수학, 분할 정복을 이용한 거듭제곱 https://www.acmicpc.net/problem/1629 문제 요약 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어졌을 때, A를 B번 곱한 수를 C로 나눈 나머지를 출력하면 된다. 풀이 정리 - 분할 정복을 활용하여 지수를 나누어 주면 된다. (1) 지수가 0인 경우 -> X^0 = 1 이므로 1을 리턴해준다. (2) 지수가 짝수인 경우 -> X를 X/2로 나누어서, 계산한 두 값을 곱해준다. (3) 지수가 홀수인 경우 -> X를 X/2로 나누고, 계산한 두 값과 밑을 한 번 더 곱해준다. - 예제에 나왔던 A=10, B=11로 예를 들어 보면, 1. 가장 나이브하게 먼저 생각나는 방법은 for문을 이용하여 .. 2023. 11. 10.
반응형

티스토리툴바