알고리즘 문제풀이/프로그래머스
-
[프로그래머스/Level 2] JadenCase 문자열 만들기 (C++)알고리즘 문제풀이/프로그래머스 2020. 11. 10. 15:40
programmers.co.kr/learn/courses/30/lessons/12951 코딩테스트 연습 - JadenCase 문자열 만들기 JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는 함수, solution을 완성해주세요. 제한 조건 programmers.co.kr #include #include using namespace std; string solution(string s) { for(int i = 1; i < s.size(); i++) { if(s[i - 1] == ' ') s[i] = toupper(s[i]); // 앞에 공백이 있으면 현재 위치 대문자 else s[i]..
-
[프로그래머스/Level 2] 행렬의 곱셈 (C++)알고리즘 문제풀이/프로그래머스 2020. 11. 9. 16:34
programmers.co.kr/learn/courses/30/lessons/12949 코딩테스트 연습 - 행렬의 곱셈 [[2, 3, 2], [4, 2, 4], [3, 1, 4]] [[5, 4, 3], [2, 4, 1], [3, 1, 1]] [[22, 22, 11], [36, 28, 18], [29, 20, 14]] programmers.co.kr 은근 헷갈렸던 문제 transferhwang.tistory.com/209 해당 문제의 심화(?) 문제이다. #include #include using namespace std; vector solution(vector arr1, vector arr2) { vector answer; for(int i = 0; i < arr1.size(); i++) { // ar..
-
[프로그래머스/Level 2] 최솟값 만들기 (C++)알고리즘 문제풀이/프로그래머스 2020. 11. 9. 16:16
programmers.co.kr/learn/courses/30/lessons/12941 코딩테스트 연습 - 최솟값 만들기 길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다. 배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱 programmers.co.kr 입력값의 범위가 1000 이하의 자연수라서 next_permutation을 이용하여 한 배열의 순열을 구하고, 이를 통해 최소값을 구하려고 했는데 이상하게 시간 초과가 발생한다. (O(N^2)로도 풀려야한다고 생각했는데... 접근이 잘못됐나,, 이유를 모르겠다.) 그래서 다른 풀이는 O(N)으로 해결할 수 있는 방법으로, 각 곱을 합한 최소값은 최대값 x..
-
[프로그래머스/Level 2] 폰켓몬 (C++)알고리즘 문제풀이/프로그래머스 2020. 11. 9. 15:43
programmers.co.kr/learn/courses/30/lessons/1845 코딩테스트 연습 - 폰켓몬 당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. programmers.co.kr 벡터 nums의 크기의 2분의 1개 만큼 폰켓몬을 뽑는데, 가장 많은 종류의 폰켓몬을 뽑아야 하는 문제다. 벡터의 원소를 set을 선언하여 전부 넣어주면 중복된 값이 사라진다. 이때 set의 크기가 nums의 크기의 2분의1 보다 크거나 같으면 그냥 nums의 크기의 2분의 1을 리턴하면 되고, set의 크기가 더 작다면 set의 크기를 리턴하면 답이된다. #include ..
-
[프로그래머스/Level 2] N개의 최소공배수 (C++)알고리즘 문제풀이/프로그래머스 2020. 11. 9. 14:47
programmers.co.kr/learn/courses/30/lessons/12953 코딩테스트 연습 - N개의 최소공배수 두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배 programmers.co.kr 유클리드 알고리즘을 이용해서 최대 공약수를 구한 후, 이를 토대로 최소 공배수를 구하면 된다. 이때 오름차순으로 정렬하여, 작은 것부터 큰 것 순서로 최소 공배수를 구하고, 나온 값을 i+1번째 배열에 저장해주었다. #include #include #include using namespace std; int getGCD(int a, ..
-
[프로그래머스/Level 2] 숫자의 표현 (C++)알고리즘 문제풀이/프로그래머스 2020. 11. 9. 14:02
programmers.co.kr/learn/courses/30/lessons/12924 코딩테스트 연습 - 숫자의 표현 Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 programmers.co.kr 입력값의 최대가 10,000 이므로 O(N^2) 풀이로는 시간초과가 발생할 위험이 있으므로 투 포인터를 이용하여 O(N)의 시간 복잡도로 해결했습니다. #include #include using namespace std; int solution(int n) { int answer = 0, head = 0, tail = 0, sum = 0; vector v(..
-
[프로그래머스/Level 2] 땅따먹기 (C++)알고리즘 문제풀이/프로그래머스 2020. 11. 6. 21:19
programmers.co.kr/learn/courses/30/lessons/12913 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟 programmers.co.kr 입력값의 범위가 100,000 이하의 자연수이기 때문에, 단순히 O(N*N) 방법으로 풀면 시간초과로 인해 문제를 해결할 수 없다. 보통 이러한 시간 초과 문제를 해결하기 위해서 DP를 사용하는 것 같다. 다음 행으로 이동할 때마다 각 열의 누적합을 구해주면 된다. | 1 | 2 | 3 | 5 | | 5 | 6 | 7 | 8 | | 4 | 3 | 2 | 1..
-
[프로그래머스/Level 2] 올바른 괄호 (C++)알고리즘 문제풀이/프로그래머스 2020. 11. 6. 16:39
programmers.co.kr/learn/courses/30/lessons/12909 코딩테스트 연습 - 올바른 괄호 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 ()() 또는 (())() 는 올바른 괄호입니다. )()( 또는 (()( 는 올바르지 않은 괄호 programmers.co.kr 스택으로 해결하는 너무나도 유명한 문제 1. '(' 을 만나면 스택에 push 2. ')'을 만나면 - 스택이 비어있을 경우 false를 리턴 - 스택에 원소가 있는 경우 pop 3. 괄호 탐색을 완료 후, 스택에 원소가 남아 있다면 false, 비어있다면 true #include #include using namespace std; boo..