PS/PS Log
22.06.03. 풀었던 문제들
1. 숫자 블록 찾아보니 lv4였던 문젠데 lv2로 격하된 문제다. 잠깐만 생각해 보면 그렇게 어렵지 않음을 알 수 있다. 규칙은 '해당 숫자의 약수 중 본인을 제외한 가장 큰 수'를 채워넣는 것이 규칙이다. 그러면 10000개의 수에 대해 최대 10억 size의 약수를 구해야 하며 - sqrt(10억) = 3만 정도이다. 또한 최대 블록의 수가 1000000이므로 약수가 이것을 초과한다면 더 작은 약수를 구해야만 할 것이다.
22.06.02. 풀었던 문제들
한 10일 쉰 것 같다! 그동안 탁구 배우면서 잘 쉬었던 것 같다. 외박도 다녀왔고 이제부터 다시 열심히 공부해야겠다! 1. 경주로 건설 일단 graph 문제이고, 최소값을 리턴하기 때문에 -> dijkstra를 사용해야만 한다. 그리고 v[max_r][max_c]를사용하는 것이 아니라, v[max_r][max_c][max_dire] 이렇게 3차원 배열로 풀어야만 하는 문제였다. 이렇게 해야 하는 이유는 반례가 있기 때문이다. 생각해 보자. (n, n) 좌표가 도착지점이다. 그리고 (n, n-1)지점이 (n, n)으로 갈 때 최솟값 경로에 속해있는 값이라 치자. 이 때, (n, n-2) 지점에서 오는 것과 (n-1, n-1)지점에서 올 때는 값이 달라질 수 있다. 아래 예제와 같이 (n-1, n-2)..
22.05.22. 풀었던 문제들
1. 징검다리 건너기 제일 처음 접근은 '어떤 index i부터 i+k-1까지 max값들 중 min값이 답이다'였는데, 이렇게 풀면 답은 맞지만 O(n * (n-k))이므로 O(n^2)이고, n은 max 20만이므로 시간초과가 난다. int solution(vector stones, int k) { int answer = 0; int size = stones.size(); int min_value = 2100000000; for(int i = 0; i 이분 탐색으로 풀 수 있다 가 떠오른다. 계산해 보면 32 * 20만 -> 640만이므로 시간 내에 풀 수 있을 것이라 예측된다. #include #include #include using namespace std; bool isPassable(int nu..
22.05.20. 풀었던 문제들
1. 순위 플로이드 와샬로 쉽게 풀 수 있는 문제. 플로이드-와샬은 모든 노드로부터 모든 노드까지의 거리를 알아내는 알고리즘. 플로이드-와샬 결과로써 from-to에 edge가 n-1개 있다면 순서를 매길 수 있다는 것임.
22.05.18. 풀었던 문제들
1. 모두 0으로 만들기 leaf부터 탐색하면 최적값이 나올 거라 생각해서 unvisited edge가 1인 node들부터 차곡차곡 방문하고, 해당 node와 adjacent한 node들의 edge 개수를 갱신하려 했는데 이러면 너무 복잡하다. 그럴 필요 없이, 트리 후위 순회를 돌려버리면 leaf부터 방문하니 상관없고, 해당 문제의 경우 'tree임이 보장되어 있으므로 어느 점을 root로 잡든 leaf는 생긴다...' 2. N으로 표현 간단한 DP였는데 몇 가지 때문에 헷갈렸다. 1) 연산 끝에 숫자를 붙이지 못한다. 무슨 말이냐면 1(1 + 1)1로 121을 만들지 못한다. 숫자를 연속해서 만들 수 있는 것은 1, 11, 111, ...이다. 2) c를 만들 때, a + b도 되지만 b + ..
22.05.17. 풀었던 문제들
1. 아이템 줍기 사각형을 바로 채워버리면 거리가 1일 때 해당 부분이 뭉개진다! 따라서 2배로 scale-up을 해야 풀 수 있었던 문제. 2. 보행자 천국 방향성을 고려해 주어야 하는 문제였다. 처음에는 회전금지 신호가 있으면 위/또는 아래에서 해당 값을 받아오는 형식으로 구현했는데 이렇게 하면 연속된 회전금지 신호일 경우 잘 나타나지 않았다. 그래서 '현 위치에서 r방향/c방향으로 갈 수 있는 경우의 수'를 만들었다. 그래서 2d vector of pii로 구현했다. dist[r][c].first는 r, c에서 r방향으로 갈 수 있는 경우의 수, .second는 c방향으로 갈 수 있는 경우의 수이다. // 보행자 천국 int MOD = 20170805; typedef pair pii; // ..
22.05.16. 풀었던 문제들
1. 입국심사 binary search로 풀 수 있는 문제. 다만 형변환을 조심했어야 했다... 이것 때문에 시간을 날림. // 입국심사 using namespace std; typedef long long ll; ll isEnough(vector times, ll t){ ll cnt = 0; for(int i : times){ cnt += (ll)t/(ll)i; } return cnt; } long long solution(int n, vector times) { long long answer = 0; ll l = 1L, r = (ll)(*max_element(times.begin(), times.end())) * n, mid; while(l < r){ mid = (l+r)/2; ll pass_num ..
22.05.15. 풀었던 문제들
1. 110 옮기기 어려워 보이는 문제였는데 해답은 간단하다. 1) 110을 제거하고, 110을 제거함으로써 생기는 모든 110도 제거한다. 2) 그렇게 남은 문자열에서 제일 뒤에 있는 0 바로 뒤에 모든 110을 넣는다. 이렇게 되는 이유는 '110'은 1보다는 앞에 와야 하고(1101보다 1110이 더 느리다) 0보다는 느리게 와야 한다(0110보다 1100이 더 느리다) 즉슨 모든 0보다 110이 뒤에 와야 한다는 말이다. 한편 110을 삽입함으로써 0의 위치는 삽입한 110의 0이 된다. // 110 옮기기 #include #include #include using namespace std; string solve(string s){ int cnt= 0; for(int i = 0; i= i+3){..
22.05.14. 풀었던 문제들
1. 가장 긴 팰린드롬 내가 작성한 코드의 문제점을 찾았다. 나는 index i부터 index j까지 palindrome인지 검사하는 식으로 잡았는데, 이러면 2중 for문 + palindrome 검사문의 시간이 O(s.length())이므로 총 합해서 O(n^3)으로 풀고 있었던 것이다. 그래서 좀 더 효율적인 방법을 생각했다. 첫 번째 for문은 검색 index의 중간점을 두고, i에 따라 좌우로 검색할 수 있는 string max 길이를 계산한다. 그리고 짝수/홀수인 경우에 따라 string length를 1칸씩 늘려가면서 검사한다. string length가 1일 때는 무조건 팰린드롬, 2 이상일 때는 문자가 같은지 검색해 나가야 하는데, 기존 검색되어 있는 내용을 이용하는 것이다. // 가장 긴..
22.05.13. 풀었던 문제들
1. 가장 긴 팰린드롬 시간 초과가 계속계속 난다... 그래서 최대한 줄이기 위해 긴 문자열부터 검색을 진행하고, 추가 함수도 사용하지 않고 s.substr도 사용하지 않고 index와 length만으로 검사를 하는데 잘 안된다...으으으으윽 내일 다시 봐야겠다.... 그리고 lv3 오니까 좀 어려운 문제가 많아지긴 했다. 2. 2 x n 타일링 문제를 잘 살펴보면 n개를 채우는 방법 - 1개짜리 n개로만 채우는 방법 = nPn (1) - 2개짜리 1개, 1개짜리 n-2개 = (n-1)! / (n-2)! - 2개짜리 2개, 1개짜리 n-4개 = (n-2)! / (n-4)! 이렇게 된다. 그러나 이렇게 구하면 답이 없는게 n이 6만이기 때문이다. 따라서 다른 방식을 취해주어야 한다. 잘 살펴보면 n..
22.05.12. 풀었던 문제들
1. 스티커 모으기(2) DP문제이다. dp[i]는 i번째 스티커까지 봤을 때 최댓값이라고 두면 점화식은 dp[i] = max(dp[i-1], dp[i-2] + sticker[i])이다. max 함수에서 전자는 i번째 스티커를 떼지 않는 경우이고 후자는 i번째 스티커를 떼는 경우이다. 그리고 이 문제의 경우 0번째 스티커를 떼면 마지막 것을 떼지 못하므로 이에 대한 예외처리도 해 주어야 한다. 2. 기지국 설치 그냥 풀면 되는 문제. 3. 스타 수열 꽤 빡셌다. 일단 모든 숫자들이 나온 횟수를 저장하고, 모든 숫자로 brute-force하게 탐색해야 하는 건 맞다. 그러나 조금 최적화가 빡셌다. 마음같아서는 a배열 한번만 탐색하면서 찾는 방법을 찾고 싶은데.... // 스타 수열 #incl..
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...