전체보기
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 시작하기"..
대회 일정
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.(수) 이거 예선 온라인 방식이 팀장이 문제를 제출하는 방식이라 하루..
[Socket.io] 채팅 기능에 관한 고찰
실시간 채팅 구현 조금 생각을 해 보았다. 1) 온라인 -> socketio로 연결해서 실시간 통신 1.5) 백그라운드 -> FCM으로 push 알람만 보냄. 2) 오프라인 -> 아무것도 하지 않음. 다만 온라인으로 상태 변경 시, 서버에서 읽지 않은 메시지 목록을 전부 받아오면 될 듯. + 읽은 기능 구현은 users - room join table에 해당 유저가 접속한 시간을 적고, 그 시간이 갱신되면 그것보다 작은 것들의 읽은 시간을 갱신하면 될 듯. 저번에 올린 예제를 만든 파일의 경우, 인터넷 연결이 끊기면 메시지를 받을 수 없다는 문제점이 존재했다. 그래서 서버에 보낸 메시지를 저장하는 schema를 추가하려고 합니다. 형태는 ((보낸 시간, 방 번호), 보낸 사람, 메시지 내용) 정도로 ..
플젝 아이디어
deep learning / object detection 기반 - 농구 코트 및 사람 인식, 평면도로 바꾸어서 전술 분석 - 미스매치 여부, 전술별로 승률, 득점률 등을 따져서 빅데이터 만들면 재밌지 싶다. - 농구 슛/드리블 폼 분석 - pose 분석으로 가져오기 계획 세워주는 프로그램. - 책/일정 입력하면 계획 세워주는 프로그램 택시 잡아주는 프로그램. - 현재 위치 기준, 도착지까지 최단시간으로 갈 수 있는 위치로 잡아주는 프로그램. - A에서 B까지 택시타고 갈 때 A에서 택시를 호출하면 택시가 A까지 오는 위치, A에서 택시를 타고 가는 시간이 있다. - 이 시간을 줄이기 위해서 A에서 B 사이에 있는 A'이라는 위치까지 걸어가고, 택시는 A'까지 오게 해서 시간을 최소화 해주는 어플리케..
22.06.21. 프로그래머스 Lv3까지 올솔 + 이후의 목표
프로그래머스 lv1, lv2, lv3까지 전부 풀었다! 의미는 없지만 순위도 33위까지 들어왔다. 즉슨 lv3까지 모두 푼 사람이 적어도 32명이라는 거다... 이거에 안주하지 말고 더 발전하자. 또, 작성했던 '나중에 다시 풀기'가 87문제다. 이 중에서 후반부에는 내가 못 푼 것들도 많다. 나중에 다시 풀어보는 시간을 갖자! 프로그래머스를 풀면서 제일 많이 늘었다고 생각하는 건 '구현력'이다. 카카오의 기출문제가 대부분 간단한 알고리즘에 비해 + 복잡한 구현인데, 예전이었으면 함수 하나에 다 때려박았는데 지금은 함수도 잘 분할하고(해당 함수의 로직이 잘 돌아가는지 검증하기도 쉽다) 전역변수도 적극적으로 사용하고(특히 DFS나 backtrack에서) index 실수가 아니면 구현하고자 하는 걸 구현..
22.05.02. 와,, 과거의 나... 대체 뭐니..?
오늘 갑자기 옛날 포스팅들을 돌려보면서 과거 생각을 조금 했는데. 2020년 겨울에 무은재 1층에서 알고리즘 과제 10시부터 5시까지 조지고 데이터베이스 과제 조지고 시험기간에 강의 4번씩 돌려보면서 폰블서 하던 기록이 정말 새록새록하다. 그리고 알고리즘 시험을 마지막으로 시험 끝난 날 이터널 리턴 얼리억세스 시작했던 것도 기억나고, 그거를 시작으로 넵튠 주식으로 한 30% 떡상한 것도 너무 새록새록하다. 그러고 겨울 연참하다가 아... 인턴!인턴! 하면서 매일매일 인턴 뒤져보고. 그와중에 레식이랑 이리 조지고. 그랬던 내가 어쩌다 소마를 하고, 어쩌다 SW개발병까지 왔네. 소마 했을 때 kubernetes, jenkins, docker, gcp, git, spring(security, jwt token..
2022.03.22. 군대에서 PS공부 시작.
Algorithm 병 생활 중 전역 이후 알고리즘 공부 아래 네 군데서 공부할 예정 - https://www.acmicpc.net/ - https://codeforces.com/ - https://programmers.co.kr/ - https://leetcode.com/ 정보 블로그들 subinium.github.io/PS-Study-Types-and-Complements/?msclkid=d60b6cd9a9be11ecb723c667121b88da blog.naver.com/kks227 https://github.com/tony9402/baekjoon 전역 전까지 목표 최소 어디든 상위 10%까지는 찍어보기 국내 대기업 코딩테스트 안전빵으로 통과할 수 있을 정도로 역량 쌓기 대회 수상까지 노려보기 아래 ..
[개발서적] Clean Code 정리
1. 의미 있는 이름을 작성하자 누가 보든 알아보기 쉽게 변수명과 함수명을 작성하자 읽기 쉽고, 직관적인 단어를 사용하자(줄임말 말고) 코드 길이가 조금 길어지더라도 상수를 변수로 사용하자(검색의 편의를 위해) 클래스 이름 : 명사/명사구 메소드 이름 : 동사/동사구 한 개념에 한 단어(동의어를 사용하지 말 것) 2. 함수는 작게 작성하자 최대한 짧게 작성하자. indent는 1-2개 정도로 두자. 함수 이름을 서술어로 잘 설정해서 코드만 읽어도 이해되게 해 보자. 함수는 1가지 역할만 하자. (추상화 수준을 1개로 만들자는 것) 함수 인수는 최대한 적게 두자. 3. 주석은 최대한 없애자 주석이 필요없을 정도로 깔끔한 코드를 짜면 된다. 필요하다면, 의도와 의미를 명확하게 설명하자. 필요한 주석은, ..
22.06.23. 풀었던 문제들
acmicpc String 파트 풀었음. 조만간이다..! 다따라잡자! 11654 아스키 코드 11720 숫자의 합 10809 알파벳 찾기 2675 Repeating Characters 1157 단어 공부 1152 단어의 개수 2908 FILIP 5622 BAKA 2941 LJESNJAK 1316 그룹 단어 체커
21.07.11. 이번 주 공부계획
팀원들과 프로젝트 이야기 - 프로토타입 다듬기(추가기능 등) - 마일스톤 작성하기(상세기능 및 전체 계획 등) - API 명세 - DB Schema 작성 Jenkins 공부 (~15일) - Gitlab hooker와 jenkins 연동해서 push 시 build하는 것은 진행했음. - unit test - docker image 등록하는 것까지 jenkins로 해 보자. MSA 공부 (~11일) - Java 기반 마이크로 서비스 이해와 아키텍처 구축하기 책 완독 및 정리하기 Spring 공부 - 강의 듣기
21.06.28. 짧은 공부계획
06/28, 06/29 - Spring Boot MVC model 게시판 예제 구현 https://aridom.tistory.com/61 victorydntmd.tistory.com https://kyuhyuk.kr/article/spring-boot/2020/07/19/Spring-Boot-JPA-MySQL-Board-Write-Post https://congsong.tistory.com/15?category=749196 congsong.tistory.com 그러면 다음주까지 계획은 대충... 일요일 월요일 화요일 수요일 목요일 금요일 토요일 28 29 30 1 2 3 springboot mvc 게시판 구현 오전 정처기 실기계획 springboot mvc 로드맵 오후 springboot mv..
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)) 최대 거리는 ..