PS
22.06.21. 풀었던 문제들
1. GPS bellman-ford로 푸는 문젠가? 싶어서 생각해 봤는데 '잘못된 길'을 찾는 시점부터 뭔가를 해결하려 하면 끝이 없을 것 같아서 포기 DP라는 걸 알게 되어서 dp[i][j]를 time i to j까지 최소수정 횟수를 두려 했는데, 이렇게 해서 dp[0][0]부터 시작하려 했다. 그런데 음... 아니었다. {0, 0}, {1, 1}, ... {n, n}을 고치고 {0, 1}, {1, 2}, ... 를 고치는 방식은 모든 위치 정보를 넣어야 하기도 했다. 시간 초과가 날 알고리즘이기도 했고. 그래서 다른 방식을 고민하다 ㅏ아... 모르겠다 싶어서 구글링 dp[t][l] = 시간 t의 위치가 l일 때, 시간 0부터 t까지경로를 수정해야 하는 최소 횟수로 생각하면, dp[t][l] = min..
22.06.19. 풀었던 문제들
1. 몸짱 트레이너 라이언 푸는 중... 겹치는 사람 수는 누적합으로 쉽게 구할 수 있다. 처음에는 backtracking으로 풀려 했는데 최악의 시간인 100C50의 경우 1억을 훨씬 초과한다. 그래서 case by case를 세웠는데, 겹치는 사람 수가 n*n/2 + n%2(chessboard처럼 배열)보다 크다면 무조건 거리는 1이다. 잘 모르겠어서 구글링을 했고, 모든 경우의 탐색보다는 '거리가 d일 때 k개를 배열에 둘 수 있는가?'를 탐색하는 것으로 바꾸어 생각하면 풀린다고 한다. 생각해 보면, 새로 locker는 직전에 놓은 locker와 거리가 d인 위치에 놓게 하고(O(1)), 지금까지 놓은 locker들을 순회하면서 거리가 d 이상인지 검사해야 하고locker(O(50)) 최대 거리는 ..
22.06.18. 풀었던 문제들
1. 캠핑 처음에는 O(n^2)으로 풀어야 하는 문젠데, 어떻게 O(1)또는 O(logn)만에 좌표가 사각형 안에 있는 걸 판별하지 ? 라고 생각했다. 이렇게 판별하려면 좌표평면 안에 모든 좌표에 대한 정보를 넣어야 하는데 좌표의 범위가 int이므로 이 또한 불가능했다. 잘 모르겠어서 구글링 해 보니 좌표압축 후 누적합으로 푸는 문제였다. 좌표압축은 처음 들어보는 알고리즘이다! 신박했다. https://puzzle-puzzle.tistory.com/entry/2017-%EC%B9%B4%EC%B9%B4%EC%98%A4-%EC%BD%94%EB%93%9C-%EC%98%88%EC%84%A0-%EC%BA%A0%ED%95%91 // 캠핑 #include #include #include #include #includ..
22.06.17. 풀었던 문제들
1. 백준 1717 집합의 표현 union-find 기초 구현 문제 2. 사라지는 발판 첫 접근은 - A, B 둘 다 이동할 수 있는 경로로 이동하되 전체 게임의 수가 제일 긴 것을 리턴하게 했는데... 이러면 A가 이길 수 있는 상황에서도 지는 경우로 가는 수가 생긴다. 즉 잘못된 풀이다. 잘 모르겠어서 구글링 한 결과 접근은 아래와 같다. 현재 플레이어가 어떤 수를 택하고, 다음 플레이어가 어떤 수를 택했을 때 다음 플레이어가 승리 가능한 수가 있을 때 : 승리할 수 있는 수를 선택할 것이다. 다음 플레이어가 무조건 패배할 때 : 최대한 게임을 길게 끌고 갈 것이다. 종료 조건은 더 이상 움직이지 못할 때, 승리자는 현 플레이어가 아닌 플레이어이다. 에서 시작한다. 위 접근으로, '현 ..
22.06.16. 풀었던 문제들
1. 카드 짝 맞추기 너무 귀찮았다. 크게 3단계로 나눌 수 있는데 현재 위치부터 1번 입력으로 이동할 수 있는 좌표 list 구하기 구현으로 풀 수 있음 현재 위치부터 모든 점까지 거리 구하기 바로 위의 함수와 BFS를 이용해 풀 수 있음 backtrack으로 카드를 뒤집는 모든 종류를 구하기 한 카드를 뒤집으면 그 카드의 pair도 바로 뒤집는 게 제일 효율적이다. 따라서 한 카드를 뒤집고자 하면 '현재 위치 ~ 그 카드의 위치' + '그 카드의 위치 + 그 카드의 pair의 위치' + 2만큼의 count가 더해진다. 이걸 이용해 backtrack하면 된다. // 카드 짝 맞추기 #include #include #include #include #include #include #include using..
22.06.15. 풀었던 문제들
1. 양과 늑대 처음에는 현재 미탐색인 양으로부터 visited까지 올라오면서 추가 가능한 양들만 계속 탐색해 나갈려고 했는데 너무 복잡해졌다. 조금 검색해서 DFS란 걸 알았고 이걸 아니까 쉽게 풀리는 문제였다. 먼저 candidates vector는 현재까지 visited인 것들의 child vector이다. 즉, 탐색 가능한 후보군 vector이다. can_go vector는 정말 갈 수 있는 node들만 넣은 것이고, candidates[i]가 true이고 해당 node를 추가함으로써 늑대 숫자가 양 숫자보다 크거나 같아지면 탐색 불가능이므로 그렇지 않을 때만 node를 넣는다. 이후에는 can_go 내의 node들로 DFS를 한다. DFS 할 때에는 node를 사용했으므로 candidate[no..
22.06.14. 풀었던 문제들
1. 블록 이동하기 어제 시간 없어서 못 풀었던 문제 풀었다. 전체적으로 구현이 귀찮은 문제였다. 신경 쓸 것도 많았고. 로직 자체는 간단한 BFS이지만 1) visited 배열 - 로봇의 위치는 점 2개로 이루어지기 때문에 점 2개를 이용해서 중복 검사를 할 수 있게 해야 했기 때문에 ppiipii를 항상 정렬한 상태로 유지했다. 2) 이동 가 / 불 여부 - 현재 위치 (r, c), (r', c') 기준으로 어디로 이동할 수 있는가?를 조금 생각해 주어야 했다. a) 직선 이동하는 경우 - 위 / 아 / 왼 / 오 - 모두 다 범위 안이고 0이어야 이동할 수 있음. 이건 쉽지만 b) 회전 이동하는 경우 - (r, c)을 축으로 90도 - 이게 귀찮았다. 물론 이동 후 위치도 0이어야 이동 가능하겠..
22.06.12. 풀었던 문제들
오늘은 정기외출이었던 관계로 연등 때 1문제만 풀려 했는데... https://army.goorm.io/ https://military22.elice.io/ 두 곳의 사전테스트로 인해서 오늘 공부는 패스. 사전테스트는 패스했다. 사전 테스트는 python을 이용한 뭔가였는데 만점 받았다! 이제 프로그래머스 슬슬 끝나가니까 AWS EC2(무료 컨테이너)를 이용해서 vs code 서버나 하나 만들어 보자. 사지방 로컬은 매번 초기화되니까 하나 있어야 하지 싶다.
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..
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. ..