Algorithm

프로그래머스 삼총사 문제 바로가기 간만에 푼 코딩테스트 문제. 문제 조건에 따라서 3개씩 뽑아 삼총사의 조건(세 수의 합이 0)을 만족하는지 확인해주면 간단히 해결 가능하다. Python의 경우 collections의 combination을 이용해 sum이 0인지 확인하면 더 편할듯하다. (메모리 초과는 차치해두면) #include <string> #include <vector> using namespace std; int solution(vector<int> number) { int answer = 0; for (int i=0; i<number.size()-2; i++){ for (int j=i+1; j<number.size()-1; j++){ for (int k=j+1; k<number.size(); k++){ if (number[i] + number[j] + number[k] == 0){ answer++; } } } } return answer; }

프로그래머스 최댓값과 최솟값 문제 바로가기 python이라면 split을 이용해서 list을 만들고 max, min 함수를 이용해서 쉽게 구할 수 있을듯하다. C++도 vector에 저장해서 algorithm에서 max_element() min_element()으로 최대,최소값을 구할 수 있다. 하지만 vector을 저장하는 메모리가 사용되기 때문에 그보다 효율적인 비교하는 방식을 택했다. #include <string> #include <vector> #include <sstream> using namespace std; string solution(string s) { string answer = ""; int num, _max=-32768, _min=32767; stringstream stream; stream.str(s); while (stream >> num){ if (num > _max){ _max = num; } if (num < _min){ _min = num; } } answer = to_string(_min) + " " + to_string(_max); return answer; }

프로그래머스 연속된 부분 수열의 합 문제 바로가기 Bruteforce Simple is best라는 생각에 바로 bruteforce로 풀어보았다. 결과는… 시간초과 시간 복잡도가 $ O(n^{2}) $ 이기에 n이 조금만 커져도 기하급수적으로 증가한다. #include <string> #include <vector> #include <numeric> using namespace std; vector<int> solution(vector<int> sequence, int k) { vector<int> setting(k, 1); vector<int> answer; for (int start=0; start<sequence.size(); start++){ vector<int> temp; int i=start; while (reduce(temp.begin(), temp.end()) < k){ temp.push_back(sequence[i]); if (reduce(temp.begin(), temp.end()) == k){ if (setting.size() > temp.size()){ setting = temp; answer = {start, i}; } } i++; } } return answer; } 테스트 1~5 통과 테스트 6 이후 → 시간 초과 Two Pointer 어떻게하면 불필요한 연산을 줄일 수 있을까 고민했다. 사실 스스로 그 답을 찾아내진 못했고, Two Pointer이라는 힌트를 얻었다. Two Pointer는 starting 위치에 따라서 연산을 새로 시작하지 않고 기존의 계산 결과를 활용한다. 따라서 bruteforce에 비해서 현격히 적은 시간을 소요로 한다. 시간 복잡도: $ O(n) $ ...

백준 14940번 문제 바로가기 C++로 풀어보는 첫 bfs문제! python와 비교했을 때에 정의하는 방식만 다르지, 전체적인 구조는 동일해서 쉽게 익힐 수 있었다. 가장 헷갈렸던 부분은, deque을 정의하고 “좌표를 어떻게 전달할 것인가"는 문제였다. python같은 경우 tuple로 간단하게 전달하면 되지만, {x, y}로 전달하면 C++에서는 에러가 발생하기 때문이다. 다른 사람들의 bfs 구현 방식을 참고했는데, 대부분 pair 기능을 이용해서 좌표를 전달했다. make_pair(x, y)로 전달하면 마치 tuple 마냥 전달해줄 수 있다. 다시 그 값을 불러올 때에는 .front .second 처럼 점 연산자(.)를 통해 알아낼 수 있다. ...

백준 2630번 문제 바로가기 재귀 혹은 분할정복(Divide & Conquer) 문제인데, 은근 시간이 오래 걸렸다. 재귀 아이디어는 금세 나왔는데, 소소한 기본이 이슈가 있어서 자꾸만 문제를 다시 풀게 되었다. 처음에는 2차원 vector을 이용해서 풀었는데, size가 커지면 에러가 발생했다. 알고보니 vector을 함수의 인수(parameter)로 넘겨주면 그때마다 vector가 복사되기 때문에, 시간 초과가 발생할 수 있다. 이를 막기 위해서는 참조사를 이용하거나, int paper[128][128]처럼 int 배열을 이용해야한다. #include <iostream> using namespace std; int n_0 = 0; int n_1 = 0; int paper[128][128]; void epoch(int size, int x, int y){ int n_sum = 0; for (int i=x; i<x+size; i++){ for (int j=y; j<y+size; j++){ if (paper[i][j] == 1){ n_sum ++; } } } if (n_sum == size*size){ n_1 ++; } else if (n_sum == 0){ n_0 ++; } else{ size /= 2; epoch(size, x, y); epoch(size, x+size, y); epoch(size, x, y+size); epoch(size, x+size, y+size); } } int main() { int size; cin >> size; for (int i=0; i<size; i++){ for (int j=0; j<size; j++){ cin >> paper[i][j]; } } epoch(size, 0, 0); cout << n_0 << endl << n_1; return 0; }