본문 바로가기

알고리즘 문제147

[알고리즘문제] 프로그래머스 - 타겟 넘버 예전에 똑같은 문제를 풀었었는데, dfs로 나올 수 있는 연산자의 경우를 모두 구한 다음 숫자를 하나씩 넣어서 구하는 약간 무식한 방법(?)을 사용했습니다. 그때 방법이 너무 비효율적이라 생각해서 다른 분들의 풀이법을 보고 공부를 했습니다. 예전에 제가 풀었던 방법은 ++++, +++-, ++-+...이런식으로 dfs로 모든 경우의 수를 구했고 이 값을 사용하여 number의 인덱스 하나씩 비교해서 값을 더했었습니다. 이런 방법보다는 재귀를 돌리면서 연산이 적용된 현재의 값을 저장하는 방법이 더 직관적이고 괜찮은 방법인 것 같습니다. #include #include using namespace std; vector v; int t; int count = 0; void dfs(int sum,int dept.. 2019. 12. 26.
[알고리즘문제] 프로그래머스 - 구명보트 문제 자체는 간단하다. 구명보트에는 2명만 탈 수 있고, 무게 제한이 주어질때 필요한 최소한의 보트수를 구하는 문제이다. 전형적인 그리디 문제이다. 처음 생각한 방법은, 가벼운 사람들 먼저 태워서 보내는 방법이다. 이를 위해 최소힙을 사용하였다. 근데 구현을 하다보니, 생각보다 세세하게 신경써줘야 하는 부분이 많았고 최대 2명밖에 탈 수 없다는 조건을 늦게 봤다. 두번째로 생각한 방법은, 무거운 사람과 가벼운 사람을 적절히 조합해서 태우는 방법이다. 2명을 태우는데 20,10을 태우는 것보다는 90,10을 태우는 것이 훨씬 이득이기 때문이다. 무거운쪽 인덱스를 가리키는 e(people.size()-1), 가벼운쪽 인덱스를 가리키는 s로 나누었다. people[s] + people[e] >=limit --.. 2019. 12. 26.
[알고리즘문제] 프로그래머스 - 더 맵게 문제는 크게 어렵지 않은데, 처음 문제를 읽었을 때 바로 이해가 되지 않았다. 문제를 2번 읽고, 입출력 예 설명을 읽고 문제를 이해할 수 있었다. 스코빌 지수가 나오고 하는데, 문제를 쉽게 설명하면 배열에 자연수가 들어가 있다. 배열에서 첫번째, 두번째로 작은 값을 꺼내고 첫번째 + (두번째 * 2)값을 다시 배열에 넣는다. 이 과정을 한번 연산을 진행했다고 말한다. 결과는 위의 연산을 몇번 진행을 해야 배열의 모든 값이 K이상이 되는가? 묻는 문제이다. 첫번째, 두번째로 작은 값을 꺼내야 하기 때문에 min heap을 사용하였다. min heap에서 값을 꺼내면 가장 작은 값이 나오기 때문. while문의 조건은 초기 heap.size() > 1인데, 그 이유는 한번의 연산을 하면서 heap에서 값이.. 2019. 12. 23.
[알고리즘문제] 프로그래머스 - 조이스틱 문제를 보니깐 JAVA로 예전에 푼 흔적이 있었다. 정답을 맞춘 흔적이 없는 걸 봐선 그떄 못 푼 문제 같았다. 문제해결방법은 먼저 그리디하기 생각했다. 내 알파벳을 바꾸고 현재 나의 위치에서 가장 가까운 놈을 먼저 찾아가는 것이다. #include #include #include #include using namespace std; int getMinLength(int start,string name){ int left = name.at(start); int right = name.at(start); int depth = 0; while(true){ if(left == 65 || right == 65){ break; } depth++; right++; left--; if(right > 90){ righ.. 2019. 12. 22.

티스토리툴바