PS
22.07.12. 풀었던 문제들
백준 단계별 19 스택 10828 스택 10773 Zero That Out 9012 Parenthesis 4949 The Balance of the World 1874 스택 수열 17298 오큰수 백준 단계별 20 큐, 덱 18258 큐 2 2164 카드2 11866 요세푸스 문제 0 1966 Printer Queue 10866 덱 1021 회전하는 큐 5430 Interger Lists
22.07.11. 풀었던 문제들
Codeforces #787 Div. 3 Upsolving F 백준 단계별 18 greedy 11047 동전 0 1931 회의실 배정 11399 ATM 1541 잃어버린 괄호 13305 주유소
22.07.10. 풀었던 문제들
BOJ 단계별 17 누적합 11659 구간 합 구하기 4 2559 수열 - partial sum으로 해도 되고, sliding window로 풀어도 된다. 근데 문제 특성상 k가 주어지기 때문에 sliding window로 푸는 게 더 쉬울 듯. 16139 인간-컴퓨터 상호작용 - 알파벳 별로 누적합을 만들어야 했음 10986 나머지 합 - 흥미로운 문제. psum을 구할 때 % 연산을 하고, 해당 값이 몇 번 나왔는지를 기록한다. 그리고 모든 %값의 개수에 대해, combination 2를 택해주고(% M이 같은 두 구간을 뺀다면 그 구간은 M의 배수이다. 이 구간 중 순서 상관없이 2개를 택하는 경우의 수), 마지막으로 0이 나온 횟수(첫번째부터 i까지 %K == 0이라는 의미)를 더해주면 된다. i..
누적 합 Prefix Sum
어떤 배열 arr에 대해 prefix sum 배열을 만들어 배열의 index i부터 index j까지의 합을 O(1)으로 풀 수 있는 알고리즘. 배열의 크기가 $O(n^{k})$일 때 초기화는 $O(n^{k})$, 구간 합을 구할 때는 O(1)의 시간이 걸린다. 특정 구간의 합을 구하는 것이기 때문에 해당 구간의 값이 변화하지 않는 것을 통해, 특정 구간 안에 원소가 있는지 없는지도 쉽게 계산할 수 있다.(2차원도 적용 가능) range sum을 구할 때 index를 주의하도록 하자. 1. 1차원 Prefix Sum : 초기화 $O(n)$, 쿼리당 O(1) range sum을 구할 때, start가 0이면 -1로 out of bound가 되어버리므로 start가 0일 때만 예외 처리를 해 주자. // r..
동적 계획법 Dynamic Programming (+ LIS)
DP의 정의는 '복잡한 문제를 간단한 문제로 나누어 풀고, 이 subproblem으로 원 문제를 푸는 것'이다. 어떻게 보면 divide-and-conquer과 유사하지만, DP의 경우 subproblem이 중복되기 때문에 좀 더 빠른 시간으로 풀 수 있다. 그렇기 때문에 필자는 DP의 핵심이 memoization과 recursion relation(점화식)의 2가지라 생각한다. memoization으로 이미 계산 한 값이라면 그 값을 return하고, recursion relation으로 계산한 값을 이용해 다음 값을 빠르게 구할 수 있다. 예제 : 냅색 if j - cost[i] >= 0 then dp[i][j] = max(dp[i][j], dp[i-1][j-cost[i]] + value[i]) el..
22.07.09. 풀었던 문제들 - Codeforces #787 Div. 3 4/7 *** euler tour, path, circuit
BOJ DP 11054 가장 긴 바이토닉 부분 수열 2565 전깃줄 9251 LCS 12865 평범한 배낭 9465 스티커 (DP) void solve(){ int n; cin>>n; vector stickers(2, vector(n)); for(int i = 0; istickers[i][j]; } } vector dp(2, vector(n, 0)); // dp[i][j] : i번째 row, j번째 col의 sticker를 선택했을 때 최댓값 dp[0][0] = stickers[0][0]; dp[1][0] = stickers[1][0]; if(n >= 2){ dp[0][1] = dp[1][0] + stickers[0][1]; dp[1][1] = dp[0][0] + stickers[1][1]; } for(..
22.07.07. 풀었던 문제들
BOJ 단계별 DP 1단계 1463 1로 만들기 10844 쉬운 계단 수 2156 포도주 - 이문제.. 빡세다 #define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pis; int main(void) { cin.tie(0); cout.tie(0); std::ios_base::sync_with_stdio(0); ////////////////////// write your code below int n; cin>>n; vect..
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 스타트와 링크
2022 현대모비스 SW 알고리즘 경진대회 예선 참가 (22.07.01.)
경험삼아 이것저것 나가보는 중. 1번 - map을 이용해서 간단하게 풀 수 있었음 2번 - priority queue를 이용한 BFS 3번 - Trie (문자열 tree) 4번 - BFS 5번 - 모르겠음. 한 2.5솔 한 것 같다. 결과 1번, 4번은 올솔, 2번은 1/3솔이다. 팡탈.
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..
좌표 압축
값의 대소 관계만 필요하다면 수를 바꾸어 사용할 수 있다. 예를 들어 [0, 1, 5, 6, 11] 이런 좌표라면 [0, 1, 2, 3, 4]로 바꿀 수 있고, [0, 100, 150, 50, 175, 50, 50] 이런 좌표라면 [0, 2, 3, 1, 4, 1, 1]로 바꿀 수 있다. 방법은 크게 2가지가 있다. vector의 unique 값을 지우고 lower_bound로 해당 값을 찾는 방법 set으로 중복을 지우고 map으로 압축된 좌표를 mapping하는 방법 1. vector의 unique 값을 지우고 lower_bound로 찾는 방법 : O(nlogn) void gridCompress(vector &arr){ vector temp(arr.size()); for(int i = 0; i
22.06.28. 풀었던 문제들
백준 단계별 정렬 2750 수 정렬하기 2751 수 정렬하기 2 10989 수 정렬하기 3 2108 통계학 1427 소트인사이드 11650 좌표 정렬하기 11651 좌표 정렬하기 2 1181 단어 정렬 10814 나이순 정렬 18870 좌표 압축 정수론 및 조합론 귀차낭
정렬 ***TODO
stable sort는 정렬을 했을 때 중복된 값들의 순서가 변하지 않는 sort. 변한다면 unstable이다. 아래 정렬들은 stable. Bubble Sort, Insertion Sort Counting Sort Merget Sort in-place sort는 추가적인 메모리가 거의 들지 않는 sort. 아래 정렬들은 in-place. Bubble Sort, Selection Sort, Insertion Sort Quick Sort, Heap Sort Implenentation of Sort Bubble Sort : $O(n^{2})$ - Stable and In-Place Sort array의 값 2개를 비교해서 비교함수를 만족하지 않는다면 swap하는 방식 for(int i = 0; iN>>IN..
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..
알고리즘 하면서 공부해야 할 것들 & 고쳐야 할 것들 & 알면 좋은 것들 ** TODO
* 알고리즘/DB/AI/OS/아키 수업 들었던 과제 / ppt / 정리한 것 글로 작성해 보기 * 기하 - 신발끈 공식 * 작성중인 정렬 게시글(insertion sort, bubble sort, selection sort, count sort, radix sort, quick sort, merge sort, heap sort) * sliding window, two pointer, meet in the middle * dp + LIS + trackback * backtrack * DFS 코드 정립 * vector erase vs remove * KMP 알고리즘 * euler tour, path, circuit * 백준 단계별 위상정렬까지 끝나면 DP나 누적합, 시뮬레이션 등 문제별 풀이 하면서 해 보자..
나중에 다시 풀어 볼 문제들
뭔가 구현이 특이했거나, 제대로 못 풀었거나, 어려웠던 문제들이다. 까마득하네요... DP 약하다. 도전하자. 프로그래머스 [1차] 비밀 지도 크레인 인형뽑기 [1차] 다트 게임 숫자 문자열과 영단어 키패드 누르기 삼각 달팽이 주식가격 기능개발 큰 수 만들기 H-index 2개 이하로 다른 비트 다리를 지나는 트럭 조이스틱 교점에 별 만들기 124 나라의 숫자 예상 대진표 단체사진 찍기 행렬 테두리 회전 캐시 [1차] 프렌즈4블록 [3차] 압축 [3차] 파일명 정렬 [3차] 방금그곡 후보키 문자열 압축 수식 최대화 거리두기 확인하기 순위 검색 주차 요금 계산 디스크 컨트롤러 양궁대회 단속카메라 숫자 게임 스타 수열 가장 긴 팰린드롬 공 이동 시뮬레이션 110 옮기기 풍선 터트리기 징검다리 건너기 신규 아..
PS 하면서 알면 좋은 STL들
Range Iteration(범위 반복) C++의 모든 container들은 range iteration을 통해 간편하게 container를 순회할 수 있다. - sequence container : vector, deque, list - container adapter : stack, queue, prority_queue - associate container : set, unordered_set, multiset, map, unordered_map, multimap, bitset for(auto i : container) ... 입/출력 관련 STL 소수점 아래 n자리 출력 아래 예시는 고정시켜서 10개를 출력하는 함수이다. cout
PS 하면서 알면 좋은 알고리즘들
약수 구하기 : O(n^0.5) 내 블로그 포스트에서 정리했다. set getFactorNumber(int n){ set v; for(int i = 1; i target) // 중간값이 target보다 큰 경우 해당 index까지 end를 당김. end = mid; else start = mid + 1; // 중간값이 target보다 작으면 mid+1까지 start를 당김. } return end; } // STL 이용 #include binary_search(v.begin(), v.end(), value); lower_bound(v.begin(), v.end(), value); // 결과로 iterator가 리턴됨 lower_bound(v.begin(), v.end(), value) - v.begin(..
PS 하면서 알면 좋은 SQL들
Max SELECT MAX(A) FROM S; Group By group에 대한 조건은 having으로 함 SELECT A FROM S GROUP BY NAME HAVING COUNT(*)>1 ORDER BY NAME ASC; HOUR datetime을 시간으로 바꿔주는 함수 SELECT HOUR(DATETIME), COUNT(*) FROM ANIMAL_OUTS WHERE HOUR(DATETIME) >= 9 AND HOUR(DATETIME)
대회 일정
1. ucpc https://ucpc.me/ - 참가 신청 : ~2022. 06. 23.(목)까지 - 예선 : 2022.07.02. (토) 14시~17시 / 온라인 - 본선 : 2022.07.23. (토) 11시~16시 / 오프라인, 스페이스쉐어 삼성 COEX센터(강남) 2. cps festival https://www.cpsfestival.org/ - 접수 : 2022. 6. 13.(월)-7. 18(월) / 온라인 - 예선 : 2022. 7. 25.(월) - 8. 1(월) / 온라인, 시간 내에만 하면 됨 - 본선 : 2022. 8. 27(토) 14시 / 호텔인터불고대구 컨벤션홀(대구 수성구) - 시상식 : 2022. 11. 16.(수) 이거 예선 온라인 방식이 팀장이 문제를 제출하는 방식이라 하루..
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