목록전체 글 (246)

영벨롭 개발 일지

[백준 BOJ][C++]3187번 양치기 꿍 풀이: BFS/DFS

https://www.acmicpc.net/problem/3187 3187번: 양치기 꿍 입력의 첫 번째 줄에는 각각 영역의 세로와 가로의 길이를 나타내는 두 개의 정수 R, C (3 ≤ R, C ≤ 250)가 주어진다. 다음 각 R줄에는 C개의 문자가 주어지며 이들은 위에서 설명한 기호들이다. www.acmicpc.net 이 문제는 BFS/DFS 를 사용하여 해결할 수 있습니다. [풀이 과정] 1. R과 C, 각 영역에 대한 정보 입력 2. 영역이 'k'라면 전체 양의 수를 나타내는 k값 증가, 'v'라면 전체 늑대 수를 나타내는 v값 증가 3. 아직 방문하지 않은 울타리로 둘러쌓인 영역 탐색(bfs) 4. 탐색 과정에서 울타리로 둘러쌓인 영역 내에서의 양의 수(knum), 늑대의 수(vnum) set..
알고리즘 문제 풀이/BOJ 2022. 3. 9. 17:32
[백준 BOJ][C++]2225번 합분해 풀이: DP

https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 이 문제는 Dynamic Programming, DP를 사용하여 해결할 수 있습니다. dp부터 설정해야겠죠? dp[i][j] 는 i 개의 숫자의 합이 j 가 되는 경우의 수를 나타냅니다. 초깃값으로는 dp[1][j]는 모두 1이 되겠죠? dp[2][j] 부터 보겠습니다. 각 색깔이 다음 단계에서 어떻게 쓰이는지 봐주세요! 모든 경우 경우의 수 dp[2][0] 0+0 1 dp[2][1] 0+1 1+0 2 dp[2][2] 0+2 1+1 0+1 3 dp[3][j] 는 어떻게 될까요? 모든 경우 경우의 수 dp[3][0] 0+0+..
알고리즘 문제 풀이/BOJ 2022. 3. 9. 17:23
[프로그래머스][C++]Level 2 타겟 넘버 풀이: DFS

https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 programmers.co.kr [풀이 과정] 1. value는 해당 숫자, idx는 numbers 벡터에서 숫자의 위치, sum은 탐색하는 과정에서 해당 숫자까지의 합인 구조체 info 선언 2. info 타입의 스택(벡터) 선언 3. {0, -1, 0}을 스택에 push 4. 스택의 top 원소 pop 5. numbers 벡터에서 top원소 다음 위치에 해당하는 숫자..
알고리즘 문제 풀이/프로그래머스 2022. 3. 8. 16:19
[알고리즘]랜덤 미로 생성 알고리즘: 엘러(Eller)의 알고리즘

DFS나 BFS와 같은 여러 탐색 알고리즘들로 미로를 탐색할 수 있었죠? 오늘은 미로를 직접 만들어보겠습니다. 미로를 만드는 알고리즘에는 여러가지가 있는데 그 중 Eller's Algorithm 엘러의 알고리즘을 살펴보겠습니다. 랜덤 미로 생성 알고리즘 Eller's Algorithm 엘러의 알고리즘은 미로를 한 행 씩 차례로 생성해나가는 방법입니다. 가장 빠르게 미로를 생성하는 알고리즘 중 하나이다. 미로의 크기가 N이라면 시간복잡도는 O(N)으로, 미로를 선형시간 안에 만드는 엄청난 성능의 알고리즘입니다. 생성 과정 3x5 크기의 미로를 생성하는 과정은 다음과 같습니다. 1. 미로의 첫 번째 행을 초기화합니다. 이때 첫 번째 행에 속한 5개의 칸을 서로 다른 집합에 속하게 합니다. 2. 현재 행에서 ..
CS/알고리즘 2022. 3. 7. 17:54
[백준 BOJ][C++]1912번 연속 합 풀이: DP

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 이 문제는 Dynamic Programming, DP를 사용하여 해결할 수 있습니다. dp[n]은 수열 arr의 n번째 원소까지의 연속합의 최댓값입니다. 문제 예제인 10 -4 3 1 5 6 -35 12 21 -1 을 보겠습니다. arr[0]인 10까지의 최대 합은 당연히 10이겠지요? dp[0]=arr[0]=10으로 초기화 합니다. arr[1]인 -4까지의 최대 합을 보겠습니다. dp[0]+arr[0] 6..
알고리즘 문제 풀이/BOJ 2022. 3. 6. 20:10
[백준 BOJ][C++]1699번 제곱수의 합 풀이: DP

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 이 문제는 Dynamic Programming, DP를 사용하여 해결할 수 있습니다. dp[n]은 n을 제곱수들의 합으로 표현할 수 있는 최소 항의 개수를 나타냅니다. 점화식부터 보겠습니다. dp[n]=min(dp[n], dp[n-i*i]+1), (1 N; dp[1] = 1; dp[2] = 2; dp[3] = 3; for (int i = 4; i
알고리즘 문제 풀이/BOJ 2022. 3. 6. 19:35
이전 Prev 1 ··· 31 32 33 34 35 36 37 ··· 41 Next 다음