알고리즘 문제풀이/프로그래머스
-
[프로그래머스/Level 3] 정수 삼각형 (C++)알고리즘 문제풀이/프로그래머스 2021. 1. 28. 23:55
programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr DP유형의 문제로, 백준의 1932번과 똑같은 문제였습니다. DFS를 호출할 때, 2차원 입력값을 전역변수로 설정하지 않고 매번 호출하게 되면 메모리 낭비로 인한 시간초과가 발생할 수 있기 때문에 전역으로 따로 선언 후, 값을 복사해주었습니다. #include #include #include using namespace std; int dp[501][501]; vector cpy; int DFS(int x, int y, int size) { if(dp..
-
[프로그래머스/Level 2] 단체사진 찍기 (C++)알고리즘 문제풀이/프로그래머스 2021. 1. 15. 16:46
programmers.co.kr/learn/courses/30/lessons/1835 코딩테스트 연습 - 단체사진 찍기 단체사진 찍기 가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 programmers.co.kr 새롭게 알게된 점 distance() 함수를 통해 iterator 사이의 크기를 반환할 수 있다. #include #include #include using namespace std; bool isPossible(int dis, char op, int target) { if(op == '=') return dis == target; else if(op == '>') retu..
-
[프로그래머스/Level 2] 이진 변환 반복하기 (C++)알고리즘 문제풀이/프로그래머스 2021. 1. 13. 15:56
programmers.co.kr/learn/courses/30/lessons/70129 코딩테스트 연습 - 이진 변환 반복하기 programmers.co.kr 1. 무한루프 안에서 문자열 s의 모든 0을 제거합니다. 2. 제거할 때마다 제거한 횟수를 더해줍니다. 3. 0이 제거된 문자열의 길이를 2진수로 변환해줍니다. 4. 변환이 끝나고 변환한 횟수를 더해줍니다. 5. 이러한 과정을 문자열의 길이가 1이 될 때까지 반복합니다. #include #include using namespace std; string getBinary(int num) { string strBinary = ""; while(1) { if(num == 0) break; strBinary.insert(0, to_string(num % ..
-
[프로그래머스/Level 2] 예상 대진표 (C++)알고리즘 문제풀이/프로그래머스 2021. 1. 3. 20:50
programmers.co.kr/learn/courses/30/lessons/12985 코딩테스트 연습 - 예상 대진표 △△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N programmers.co.kr #include using namespace std; int solution(int n, int a, int b) { int answer = 0; while(1) { if(a == b) return answer; a = (a + 1) / 2; b = (b + 1) / 2; answer++; } }
-
[프로그래머스/Level 2] 삼각 달팽이 (C++)알고리즘 문제풀이/프로그래머스 2020. 12. 29. 16:16
programmers.co.kr/learn/courses/30/lessons/68645 코딩테스트 연습 - 삼각 달팽이 5 [1,2,12,3,13,11,4,14,15,10,5,6,7,8,9] 6 [1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11] programmers.co.kr 위의 그림에서 숫자가 채워지는 방향이 위/오른쪽/왼쪽 위 대각선 총 3가지인 것을 확인할 수 있습니다. 또한 방향의 전환은 n번 이루어지는 것을 확인할 수 있습니다. 이러한 규칙을 이용해서 2차원 배열에 값을 저장하고, 저장이 끝난 후 배열 전체를 탐색해 0보다 큰 경우만 벡터에 집어넣어 리턴하였습니다. #include #include using namespace std; int m..
-
[프로그래머스/Level 3] 단어 변환 (C++)알고리즘 문제풀이/프로그래머스 2020. 11. 24. 17:19
programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 레벨3 문제 치고는 어렵지 않은 DFS/BFS 문제였습니다. begin 문자열이 words 배열의 문자열중 어느 문자열로 바뀔 수 있는지를 잘 구현만 한다면 쉽게 해결할 수 있을 것 같습니다. /* BFS 풀이 */ #include #include #include #include using namespace std; bool visi..
-
[프로그래머스/Level 2] 조이스틱 (C++)알고리즘 문제풀이/프로그래머스 2020. 11. 17. 17:57
programmers.co.kr/learn/courses/30/lessons/42860 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 굉장히 어려웠던 그리디 유형 문제 한방향으로만 진행되는게 최소값이 아닐 수 있다. 따라서 왼쪽, 오른쪽으로 진행을 각각 해보고, 두개의 값중 최소값을 구하는 과정을 반복해야한다. 반례 : BBBAAAB -> 9 #include using namespace std; int solution(string name) { int answer = 0; string t..
-
[프로그래머스/Level 2] 짝지어 제거하기 (C++)알고리즘 문제풀이/프로그래머스 2020. 11. 10. 16:21
programmers.co.kr/learn/courses/30/lessons/12973 코딩테스트 연습 - 짝지어 제거하기 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙 programmers.co.kr 짝을 지어서 제거하거나, 옳고 그름을 판단할 때 스택을 이용하는 경우가 많은 것 같다. 1. 스택을 선언 2. 스택이 비어있지 않으면서 스택의 top과 현재 인덱스의 문자가 같으면 pop 3. 위를 만족하지 않으면 현재 인덱스의 문자를 스택에 push 4. 2번과 3번을 반복한 후, 스택이 비어있다면 1을 리턴, 비어있지 않다면 0을 리턴 #include #inc..