전체 글
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)
[Spring] Spring Boot MVC 개념 이해
SWM 프로젝트로 spring을 이용해 BE 구성을 하지 싶다. 그래서 배워보고자 spring을 이용해 게시판 CRUD를 해 보자. 개인적으로, Node.js에 비해 Spring이 진입장벽이 더 높은 것 같긴 하다. 나는 C++을 메인으로 학교에서 배웠기 때문에 API 코드를 짜면 그 url로 접속하면 해당 함수 내에 있는 것들만 수행된다는 것이 상당히 직관적이었기 때문이다. 그런데 Spring은 MVC 2 형태라고 해서, controller, service, DAO, servlet, DB와 연동을 위해서는 mybatis, JPA, hibernate, mapper 등, 또 그걸 쓰려면 entity, DTO, repository까지... 알아야 할 것이 너무 많다. 처음에는 "springboot 시작하기"..