728x90
반응형

알고리즘 258

백준, BOJ, 14226번, 이모티콘 C++ [CPP] ★★★

어렵지 않았다. 다만 어떻게 풀지? 가 관건이다. https://www.acmicpc.net/problem/14226 문제 분석부터 해보자 최솟값을 가지는데 수행해야 하는 작업의 가중치가 같다? BFS 가자 #include using namespace std; //1개는 이미 입력 int S; int visited[3000][3000]; int main(){ cin >> S; //현재 상태, 클립보드에 저장된 개수 queue q; q.push({1,0}); visited[1][0] = 1; while(!q.empty()){ auto cur = q.front(); q.pop(); int now = cur.first; int clip = cur.second; //체크 if(now == S){ cout

알고리즘 문제풀이 - 수학 자주 나오는 개념 총정리

많은 수학 문제들이 있지만 가장 자주 나오는 문제부터 살펴보고 나머지는 교양으로 알아보자 나머지 나머지는 특히 답에 xxx로 나눈 나머지를 구하시오와 같은 문제로 많이 나오는데 이건 범위를 제한하기 위해서다. 즉, 기본 자료형의 범위를 초과한다고 생각하면 이런 문제가 나온다. 나머지에는 특징이 있는데 덧셈, 곱셈, 뺄셈은 이 법칙이 적용이 되고 나눗셈은 안된다. 1. 합을 나눈 것은 각자의 나머지의 합의 나머지를 구하는 것과 같다 2. 곱을 나눈 것은 각자의 나머지를 곱해서 나머지를 구하는 것과 같다. 3. 뺄셈을 나눈 것은 각자의 나머지를 뺀 것의 나머지를 구하는 것과 같다. **다만 뺄셈은 음수가 나올 수 있기 때문에 M을 한 번 더해준다. 마치 분배법칙을 이용한 것과 같다. 하지만 조금 다르다. 분..

알고리즘 문제풀이 - 스택, Stack 총정리

사실 스택을 이용하는 문제는 수없이 많다. 글 하나로 정리를 할 수 없다는 것은 안다. 하지만 스택이 가리키는 것은 단 하나 밖에 없고 그 개념을 조금이라도 감을 잡고자 글을 쓴다. 실전 개념 1. 스택은 한쪽 끝에서만 자료를 넣고 뺄 수 있다. 2. Push, Pop은 O(1)의 시간복잡도를 가진다. 3. Stack에 최근에 들어간 것만 뺄 수 있다. => 가장 마지막에 들어간 것만 뺄 수 있다. 확장 3. 연속된 원소를 집어넣으면 뺄 때는 역순으로 나온다. 문제를 풀면서 저 1,2,3번의 개념이 어디에 들어가나 보자 1. 단어 뒤집기 사실 어려운 문제다. https://www.acmicpc.net/problem/9093 #include using namespace std; int n; int main..

프로그래머스 카카오, 괄호 변환 C++ [CPP] ★★★

문자열 처리에 애를 먹었다. 조건이 정말 까다로웠다. 난 그랬다. https://programmers.co.kr/learn/courses/30/lessons/60058 #맞는 풀이 #include using namespace std; //나눌 수 없는 균형잡힌 문자열 => position //그것이 올바른지 아닌지 return bool IsCorrect(string str, int* pos){ bool isCorrect = true; int open = 0; int close = 0; stack stk; for(int i = 0; i 해당 위치를 찾았으니 종료 if(open == close){ *pos = i + 1; return isCorrect; } } return true; } string solu..

프로그래머스 카카오, 메뉴 리뉴얼 C++ [CPP] ★★★★★

MAP을 쓰는 정말 좋은 문제가 아닐까 싶다. 처음 생각하기는 어렵다. 하지만.. 알고 나면 너무나 쉽다. https://programmers.co.kr/learn/courses/30/lessons/72411 #맞은 풀이 #include using namespace std; //orders 배열의 각 원소는 크기가 2 이상 10 이하인 문자열 => 음식을 10개 초과로 시킬 수 없음 unordered_map combination[11]; // "음식이름", "횟수" //index는 음식의 수를 말함 combination[3] => 3가지로 만들 수 있는 조합 int mxCount[11]; //해당 조합 중에서 가장 많이 중복된 값 void comb(string str, int cnt, string res..

프로그래머스 카카오, 신규 아이디 추천 C++ [CPP] ★★★★

문자열 처리의 정말 정석이 아닐까 싶다. https://programmers.co.kr/learn/courses/30/lessons/72410?language=cpp #맞은 풀이 #include using namespace std; bool IsValidChar(char c){ if(isalnum(c))return true; if(c == '-' || c == '_' || c == '.')return true; return false; } string solution(string new_id) { string answer = ""; //모든 문자열을 뒤짐. for(auto c : new_id){ if(!IsValidChar(c))continue; //조건 2 c = tolower(c); //조건 1 //..

프로그래머스 카카오, 신고 결과 받기 C++ [CPP] ★★

우선 map을 자유자재로 사용한다면 쉽겠다. unordered_map인데도.. 순서가 바뀌어서 깜짝 놀랐다. https://programmers.co.kr/learn/courses/30/lessons/92334 #맞는 풀이 #include using namespace std; vector solution(vector id_list, vector report, int k) { vector answer(id_list.size()); int idx = 0; //유저 ID, Index unordered_map users; //유저 ID, 신고받은 횟수 unordered_map result; for(auto x : id_list){ result[x]; //0으로 초기화 users[x] = idx++; } //유저..

프로그래머스 카카오, k진수에서 소수 개수 구하기 C++ [CPP] ★★★★★(문자열처리)

우선 문자열처리가 C++에서 어렵다. 나는 아직 stringstream에 익숙하지 않아서 어려웠다. stringstream만 익숙한 사람이라면 무리없이 풀 것이다. https://programmers.co.kr/learn/courses/30/lessons/92335 #맞는 풀이 #include using namespace std; bool IsPrime(long long num){ if(num == 2)return true; if(num == 1 ||num % 2 == 0) return false; for(long long i = 3; i 다음 것 조사 if(val.size() == 0){continue;} if(IsPrime(stol(val))){ answer ++; } } return answer; ..

백준, BOJ, 16571번, 알파 틱택토 C++ [CPP] ★★★

이 문제도 구현 중 엄청 어려운 편에 속한다. 우선 나는 그렇다. 이건 진짜 어려웠다. 아니 알파고는 어떻게 계산함? https://www.acmicpc.net/problem/16571 #맞은 풀이 #include using namespace std; //게임은 누가먼저 시작하느냐에 따라 달라짐. string answer; //게임이 끝났는지(turn이 이기거나 지거나) 체크 //turn은 O 또는 X임 bool CheckGameEnd(vector& board, char turn){ //가로로 이겼는지 for(int i = 0; i

백준, BOJ, 12100번, 2048 C++ [CPP] ★★★★

난 아주 고난이도라고 생각하는 구현 문제다. 해당 게임을 해봤음에도.. 나는 이 문제를 푸는데 오랜 시간이 걸렸다. https://www.acmicpc.net/problem/12100 #맞은 풀이 #include using namespace std; int maxNumber = -1; int N; // N*N size vector vec; void DFS(int cnt, vector& board); void shiftBlock(int type, vector& board); //1 => 모든 경우를 살펴봐야함. int solution(vector& board) { DFS(0, board); return maxNumber; } //2 void DFS(int cnt, vector& board){ //모든 경우..

728x90
반응형