전체 글
22.06.11. 풀었던 문제들
1. 광고 삽입 처음 접근은 two-pointer로 풀려 했는데, two-pointer로 풀 경우 right index가 한 칸 넘어갔을 때 right index보다 작은 모든 값들에 대해 계산을 다시 해 주어야 했다 - two-pointer지만 시간복잡도에서 이득보지 못하기 때문에 pass 다음 접근은 사용자가 보기 시작하는 시간에 +1, 다 본 시간에 -1을 하고 그 구간을 저장하고, 이 구간을 이용해 풀려 했는데 위와 같은 이유로 pass 잘 모르겠어서 다른 블로그들 참고(답을 봤다)했더니 바로 위 접근에서 조금만 변경하면 되었다. 아쉽다... 방법은 모든 시간에 대해 사용자가 보는 경우 +1, 안 보는 경우 -1을 2번 누적합을 만들고 i~j까지 부분합을 이용해 풀 수 있는 문제였다. 다만 누적합..
22.06.10. 풀었던 문제들
1. 파괴되지 않은 건물 naive하게 brute-force로 풀면 O(1000 * 1000 * 25만)이어서 절대 풀 수 없는 문제. 그래서 row를 고정시키고 column에서 누적합으로 푸는 방식을 택했는데 - O(1000 * 25만)이어서 여전히 시간 초과가 난다. 해결법은 2차원 누적 합이었다. 2차원은 생각을 못하고 있었는데, 풀고 나니 재밌는 문제였다. // 파괴되지 않은 건물 #include #include #include using namespace std; int N, M; typedef pair pii; int solution(vector board, vector skill) { N = board.size(); M = board[0].size(); vector datas(N, vecto..
22.06.09. 풀었던 문제들
1. 길 찾기 게임 트리 구현이다. 오랜만에 이런 것 구현할려니까 까먹은 게 많다. 먼저 높이가 높은 순대로 map에 저장. 이렇게 저장한 map에서 key가 높은 것부터 tree에 넣을 것임. 유의할 점은 node 할당 시 node *root = new node를 써야 한다는 점. 그리고 현재 보고 있는 node의 x값이 parent보다 작으면 왼쪽, 크면 오른쪽에 넣는 binary tree의 삽입 방식을 이용해서 tree에 계속 넣어준다. 만약 parent->child가 NULL이면 그 부분에 cur_node를 넣어주면 된다. 이렇게 tree를 만들었으면 traversal이다. preorder는 값 넣은 이후 탐색이고, postorder는 탐색 이후 값 넣기이다. 구현이 귀찮은 문제였다. // 길 찾..
22.06.08. 풀었던 문제들
1. 추석 트래픽 생각보다 간단한 문제였음. 로그 갯수가 바뀌는 위치 : 각 로그의 시작점 또는 끝점이다. 또한 greedy하게 시작점은 탐색할 필요가 없는 게, 앞에서 이미 탐색되는 위치이기 때문(끝점 탐색하면서) 따라서 끝점만 탐색하면 된다. 끝점 기준으로 +1초 탐색하면 됨 2. 셔틀버스 시간이 작기 때문에 그냥 시뮬레이션 돌려도 된다. 시간 뒤에서부터 탐색, 탈 수 있으면 break, 못타면 계속 탐색. 탐색 시 crew의 대기시간이 버스도착시간보다 크면 bus index 증가, 그렇지 않으면 bus값에 1 빼줌. 그러고 만약 bus가 가득 차면 bus index++. 이 때, '나'의 시간이 crew 시간보다 작고 버스 도착시간보다 작다 -> 나는 버스에 탈 수 있다. (크루 도착시간이 ..
22.06.07. 풀었던 문제들
1. 자물쇠와 열쇠 처음에는 자물쇠 부분에서 0이 있는 부분만 따로 떼어 생각하려 했는데 - 이러면 자물쇠의 1부분과 열쇠의 1부분이 겹칠 수 있어서 이 생각은 접음 그래서 자물쇠를 keysize * 2 - 2 + locksize만큼 resize하고 가운데 lock을 넣어서 탐색했다.
22.06.06. 풀었던 문제들
4시간동안 고민했던 브라이언의 고민... 이런 고민은 좀 하지 마라.. 1. 브라이언의 고민 너무너무 어렵게 풀었다. 처음 접근은 'rule 2가 적용된 모든 것들을 풀고, 이후에 rule 1이 적용되어 있는 것을 풀어야지' 했는데 이것저것 반례가 계속 튀어나와 덕지덕지 테이프칠하다 보니 너무 더러워져서 다시 깔끔하게 풀기로 했다. 먼저. 어떤 s[i]를 봤을 때 2가지 경우의 수가 있다. 1) 대문자 - rule 1이 적용되었거나, 아무것도 적용되지 않은 경우 - 따라서 다음 글자가 대문자이면 s[i]를 정답 vector에 붙여넣는다. - 다음 글자가 소문자이면 해당 소문자의 개수가 2가 아니라면 rule 1을 적용한다. (2라면 rule 2를 적용시킬 것임) 2) 소문자 - rule 2가 적용되었..
22.06.05. 풀었던 문제들
1. 3 x n 타일링 2 x n 타일링이 lv3에 있는데 이건 왜 lv2에 있는지 모르겠다. ㅋㅋㅋ 아 그리고 이중for문말고 점화식이 하나 존재한다. dp[i] = 4 * dp[i-2] + dp[i-4]인데. 규칙이 그런거지 왜 이런 규칙이 나왔는진 잘 모르겠다. 2. 불량 사용자 규칙을 찾으려 했는데, 사이즈가 8인 걸 보고 그냥 순열 탐색으로 풀었다. 중요한 점은 마지막에 중복 검사를 해 주어야 했다는 것. 3. 카카오 인턴 문제랑 dev-matching 문제 풀고 싶당
22.06.04. 풀었던 문제들
1. 보석 쇼핑 투포인터로 푸는 문제. 처음 접근은 제일 뒤에서부터 앞으로 당길 수 있을 만큼 당기고 이후에 앞에서 밀 수 있을 만큼 뒤로 미는 방식을 택했는데 반례가 존재해 다른 풀이로 풀어야만 했다. 다음 접근은 start, end를 0으로 두고 end를 1칸씩 뒤로 민다. 그리고 start~end-1 사이에 보석별 개수를 담는 map um을 뒀고 um에 2를 초과하는 값이 있다면 뒤로 민다. 그리고 같은 길이라면 앞에 있는 것을 가져오기 때문에 min_len > e-s라는 것을 해야 하고, 또 s~e 사이에 모든 보석이 있어야 하므로 다음과 같은 식을 취했다. 다만 처음에는 end를 -1로 두고 while(e < gems.size()-1)을 취했는데(e가 제일 마지막 index를 가리키는 방식으로)..
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..