전체보기
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를 써서 나누지 말고 ..
22.04.04 풀었던 문제들
1. 쿼드 압축 후 개수 세기 backtrack을 이용해, 압축 가능하다면 탐색하지 않고, 압축 불가능하면 탐색하는 방식으로 진행하면 된다. 2중포문 안쓸려다가 시간 엄청나게 잡아먹은 문제. 생각해 보면, 모든 arr을 log(input size)만큼 탐색하는 것이므로 시간복잡도는 n^2logn이다. 입력이 1024까지니 이런 풀이가 가능함. // 쿼드압축 후 개수 세기 #include #include using namespace std; void div(vector& arr, vector& answer, int r, int c, int size){ if(size == 1){ answer[arr[r][c]]++; return; } int base = arr[r][c]; bool compressable =..
22.04.02. 풀었던 문제들
1. 소수 찾기 어떤 숫자의 list(0, 1, 2, 3, ...)이 주어졌을 때 size가 1인 순열 size가 2인 순열 ... size가 list.size()인 순열 을 모두 구하고, 소수인지 판정하면 되었다. 2. 조이스틱 greedy라고 나와 있지만.. 이 문제가 진짜 greedy인지 나는 모르겠다. 그래서 brute-force로 풀었다. 어떤 문자열이 있으면, 그 문자열의 제일 앞에 있는 문자를 제일 뒤로 보낸다. 이렇게 만들어진 문자열(temp)의 index 0으로 이동해야 하는 거리를 구하고, 그 temp 문자열에서 왼쪽으로 쭉 갈 때, 오른쪽으로 쭉 갈 때 좌/우 이동의 최솟값을 구한다(A가 아닌 idx를 찾으면 된다). 이 두 값의 합이 기존 문자열에서 이동해야 하는 좌우 이동 ..
22.04.01. 풀었던 문제들
1. 전화번호 목록 hash로도 풀 수 있고, sort 한 후 string 특성으로도 풀 수 있다. hash로 푸는 경우, unordered_map에 모든 phone number를 넣어두고, 모든 phone number의 자기 자신을 제외한 substring(해당 phone number 제외. 즉 01234라면 0, 01, 012, 0123만 본다는 것)에 대해 unordered_map에 있는지 검사한다. 있다면 접두어가 있는 것이므로 false, 아니면 true. sort로 푸는 경우, string을 사전식으로 정렬한 후, phone_book[i-1]가 phone_book[i]의 substring이라면, 즉 phone_book[i].substr(0, phone_book[i-1].length()) =..
22.03.31. 풀었던 문제들
1. 큰 수 만들기 greedy 문제다. 앞에서부터 str[i] < str[i+1]인 경우 str[i]를 지우는 방식으로 반복한다. string의 모든 substr가 monotonic decreasing을 만족한다면 제일 작은 char부터 지워나가면 된다. 2. 기능개발 size가 작기 때문에 simple하게 queue로 돌려도 되고 (brute-force하게) 아니면 최적화해서 풀 수도 있는 문제였다. 이 경우에는 남은 일자를 계산하고, 예를 들어 3 1 1 4 2 1 5 이라면 3 1 1을 하나로 묶어 배포하고 4 2 1을 하나로 묶고, 5를 묶어 배포해야 된다. 규칙은, 남은 일자가 오름차순이라면 따로 배포해야 한다는 것이다.( 남은 일자가 단조 내림차순인 것들을 찾아 묶으면 된다) // 기..
22.03.30. 풀었던 문제들
1. 구명보트 greedy / two-pointer느낌도 난다. vector를 정렬해서 max값 + min값이 limit보다 크면 둘다 보트에 태우고, 그렇지 않다면 max값만 보트에 태우면 된다. 2. 삼각 달팽이 규칙 찾기 + 구현 문제다. 3. 주식가격 pq를 잘 이용해 보는 문제였다. -> 같은 방법으로 stack으로도 풀린다... prices를 앞에서부터 하나씩 pq에 넣는다. (pq의 top은 넣은 값 중 최댓값이 올라오게 한다) prices[i] 이에 따른 처리를 해 주면 된다. prices[i] >= pq.top()이 될 때 까지 pq.pop()을 해 주고, pq.top()에 있는 것의 index와 prices[i]와의 in..
22.03.29. 풀었던 문제들
* stringstream, istringstream 정리하기 * dp * 빠른 피보나치 구하기(고속행렬곱) programmers lv. 2 1. 피보나치 수 기본적으로는 db로 풀면 된다. 시간복잡도가 올라가면, 고속 행렬 곱으로 풀면 된다. 2. 최솟값 만들기 규칙 찾기 문제다. 3. 최댓값과 최솟값 string parsing 문제이다. 그냥 for문 돌려서 풀 수도 있지만.. 아무래도 stringsteam을 공부하긴 해야 겠다. istringstream도 한번 봐 보자. 4. 다음 큰 숫자 2진수에서 1의 개수를 세는 방법이다. 이것도 정리해 보자. 5. 땅따먹기 되게 유명한 DP 문제다. land[i]를 보고 있을 때, land[i+1]에서 최댓값을 뽑기 위해서..
22.03.28. 풀었던 문제들
유클리드 호제법 시간복잡도 증명 programmers lv.2 1. N개의 최소공배수 gcd / lcm 문제였다. 2. JadenCase 문자열 만들기 기초 문자열 다루기 문제였다. toupper, tolower 함수를 쓰면 된다. *기억하자! toupper, tolower 함수는 cctype header에 있다. 3. 행렬의 곱셈 슈트라센 알고리즘까지는 아니어도, cache를 이용한 행렬곱까지는 기억해 두자. http://www.secmem.org/blog/2021/03/20/strassen-algorithm/ 지금까지 풀었던 문제 따라잡으려면 30문제쯤 남았는데... 그때그때 생기는 정리해야 하는 알고리즘 정리하면서 풀면 끝이 없을 것 같다. 그래서 정리해야 하는 알고리즘은 포스..
22.03.27. 풀었던 문제들 *** 정규표현식 정리하기
1. 크레인 인형뽑기 게임 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 2. 키패드 누르기 간단한 구현 문제였다. 3. 숫자 문자열과 영단어 string 문제였다. 침착하게 잘 풀어보자. 특히 string parsing을 할 때 index가 잘 저장되는지 기억하자. 그리고 정규표현식으로 이 문제를 쉽게 풀 수 있다. 정규표현식도 정리해 보자. 4...
22.03.26. 풀었던 문제들
1. 나머지가 1이 되는 수 찾기 기초 반복문 문제였다. 2. 두 개 뽑아서 더하기 중복을 허락하지 않고, 정렬되어 있는 set 자료구조의 특징을 이용하면 쉽게 풀 수 있다. 3. 3진법 뒤집기 string 기본 문제였다. 4. 내적 loop 기본 문제였다. 5. 약수의 개수와 덧셈 simple for문이 아니라 조금 더 시간복잡도를 줄여보자. 6. 음양 더하기 기본 loop문이었다. 7. 없는 숫자 더하기 set으로 풀었지만... 그냥 총 합에서 빼는 방법도 있다. 8. 폰켓못 set으로 풀었다. set에 vector들의 원소를 넣고 싶을 때는 for문을 사용해서 하나하나 삽입해 주어도 되지만 초기화 하는 방법이 있으니 이를 참고하자. 9. 소수..
22.03.25. 풀었던 문제들
1. 약수의 합 brute-force 기초 문제였다. 2. 소수 찾기 에라토스테네스의 체를 이용해야 한다. 소수 판정법 등에 대해서는 나중에 포스팅 해 보자. 3. 최소공배수와 최대공약수 유클리드 호제법 - gcd, lcm 알고리즘에 대해 정리해 보자. 시간복잡도는 log(min(a, b))이다. 4. 최소직사각형 간단한 greedy 문제였다. 5. 부족한 금액 계산하기 언제나 문제 조건에 따른 자료형의 길이를 잘 생각해 두자. 6. 2016년 for문의 시작 idx를 잘 보자.