본문 바로가기

알고리즘 부셔버렷/ProblemSolving45

[BOJ] 백준 2225 합분해 (문제 설명, 코드, C++) 문제 설명 해결 과정 코드 전문 문제 설명 본 문제는 백준의 2225번 합분해 문제입니다. https://www.acmicpc.net/problem/2225 0부터 N까지의 정수 중 K개를 뽑아 더하고 그 결과가 N이 되는 경우의 수를 찾아야합니다. 덧셈의 순서가 다른 경우엔 다른 경우로 셉니다. 한 개의 수를 중복적으로 사용가능합니다. 해결 과정 0에서 3 까지 수에서 2개를 뽑아 합이 3인 경우의 수는 3을 하나 뽑았다는 가정하에 0에서 0 까지의 수 중 1개를 뽑아 합이 0이 되는 경우를 포함합니다. - 0 3 2를 하나 뽑았다는 가정하에는 0에서 1 까지의 수 중 1개를 뽑아 합이 1이 되는 경우를 포함합니다. - 1 2 1을 하나 뽑았다는 가정하에는 0에서 2 까지의 수 중 1개를 뽑아 합이 2.. 2023. 1. 5.
[BOJ] 백준 2482 색상환 (문제 설명, 코드, C++) 문제 설명 해결 과정 코드 전문 문제 설명 본 문제는 백준의 2482번 색상환 문제입니다. 순환구조의 배열에서 각 원소들이 서로 이웃하지 않게끔, 총 n개의 원소 중에 k를 고를 수 있는 경우의 수를 찾는 문제입니다. https://www.acmicpc.net/problem/2482 해결 과정 핵심 아이디어는 첫 원소와 마지막 원소를 둘 다 고려해야할 때를 제외하면 순환적인 구조에서 벗어날 수 있다는 것 입니다. 그렇기에 시작 원소부터 끝 원소 전까지 반복을 통해 경우를 찾을 수 있습니다. i 번째 원소를 보고 j개 원소를 뽑아야한다면 i 번째 원소를 뽑을 경우 ) dp[i - 2][j - 1] (i를 뽑았으니 자신을 빼야하고, 자신 이전의 원소는 뽑을 수 없기에 i에 2를 뺍니다) i 번째 원소를 뽑지.. 2023. 1. 4.
[BOJ] 백준 2294 동전 2 (문제 설명, 코드, C++) 문제 설명 해결 과정 코드 전문 문제 설명 본 문제는 백준의 2294번 동전 2 문제입니다. https://www.acmicpc.net/problem/2294 n 가지의 동전이 있고 각 동전들을 사용해 k란 값을 만들기 위한 경우 중 동전의 수가 가장 적은 경우의 동전수를 찾아란 문제입니다. 조합을 염두에 두고 해결해야합니다. 해결 과정 조합을 염두에 두기에 가치가 젤 적은 동전부터 그 동전을 사용하여 만들 수 있는 K까지의 모든 값들의 경우의 수는 다음과 같이 구할 수 있습니다. k = 5, 동전의 가치 3, 동전을 사용해 만들 수 있는 값 j (3 ~ k) dp[i] k 가 i일 때 최소 동전수 dp[j] = dp[j - 3] + 1(동전 3의 개수) 이 과정을 모든 동전에게 다 시행하며 기존의 동전.. 2023. 1. 3.
[BOJ] 백준 2293 동전 1 (문제 설명, 코드, C++) 문제 설명 해결 과정 코드 전문 문제 설명 본 문제는 백준의 2293번 문제 동전 1입니다. https://www.acmicpc.net/problem/2293 조합을 의식하며 주어진 동전으로부터 어느 값을 구할 수 있는 모든 경우의 수를 구하란 문제입니다. 사용 동전의 개수는 무한하며 조합을 의식하여야하기에 4란 값을 구하기 위한 1, 2, 1 와 1, 1, 2는 같은 경우로 취급하여야합니다. 해결 과정 최적해를 구하는 문제이기에 다이나믹 프로그래밍으로 풀 수 있을 것이라 생각이 들었습니다. 처음에는 익숙한 방식인 Top down 방식의 재귀를 통해 DP를 구성하려하였는데 이 방식은 조합을 의식하지 않아 다른 방법을 찾았습니다. 각 동전들은 K라는 임의의 값을 만들기 위해 K - 동전의 경우의 수를 경우.. 2023. 1. 2.
[BOJ] 백준 2631 줄 세우기 (문제풀이, 코드 c++) 문제 설명 해결 과정 코드 전문 문제 설명 본 문제는 백준의 2631번 문제 줄 세우기 문제입니다. https://www.acmicpc.net/problem/2631 중복 없는 연속된 수들을 최대한 적게 숫자를 이동시켜 오름차순으로 정렬하는데 그 때의 이동횟수를 구하는 문제 입니다. 해결 과정 이 문제를 해결하는데는 다음과 같은 요소를 알아야합니다. 증가하는 부분수열 중 가장 큰 것을 구하고 부분수열에 해당되는 않는 숫자들을 옮기면 가장 적은 횟수로 정렬이 가능하다는 것 입니다. 문제에서 사용된 예시입니다. 3 7 5 2 6 1 4 증가하는 부분수열 중 가장 큰 것 { 3, 5, 6 } 이 숫자들은 고정해둔 채 나머지 7, 2, 1, 4를 움직이는 것 입니다. 그렇기에 답은 7 - 3 = 4가 됩니다. .. 2023. 1. 1.
[프로그래머스] 순위 검색 (문제 설명, 해결 과정, 코드 전문, c++) 문제 설명 해결 과정 코드 전문 문제 설명 본 문제는 프로그래머스의 순위 검색 문제입니다. https://programmers.co.kr/learn/courses/30/lessons/72412 = score) count++; } answer.emplace_back(count); } return answer; } 느낀 점 (잡설 99% , 배운점 1%(많은 편)) 더보기 string.find()는 문자만 찾습니다. 문자열 넣지맛! 그래도 잘 풀었다고 생각합니다. "-"가 올 수 있는 모든 경우는 하드코딩을 해버렸는데, 고심 끝에 축약해 코딩을 하였더라면 이 코드를 보는 다른 사람 입장에선 정말 난해하게 보였을 거 같아 그렇지 않았습니다. 너무 코드의 길이에 신경을 써 미시적인? 코드를 만들어버리는 건 앞뒤.. 2022. 6. 13.
[프로그래머스] 예상 대진표 (문제 설명, 해결 과정, 코드 전문, c++) 문제 설명 해결 과정 코드 전문 문제 설명 본 문제는 프로그래머스의 예상 대진표 문제입니다. 입출력 예 N A B answer 8 4 7 3 해결 과정 이 문제는 부전승이 존재하지 않고 참가자의 수가 2의 지수 승으로 주어집니다.(제한 사항) 그리고 개개인의 번호를 입력값으로 주어지는데, 참가자의 수가 2의 지수 승이고 부전승이 없기에 모든 개개인의 번호는 대진표 한 그룹의 번호로 바꿀 수 있습니다. 그리고 한 라운드가 끝나면 총 인원의 수가 2배 줄며 그룹의 수도 2배 줄게 됩니다. 이때 이긴 사람부터 차례대로 오름차순 그룹에 배정되기에 1,2번 그룹의 승자가 1그룹으로 들어가게됩니다. 이 때 입력으로 받은 두 선수의 번호가 같은 그룹이 되었을 때 라운드의 번호를 반환하면 정답입니다. 해당 라운드에도 .. 2022. 6. 12.
[프로그래머스] 게임 맵 최단거리 (문제 설명, 해결 과정, 코드 전문, c++) 문제 설명 해결 과정 코드 전문 문제 설명 본 문제는 프로그래머스의 게임 맵 최단거리 문제입니다. 입출력 예 maps answer {{1,0,1,1,1}, {1,0,1,0,1}, {1,0,1,1,1}, {1,1,1,0,1}, {0,0,0,0,1}} 11 {{1,0,1,1,1}, {1,0,1,0,1}, {1,0,1,1,1}, {1,1,1,0,0}, {0,0,0,0,1}} -1 해결 과정 최단거리를 구하는 문제입니다. 모든 거리는 통과하는데 드는 비용이 1로 같으니 BFS를 통해서 구할 수 있습니다. DFS로도 구할 수는 있지만 기법의 특성 상 최선의 경우를 따졌을 때 BFS보다 느립니다. BFS기법을 풀어 말하자면 지나온 장소는 마킹을 하여 다시 돌아오는 일을 막고 매 순간 갈 수 있는 모든 방향으로 나아.. 2022. 6. 12.

티스토리툴바