PS/PS Log
22.07.06. 풀었던 문제들
BOJ 단계별 16 DP 1904 01 타일 9461 Padovan Sequence 1912 연속합 - 재밌었다. dp[i] = max(dp[i-1] + arr[i], arr[i]) 1149 RGB 거리 1932 The Triangle 2579 계단 오르기 - 오랜만에 푸니까 재밌었다. dp[i] = max(dp[i-2] + stairs[i], dp[i-3] + stairs[i-1] + stairs[i]);
22.07.05. 풀었던 문제들
UCPC upsolving BOJ 25319 Twitch Plays VIIIbit Explorer - 출제의도대로 구현, 내가 작성한 DFS 수정 Codeforce Upsolving Codeforces #797 Div. 3 - G Count the Trains 드디어 풀었다. BOJ 단계별 16 DP 24416 알고리즘 수업 - 피보나치 수 1 9184 Function Run Fun
22.07.04. 풀었던 문제들
BOJ 단계별 15 백트래킹 15649 N과 M (1) 15650 N과 M (2) 15651 N과 M (3) 15652 N과 M (4) 9663 N-Queen 2580 스도쿠 14888 연산자 끼워넣기 14999 스타트와 링크
22.07.01 풀었던 문제들
백준 정수론 및 조합론 단계 9375 Incognito 1676 팩토리얼 0의 개수 2004 조합 0의 개수 CPS 기출 CPS 9회 본선 6번 모빌 현대모비스 2022 SW 알고리즘 경진대회 1, 3, 4번 #797 Div.3 G도 풀어야 하는뎅. -> 풀었음
22.06.30. 풀었던 문제들
백준 정수론 및 조합론 단계 1934 최소공배수 2609 최대공약수와 최소공배수 1037 약수 5086 배수와 약수 2981 GRANICA 이 문제는 조금 재밌었다. 수 a, b, c, ...를 어떤 수로 나눴을 때 나머지가 같다는 것은, a = a' + r, b = b' + r, ... (a', b' c'은 어떤 수로 나눴을 때 나머지가 0)이라는 것이고 ,그러면 a - b = a'-b' = m*Q, b - c = b'-c' = m*Q1, ... 이렇게 된다. 그렇다면 결곡 arr[0] - arr[1], arr[1]-arr[2], ...들의 최대공약수가 m이 되고, m의 약수들은 모두 답이 된다. 3036 PRSTENI 11050 이항 계수 1 11051 이항 계수 2 : 파스칼 삼각형 이용한 DP 1..
22.06.29. 풀었던 문제들 - Codeforce #797 Div. 3 4/7
오늘은 Codeforces Round #797 Div. 3를 풀었다. https://codeforces.com/contest/1690 Dashboard - Codeforces Round #797 (Div. 3) - Codeforces codeforces.com 결과 A, B, C, D번은 시간 내에 풀고 제출했다. 7문제 중 4문제를 맞췄다. A번 규칙 찾기 문제 // x + x-1 + x-2 = 3x-3 int h1 = (int)ceil((double)(n+3)/3); int h2 = (n - h1)/2 + 1; int h3 = n - h1 - h2; B번 간단한 문제였지만 범위 조절이 중요했다. b[i]가 0이 아닐 때 a[i] - b[i]의 차이의 min값을 저장하고, a[i] - min_value..
22.06.28. 풀었던 문제들
백준 단계별 정렬 2750 수 정렬하기 2751 수 정렬하기 2 10989 수 정렬하기 3 2108 통계학 1427 소트인사이드 11650 좌표 정렬하기 11651 좌표 정렬하기 2 1181 단어 정렬 10814 나이순 정렬 18870 좌표 압축 정수론 및 조합론 귀차낭
22.06.26. 풀었던 문제들
백준 브루트 포스 단계 2798 JACK 2231 Digit Generator 7568 덩치 1018 체스판 다시 칠하기 1436 영화감독 숌 집합과 맵 단계 10815 숫자 카드 14425 문자열 집합 1620 나는야 포켓몬 마스터 이다솜 10816 숫자 카드 2 1764 듣보잡 1269 대칭 차집합 11478 서로 다른 부분 문자열의 개수 기하 1단계 1085 직사각형에서 탈출 3009 CETVRTA - 입력 3개 중에서 1개인 걸 찾는 문젠데... a, b, c라 치면 a^b^c로 그걸 찾을 수 있다. 와우. 4153 Egypt 3053 HERMAN
22.06.25. 풀었던 문제들
acmicpc 기본 수학 1단계 1712 손익분기점 2292 벌집 1193 분수찾기 성공 2869 PUŽ 10250 ACM Hotel 2775 부녀회장이 될테야 2839 ŠEĆER 10757 큰 수 기본 수학 2단계 1978 소수 찾기 2581 소수 11653 소인수분해 1929 소수 구하기 4948 베르트랑 공준 9020 골드바흐의 추측 재귀 단계 10872 팩토리얼 10870 피보나치 수 5 17478 재귀함수가 뭔가요? 2447 별 찍기 - 10 11729 하노이 탑 이동 순서
22.06.24. 풀었던 문제들 - Codeforce #799 Div. 4 6/8
오늘은 코드포스 #799 Div 4를 풀었다. https://codeforces.com/contest/1692 Dashboard - Codeforces Round #799 (Div. 4) - Codeforces codeforces.com 시간 다되니까 쫄깃쫄깃 하다. 결과 8문제 중 6문제 풀었다. A번, B번, C번, D번 단순히 풀면 되는 구현 문제 E번 부분합과 two-pointer로 풀어야 하는 문제. #include #include #include #include #include #include #include using namespace std; void solve(){ int n, s; cin>>n>>s; vector v(n); cin>>v[0]; for(int i = 1; i>v[i]; v..
22.06.23. 풀었던 문제들
acmicpc String 파트 풀었음. 조만간이다..! 다따라잡자! 11654 아스키 코드 11720 숫자의 합 10809 알파벳 찾기 2675 Repeating Characters 1157 단어 공부 1152 단어의 개수 2908 FILIP 5622 BAKA 2941 LJESNJAK 1316 그룹 단어 체커
22.06.22. 풀었던 문제들
이제 백준! 입출력 10926 - 입출력 문제. 그냥 손풀기로 풀었음 18108 - 마찬가지 25083 - "출력하기 위해서는 앞에 \ 붙여야 하고, \ 출력 위해서는 \\로 해야 함. 조건문 2525 2480
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를 가리키는 방식으로)..