본문 바로가기
728x90
반응형

algorithm56

[algorithm] 백준 - 카드 구매하기 이 문제는 전형적인 DP 문제이다. 포인트는 N개의 카드팩을 사는데 가장 비싼 값을 반환하는 것이다. 이 곳에는 DP 배열과 P 배열을 변수로 사용한다. DP 배열은 n개의 카드팩을 사는 방법 중 가장 큰 돈으로 살 수 있는 경우를 저장한다. P 배열은 카드 n개가 포함된 카드팩의 값을 저장한다. 예를 들어보자, 카드팩을 4개 산다고 가정했을 때 DP[4] = max( P[4] + DP[4 - 4 = 0], P[3] + DP[4 - 3 = 1], P[2] + DP[4 - 2 = 2], P[1] + DP[4 - 1 = 3] ) 가 되고, 이를 구하기 위해선 DP[0], DP[1], DP[2], DP[3]을 필요로 하게 된다. 그럼 이를 식으로 표현해보면, DP[N] = max(P[N] + DP[N - i].. 2020. 11. 2.
[algorithm] 백준 - 좋은 수열 이 문제는 두가지 해결책을 내야했다. 좋은 수열을 걸러내는 작업 dfs 좋은 수열을 걸러내는 작업 비교해야하는 크기 비교해야하는 인덱스 위치 1212 123123 12341234 와 같이 (길이 / 2) 만큼의 수열을 비교해야한다는 것을 알 수 있다. 12341233 -- 비교해야하는 수열의 크기가 1일 때 6,7을 비교한다. 12341212 -- 비교해야하는 수열의 크기가 2일 때 45 67을 비교한다. 12345345 -- 비교해야하는 수열의 크기가 3일 때 234 567을 비교한다. 12341234 -- -- 비교해야하는 수열의 크기가 4일 때 0123 4567을 비교한다. 이것을 수식으로 표현해보자면, 수열의 크기는 i, 변하는 값은 j로 했을 때 arr[len - 2*i + j] arr[len .. 2020. 10. 30.
[algorithm] 백준 - 암호만들기 조합과 동일하다. 이 곳에서 조건이 있는데 모음은 1개 이상, 자음은 2개 이상이어야 한다. 알파벳이 모음일 경우 모음변수를 하나 증가시키고, 자음일 경우 자음 변수를 하나 증가시킨다. if(isVowel(realVector[index])){ combination(vowelCount + 1, consonantCount, index + 1, alphaVector, realVector, target - 1); } else{ combination(vowelCount, consonantCount + 1, index + 1, alphaVector, realVector, target - 1); } target에 도달하고, 조건에 일치할 경우 알파벳 열을 출력하면 된다. if(vowelCount >= 1 && con.. 2020. 10. 30.
[algorithm] 백준 - 퇴사 dfs로 해결했다. 다음 인덱스에 일해야하는 날짜를 더한 값이 일할 수 있는 날보다 작거나 같을 경우 금액을 추가함과 동시에 해당 인덱스에 일해야하는 날짜를 더한 인덱스를 다음 반복문에 방문하도록 했다. 그렇지 않은 경우엔 바로 다음 인덱스를 방문하도록 했다. if(index + moneyVector[index].first count; vector moneyVector; for(int i = 0; i > num >> money; moneyVector.push_back({num, money}); } dfs(0, 0, moneyVector); cout 2020. 10. 30.
[algorithm] 백준 - 연산자 끼워넣기 & 연산자 끼워넣기 2 4분기로 나누는 방법과 1분기로 가는 방법이 있다. https://book.algospot.com/estimation.html 이것은 연산 개수 당 걸리는 시간에 대한 자료이니 참고하는 것이 좋다. 알고리즘 문제 해결 전략 4.6 수행 시간 어림짐작하기 주먹구구 법칙 프로그래밍 대회의 시간 제한은 알고리즘의 시간 복잡도가 아니라 프로그램의 수행 시간을 기준으로 합니다. 따라서 어떤 알고리즘이 이 문제를 해결 book.algospot.com 연산자 끼워넣기 문제에서, 10!로 1분기의 경우 1.3초가 걸렸다. 4분기는 O(4^n)으로 0ms가 걸렸다. 따라서 1분기도 가능하지만 4분기가 좋다. 연산자 끼워넣기(2) 문제는 1분기로 하게 되면, 44P10으로 연산량이 많아 시간초과가 난다. 따라서 4분기로 .. 2020. 10. 30.
[algorithm] 백준 - 이모티콘 weight가 제 각각일 경우 dijkstra로 최솟값을 구할 수 있고, 1로 일정할 경우엔 bfs로 최솟값을 구할 수 있다. 이 문제는 범주가 3개로 나뉜다. 화면에 이모티콘 붙여넣기 화면 이모티콘 개수 + 클립보드 이모티콘 개수 화면에 이모티콘 삭제 화면 이모티콘 개수 - 1 화면에 이모티콘 복사하기 클립보드 이모티콘 개수 = 화면 이모티콘 개수 화면 이모티콘과 클립보드 이모티콘 개수를 따로 기록해줘야하므로 pair를 이용해서 queue에 집어넣었다. //백준 이모티콘 #include #include using namespace std; int weight[1001][1001]; bool visited[1001][1001]; int answer = 0; void initWeight(){ for(int.. 2020. 10. 30.
728x90
반응형

티스토리툴바