본문 바로가기
728x90
반응형

분류 전체보기82

[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.
[algorithm] 백준 - N과 M(10) 이 문제는 dfs이다. 이 문제는 N과 M(6)과 N과 M(9)와 연관된 문제이다. 중복되는 수열을 여러번 출력하면 안되며, 수열은 중복된 수로 나열되어있을 수 있다. 포인트는 'N과 M(6) + 재귀 시 중복된 수가 있는지 확인' 이다. N과 M(6)은 조합문제이다. 조합 코드는 두 가지가 있는데, void combination(int target, int index, vector realVector, vector numVector){ if(target == 0){ sort(numVector.begin(), numVector.end()); combinationVector.push_back(numVector); return; } if(index == realVector.size()){ return; } .. 2020. 10. 30.
[algorithm] 백준 - N과 M(9) 이 문제는 dfs이다. 중복되는 수열을 여러번 출력하면 안되며, 수열은 중복된 수로 나열되어있을 수 있다. 이 문제는 N과 M(5)와 연관된 문제이다. 포인트는 'N과 M(5) + 재귀 시 중복된 수가 있는지 확인' 이다. N과 M(5) 문제 또한 dfs인데, 순열과 조합이 섞인 문제이다. 즉, N개로 이루어진 자연수 중에서 M개를 고르고 나열하는 문제이다. //백준 N과 M (5) #include #include #include using namespace std; bool selected[9] = {false}; void permutationAndCombination(int target, int index, vector realNumVector, vector numVector){ if(target =.. 2020. 10. 30.
728x90
반응형

티스토리툴바