프로그래머스 풀이 (85) 썸네일형 리스트형 프로그래머스 - N개의 최소공배수(C++) https://tigerfrom2.tistory.com/70 유클리드 호제법(Euclidean algorithm) - 최대공약수, 최소공배수 알고리즘 최대공약수는 암호학에도 자주쓰이고 알고리즘 문제를 풀 때도 자주 등장합니다. 우리가 초등학교 때 배웠던 최대공약수 구하는 법은 ex) 4 8 이라 하면 두 수가 공통으로 나누어질 것 같은 수를 tigerfrom2.tistory.com 이 글을 참고! 어차피 몇개가 들어오던 (1,2,3,4) 라고 하면 1, 2의 최소공배수 a, a와 3의 최소공배수 b, b와 4 의 최소 공배수 c 라고 순차적으로 구해나가면 그게 정답이다. 수학적 증명은 하지않았지만 뭐 맞았다. #include #include using namespace std; int gcd(int a,.. 프로그래머스 - 삼각 달팽이(c++) 처음보면 되게 난해할 수 있는 문제이다. 방법이 있긴한가 싶었다. 처음 생각한 풀이는 DP였다. 그러나 DP는 최적의 값을 찾는 것인데 단순 배열 채우기가 DP?는 아닐거라 생각했다. 그다음은 dfs였는데 하삼각행렬만 가능하다고 치고 방향을 계속 바꿔주면 될 것 같았다. 이런 식으로 계속 규칙이 있음을 알 수 있다. 어차피 방향은 3가지뿐이라 재귀만 잘 따지면 가능할 것 같았다. dir 이라는 방향을 저장해두는 변수를 하나 만들고 dir = 0 이면 아래방향 dir = 1 이면 오른쪽 dir = 2 이면 왼쪽 대각선 으로 이동하게 만들고 각 방향마다 몇번 이동해야하는지 정해두었다. 그런데 그림으론 저렇지만 코딩을하고나니 첫번째때 0,0 에서 시작하니까 첫 아래방향에 cnt = n - 1 이 되는 것을 알.. 프로그래머스 - 마법의 엘리베이터(C++) 처음 문제를 읽고 바로 BFS구나! 싶어서 bfs로 코딩했다. 얼마 전 워딩이 거의 비슷한 문제를 만났어서 더욱 그랬다(아래 첨부) 그러나 시간초과에 틀렸습니다가 무더기로 나왔다. 잘 읽어보니 저 위의 100까지의 숫자 외에도 1000 10000까지도 나갈 수 있는 것이었다. 그래서 주어진 숫자의 자릿수까지만 bfs 할 수 있도록 했는데도 38점 밖에 받지 못했다. 너무도 당연하게 bfs가 맞다고 생각하고 있어서 내 코드가 어디가 잘못된 건지 갈피를 못잡고 있었다. 이 풀이가 잘못된건가? 라고 생각했을 땐 이미 늦었다. 이것과 비슷한 문제를 풀어본적이 있는데도 풀이를 바로 떠올리지 못한 것이 참 아쉽다. 아직까지도 시간복잡도 계산을 잘 못하는 것이 컸다. 시간복잡도를 통해 bfs가 불가함을 바로 알아챘어.. 프로그래머스 - 키패드 누르기 (C++) 처음엔 *, #에서 동시에 시작하는 그래프 문제인가? 싶었는데 그냥 구현문제였다. 각 자리의 좌표를 기억하고 갱신해주면 되는 간단한 문제이다. 뭔가 반복문을 잘 쓰면 코드를 줄일 수 있을 것 같은데 그냥 무식하게 했다. #include #include #include using namespace std; string solution(vector numbers, string hand) { string answer = ""; int leftx = 3; int lefty = 0; int rightx = 3; int righty = 2; for(int i = 0; i < numbers.size(); i++){ if(numbers[i] == 1){ leftx = 0; lefty = 0; answer.push_ba.. 프로그래머스 - 짝지어 제거하기(C++) 문제 설명 처럼 2개 짝짓고 제거하면 시간초과로 풀 수 없다. 첫 풀이는 다음과 같았다. 먼저 abcc 이런식으로 a, b가 홀수개이면 절대 문장은 제거되지 않는다. 그렇기 때문에 먼저 원소들의 개수를 세는 작업을 했고 이 작업을 통과하였을 때 제거 연산을 해봤다. 그러나 별짓을 다 해도 저 3개의 효율 테스트를 통과할 수가 없었다... 결국 아이디어를 구하기 위해 질문하기를 보았는데 답은 "스택" 이었다. 최대 크기가 100만일 때 부터 알아봤어야하는데 나는 아직 멀었다. 85점까진 받았기 때문에 코테나 대회였다면 바로 넘겼을 문제이기는 하다. 스택을 사용한다. ex) dcaabbcd 가 들어왔을 때 1. d를 꺼내 c와 비교한다. 둘은 다르다! 그러므로 꺼낸 d를 또다른 서브 스택에 넣어둔다 . 현재.. 프로그래머스 - 귤 고르기(C++) 이번에도 빡구현문제다. 프로그래머스 구현문제들은 문제를 이해하긴 되게 쉬운데 막상 어떻게 하지? 생각하면 잘 안풀리는게 특징이다. * 문제풀이 * 1. 주어진 귤의 사이즈대로 map에 삽입한다. 2. 갯수가 큰 순서대로 sort 한다. 3. 1개씩 더하고 k 보다 크거나 같아지면 멈추고 지금까지 넣은 사이즈의 귤의 갯수를 리턴한다. 다른 사람들 풀이보니까 짧고 간단하게 했던데.. 봐도 이해도 안가고 모르겠다. 그리고 실행시간을 보니 그닥 좋은 풀이는 아닌 것 같다. #include #include #include #include #include using namespace std; bool compare(const int a, const int b){ return a > b; } int solution(.. 프로그래머스 - 할인 행사 (C++) 문제 자체는 이해하기 어렵지 않다. 또 주어지는 배열의 길이가 길지 않기 때문에 시간초과를 걱정할 필요가 없어 완전탐색 식으로 전부 비교해보며 풀었다. 문제 유형은 별다른 알고리즘을 요구하는 문제는 아니고 그냥 빡구현이다. - 문제풀이 먼저 주어진 want 와 number를 각 맵을 이용해 넣어둔다 apple : 2 banan : 3 이런식으로 넣어둔다. 그 다음 discount는 10개씩 탐색해야하므로 만약 14개의 discount 가 주어졌다면 0~9 1~10 2~11 3~12 4~13 이렇게 5번 탐색해야한다. 그러므로 discount.size() - 10 으로 범위를 잡아준다. 그리고 discount도 중복을 제외하고 맵에 넣어둔다 apple : 2 banana : 3 pork : 2 이런식으로,.. 프로그래머스 - 혼자 놀기의 달인 (C++) 그냥 미친 빡구현 문제다. 문제 해석이 가장 중요하다. 상자가 열려있는지 확인할 bool 배열한개, map으로 각 상자와 카드번호를 생성한다. 주의해야할 예외사항은 1. 그룹이 1개이면 무조건 0점이다. 2. 각 그룹의 값이 같을 수 있다. #include #include #include #include #include #define MAX 101 using namespace std; int solution(vector cards) { int answer = 0; bool open[MAX] = {false,}; vector group; map cardbox; for(int i = 0; i < cards.size(); i++){ cardbox.insert(make_pair(i + 1, cards[i]));.. 이전 1 ··· 7 8 9 10 11 다음
