전체 글
22.05.10. 풀었던 문제들
1. 숫자 게임 (greedy) greedy 문제. A와 B 둘 다 오름차순으로 정렬해 두고 index를 비교한다. 만약 B가 이기는 경우면 상관없지만 A가 이기는 경우에는 B[i]를 버리고 B[i+k]를 택해 더 작은 숫자를 버리고, 이길 수 있는 숫자를 택한다. // 숫자 게임 using namespace std; int solution(vector A, vector B) { sort(A.begin(), A.end()); sort(B.begin(), B.end()); int ai, bi; for(ai = 0, bi = 0; ai = B[bi]){ bi++; } else{ ai++; bi++; } } return ai; } 2. ..
22.05.09. 풀었던 문제들
프로그래머스 lv.3 1. 야근 지수 priority queue를 이용하는 방법, set과 map을 이용해 조금 더 최적화시킨 2가지 방식으로 풀었는데, 후자의 경우 뭔지 모르겠는데 안된다. (시간적 이득은 분명히 있다) #include #include #include #include using namespace std; typedef long long ll; long long solution(int n, vector works) { priority_queue pq; for(int i : works) pq.push(i); while(n > 0 && !pq.empty()){ ll max_value = pq.top(); pq.pop(); n--; if(max_value == 1) continue; pq...
22.05.08. 풀었던 문제들
프로그래머스 lv. 3 1. N-Queen backtrack 문제. 왜 이게 lv3에서..? lv2에 더 어려운 문제가 많은데 흠... 일단 계속 풀자. 그냥 조건에 맞으면 지속 탐색, 그렇지 않다면 return하는 방법 (backtrack)하면 된다. 멍청하게 삽질을 좀 했다.... 피곤하긴 한가보다. // N-Queen #include #include #include #include using namespace std; int answer = 0; vector queen_position; bool canPlace(int r, int c){ for(int i = 0; i 다음과 같이 변경 x' + y' + ... + a' = s-n이고 미지수 개수는 n개, 모든 미지수 >= 0이어야 함 즉, (s-..
22.05.07. 풀었던 문제들
1. 이중우선순위큐 c++에서 set은 bst로 구성되어 있기 때문에(항상 정렬되어 있으며, begin()은 최솟값, end()는 최댓값) multiset을 이용하면 쉽게 풀 수 있다. 2. 등굣길 간단한 DP로 풀 수 있다. 뭔가 lv2에서 훨씬 어려운 문제를 봤던 것 같은 기분이... 3. 단어 변환 DFS로 쉽게 구현할 수 있다. 다만, target이 words에 없는 경우를 고려해 주었어야 했다. 4. 베스트앨범 unordered_map이나 map과, 해당 container 정렬을 통해 쉽게 풀 수 있는 문제. 5. 여행경로 DFS로 쉽게 구현할 수 있다. 6. 섬 연결하기 MST 문제이다. prim algorithm으로 구현해도 되고, kruskal algor..
22.05.06. 풀었던 문제들
1. 양궁 대회 brute-force하게 푼다면 서로 다른 11개의 구역 중 10개를 뽑는 방법(== 동일한 10개의 화살을 11개의 구역에 놓는 경우의 수). 즉 11H10이다. 충분히 계산 가능한 수치. 이 경우 11개의 구역 중 n개를 뽑고, 뽑은 것을 size 11짜리 vector로 변환도 해야하고, 갱신도 신경써줘야 한다. 만약 point 차가 같은 경우는 우선순위가 더 높은 벡터를 정답에 할당해 주어야 하는데, 이에 대한 함수도 만들어 주어야 한다. 즉 만들어야 하는 함수만 'vector 우선순위 계산 함수', '점수 계산 함수', '중복조합 함수'로 다 필요하긴 하지만 상당히 귀찮았다. // 양궁대회 #include #include #include #include using namespace..
22.05.05. 풀었던 문제들
1. 빛의 경로 사이클 문제 푸는 방식은 알았으나 어떻게 코드로 작성하지, 에서 애를 좀 먹었던 문제다. 결과적으로는 'r, c좌표 + direction'이 또 탐색되는 경우 사이클이 만들어지며, 만약 만들어졌던 사이클에 진입하게 되면 똑같은 사이클이 만들어지므로 cycle result = 0일 때는 결과에 추가하지 않는다. // 빛의 경로 사이클 #include #include #include using namespace std; typedef pair pii; // 0 : up, 1 : down, 2 : right, 3 : left int dr[4] = {1, -1, 0, 0}; int dc[4] = {0, 0, 1, -1}; int max_r, max_c; int handleOutBound(int ..
22.05.02. 풀었던 문제들
1. 순위 검색 brute-force하게 풀면 5만 * 10만으로 시간초과가 난다. 따라서 다른 방식으로 풀어야 하는 문제. 먼저 주어지는 조건의 경우의 수는 총 120가지(언어3, 직군2, 경력2, 소울푸드2 + 상관없는 경우의 수 + 1씩 해서 4*3*3*3 = 120이지만 예외처리 귀찮아서 4개짜리 길이의 4진수를 구성했고 string 조건을 숫자로 바꾸어 주는 함수를 만들었다. 그리고 조건은 총 4가지, 한 조건씩 "-"(상관없음)으로 바꾸어 가면 한 사람당 총 16개의 경우의 수가 생긴다. 이를 vector에 push한다. 그러면 vector[i]는 조건이 i에 해당하는 사람들의 점수 list가 되고, list를 sort해 두면 binary search할 수 있다. 이어서, query의 조건도 ..
22.05.01. 풀었던 문제들
1. 메뉴 리뉴얼 조합 찾아내고, 조합의 개수를 unordered_map으로 count하는 쉬운 구현 문제였다. 2. 순위 검색 simple하게 brute-force로 풀면 시간초과가 나 버리는 문제(50억) 따라서 nlogn으로 풀어야만 한다.
22.04.30. 풀었던 문제들
휴가 + 복귀 격리로 인해 한 10일?가량 쉰 것 같다. 1. 배달 bellman-ford 알고리즘이다. 2. 괄호 변환 string + 재귀로 간단히 풀 수 있는 문제. 구현 문제였다. 3. 거리두기 확인하기 simple하게 DFS로 풀면 되는 문제다. DFS의 탐색은 좌표평면에서 상하좌우로만 움직이고 max depth가 2로 설정하면 맨해튼 거리가 2까지로 탐색하게 된다. 이 때, 만약 파티션이 없는 경우만 탐색을 하고, 사람이 있는 경우에는 사람이 있다는 flag를 이용하면 된다.
22.04.20. 풀었던 문제들
1. 수식 최대화 값이 long long이니 string to number로 변환할 때 stol이 아닌, stoll로 변환해야 한다. // 수식 최대화 #include #include #include #include #include using namespace std; // c가 operatior인지 판별 bool isOP(char c){ if(c == '+' || c == '-' || c == '*') return true; else return false; } // c는 operator, a와 b는 숫자. a와 b를 c연산 한 후 string으로 리턴 string cal_operand(string c, string a, string b){ long long result = 0, all = stoll(..
22.04.19. 풀었던 문제들
1. 문자열 압축 입력 길이가 1일 때 예외가 있었다. // 문자열 압축 #include #include #include #include using namespace std; int solution(string s) { int length = s.length(), min_value = 9999999; // cl : 압축 단위(compress length). ceil을 쓴 이유는 문자열 길이가 1일 수 있기 때문임. for(int cl = 1; cl
22.04.17. 풀었던 문제들
1. 후보키 - key의 조합을 고른다. 이 조합은 nC1, nC2, ... , nCn으로 뽑을 수 있는 모든 경우의 수이다.(여기서 n은 key의 개수) - 위에서 고른 key들로 유일성을 만족하는지 검사한다. (키에 해당하는 relation의 개수가 중복이 없는지) - set으로 검사하면 된다. - 위 두 조건을 만족하는 것 중 포함관계가 있는지 검사하면 된다. // 후보키 #include #include #include #include #include #include #include using namespace std; // keys에 해당하는 key들이 unique한지 검사하는 함수 bool isUnique(string keys, vector& relation){ sort(keys.begin(),..
22.04.16. 풀었던 문제들 *** KMP 알고리즘
1. 방금 그곡 풀었음. string 비교니까 KMP 알고리즘 정리 한 번 해 보자. 그리고 너무 귀찮은 문제였다... 2. 튜플 string 다루는 문제였다. string 전처리 이후는 중복제거(set이나 unordered_set)로 쉽게 풀 수 있었다.
22.04.15. 풀었던 문제들
10, 11, 12, 13, 14 5일동안 밀접접촉으로 격리한다고 PS를 못했다. 다시 오늘부터 시작. 1. 방금그곡 푸는 중... -> 시간 부족으로 못 품.
22.04.09. 풀었던 문제들
1. [3차] 파일명 정렬 주어지는 대로 풀면 된다. 다만 algorithm header의 sort 함수는 quick sort(unstable)이기 때문에 stable_sort를 써줘야 한다.
22.04.08. 풀었던 문제들
1. [1차] 프렌즈4블록 쫄았는데 생각보다 풀 만 하다. 시간도 꽤 빨리 풀었고... 단순 구현 문제였다. 2. [3차] 압축 문자열과 map을 사용하는 문제다. 주어지는 대로 구현하면 되고, index가 잘 계산되었는지만 신경쓰면 된다. // 압축 #include #include #include #include using namespace std; vector solution(string msg) { // 단계 1 map dict; vector alphabet = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"}..
22.04.07. 풀었던 문제들
1. 캐시 충격적이다... range for문은 값을 변경해도 변경되지 않는다고 한다. 예를 들어 아래와 같은 코드를 실행해도 arr에서 값이 1인 element의 값은 그대로 1이다. 왜냐하면 range loop에서 값은 복사된 값이기 때문이라고 한다. for(int elem : arr){ if(elem == 1) elem = 0; } 이를 방지하기 위해 reference를 사용하면 된다. for(int &elem : arr){ if(elem == 1) elem = 0; } 풀이는 간단하다. LRU를 구현하면 된다. "city가 cache안에 있다면, 해당 city의 참조값을 0으로 둠. 없다면, 참조값이 제일 큰 것의 위치에 넣음. 이후 모든 lru 수치를 1 더함."으로 구현하면 된다. 2...
22.04.06. 풀었던 문제들
프로그래머스 lv 2 1. 멀쩡한 사각형 #include #include #include using namespace std; typedef long long ll; typedef long double ld; long long solution(int w,int h) { if(w < h) swap(w, h); // w가 더 크게. ll answer = (ll)w * h; for(ll i = 1; i
22.04.05. 풀었던 문제들
1. n^2 배열 자르기 규칙 찾기 문제였다. n = 3이 주어졌다고 하자. 그러면 arr는 아래 그림과 같다. 1 2 3 2 2 3 3 3 3 idx에 따른 값은 아래와 같다. (0,0) : 1 (1,0), (1,1), (0,1) : 2 (2, 0), (2, 1), (2,2), (1,2), (0,2) : 3 보이는가? arr[i][j] = max(i, j) + 1이다. 또, n이 주어졌을 때, 특정 idx가 주어지면 배열의 그것으로 바꿀 수 있겠는가? -> Yes. n/4, n%4로 바꿀 수 있다. 2. 방문 길이 중복되는 경우는 세지 않으니, map이나 set으로 풀면 되는 문제다. 그리고 팁. 이 문제와 같이 좌표평면에서 상하좌우로 이동하는 경우, if나 case를 써서 나누지 말고 ..