PS
22.03.23. 풀었던 문제들
프로그래머스 lv.1 1. 모의고사 기초 문제였다. 다만 여전히 구현력이 부족한 것 같다. 이런 문제를 많이 풀어보자. map 사용법을 숙지하자. 2. 완주하지 못한 선수 기초 문제. 정렬만 하면 되었다. 3. x만큼 간격이 있는 n개의 숫자 반복문 기초 문제였다. 4. 행렬의 덧셈 반복문 기초 문제였다. 5. 하샤드 수 while문 기초 문제였다. 6. 홀수와 짝수 기초 문제다. 다만 %2 하는 것처럼 쉽게 생각하지 말고, &1처럼 비트 연산을 하는 방법도 있다 ! 7. 핸드폰 번호 가리기 기초 문제다. 8. 평균 구하기 기초 문제다. range iteration을 써봤다. accumulate로 배열의 합을 쉽게 구할 수 있..
22.03.22. 풀었던 문제들
프로그래머스 lv.1 1. 직사각형 별찍기 기초문제 2. 체육복 이상한 데서 막혔던 문제. 2개 있는 사람이 나눠주는 걸 기준으로 생각하면 -> 방향에 따라 최적해가 나올 수도, 아닐 수도 있다. ->(03.23. 수정) 일반항을 기준으로 생각하면 그럴 수 있지만, 앞에서 바라보면 동일하다. 그래서 어려워 했는데 이렇게 생각하지 말고 0개 있는 사람이 빌린다고 생각하면 풀리는 것 같다. 탐색을 앞에서부터 진행할 거니까, 0인 사람이 앞사람에게 물어 봤을 때 0인 경우 -> 어차피 못빌려줌 -> 뒷사람에게 물어보면 된다. 1인 경우 -> 앞사람에게 줬을 수도 있다(이 경우에는 '앞 사람'이 앞으로 주나 뒤로 주나 최종값은 동일해진다) 처음부터 1개였을 수도 있고. 2인 경우 -> ..
21.06.24. 풀었던 문제들
programmers 위장 삼각 달팽이 2개 이하로 다른 비트 -> 비트 규칙 찾아서 풀음. docker 공부했음, react flutter spring mysql 이렇게 4개 폴더를 만들고 spring에서는 .jar 파일로 서버를 배포하는데 docker는 이 파일들을 모아서 image로 만들어 줌 이 image를 EC2에 넣음 그러니까 local src -> .jar files build -> image(docker) -> docker registery -> EC2 local source -> git docker volume을 이용한다면, local 파일 변경 -> .jar files rebuild -> docker 재실행 -> docker는 local을 참조하기 때문에 변경되지 ..
21.06.23. 풀었던 문제들
프로그래머스 2개 이하로 다른 비트 -> 규칙 비슷하게 찾은 것 같은데, 어떤 테케를 놓쳤는지 모르겠다. 시간제한에 걸렸음. 가장 큰수 -> 규칙찾아서 정렬해서 풀었음.
21.05.11. 풀었던 문제들
플라스크 API 구현 정도만 읽어보기 지금까지 알고리즘 공부를 안했는데, 연수생들 컨택하고 정처기 공부, 자취 등 이것저것 바빴다. 아마 본 프로젝트 딱 시작! 하면 그때부터 2-3문제씩 풀지 싶다.
21.03.27. 풀었던 문제들
코드잼 qualification round 30점 긁고 끝냄. 소마 면접 조진 것 같으니(떨어질 삘이다...) SES 붙기 위한 코딩테스트 공부나 좀 해야겠다..! 4/1부터 다시 시작.
21.03.13. 풀었던 문제들
오전 : 프로그래머스 SQL kit 프로그래머스 2단계 테스트(웜업) 지금까지 정리한 STL / 알고리즘 훑기 소마 12기 코딩테스트 2차
21.03.12. 풀었던 문제들
24. Shortest Path 1753 1504 9370 11657 1956 28. 유니온 파인드 union-find 1717 1976 4195 20040 29. 최소 신장 트리 mininum spanning tree 9372 1197 4386 프로그래머스 SQL kit 전부 하... 이제 주말까지 쉬고, 다음주부터는 조금조금씩 꾸준히 해야지... 뒤질거같애
21.03.11. 풀었던 문제들
23. DFS / BFS 1260 2606 2667 1012 2178 7576 7569 1697 2206 7562 1707 25. 투 포인터 two-pointer 3273 2470 1806 1644
21.03.10. 풀었던 문제들
22. 동적 계획법 2 Dynamic programming II 11066 11049 1520 10942 2629 2293 7579
21.03.08. 풀었던 문제들
14. 동적 계획법 I DP1 1003 9184 1904 9461 1149 1932 2579 1463 10844 2156 11053 11054 2565 9251 1912 12865 16. 정수론, 조합론 number theory, combinatorics 5086 1037 2609 1934 2981 3036 11050 11051 1010 9375 1676 2004
21.03.06. 풀었던 문제들
17. 스택 stack 10828 10773 9012 4949 1874 17298 18. 큐, 덱 queue&deque 18258 2164 11866 1966 10866 1021 5430 21. 우선순위 큐 priority queue 11279 1927 11286 1655
21.03.04. 풀었던 문제들
오늘부터 백준 단계별 적어도 3개씩 푸는 게 목표다. 9. 기본 수학 2 basic math 1978 2581 11653 1929 4948 9020 - 나중에 풀어보기 1085 3009 4153 3053 1002 10. 재귀 recursion 10872 10870 2447 11729 11. 브루트 포스 brute-force 2798 2231 7568 1018 1436 문제 딱 보면 브루트 포스로 풀어야 할 수 있을지 알 수 있을까?
21.03.03. 풀었던 문제들
오늘부터 백준 단계별 적어도 3개씩 푸는 게 목표다. 9. 기본 수학 2 basic math 1978 2581 11653 1929 4948 9020 - 나중에 풀어보기 1085 3009 4153 3053 1002 10. 재귀 recursion 10872 10870 2447 11729 11. 브루트 포스 brute-force 2798 2231 7568 1018 1436 문제 딱 보면 브루트 포스로 풀어야 할 수 있을지 알 수 있을까?
21.02.26. 풀었던 문제들
프로그래머스 동적 프로그래밍 DP lv3 N으로 표현 -> 이건 대체 어떻게 해야할지... lv4 도둑질 깊이/너비 우선 탐색 D/BFS lv2 타겟 넘버 lv3 네트워크 -> 나중에 union-find로 풀어보기 lv3 단어 변환 lv3 여행경로 SQL 고득점 KIT 전부 백준 냅색 작년 소마 기출. 모의테스트.
21.02.25. 풀었던 문제들
lv3 섬 연결하기 lv3 단속카메라 -> 다시 풀어보기 그리디 너무싷어ㅓㅓㅓㅓㅓ 동적 계획법 DP lv3 정수 삼각형 lv3 등굣길 내일은 프로그래머스 DP, B/DFS 다 풀고 SQL 키트 다 풀고 백준 냅색, 기출 풀면 될듯. lv3 N으로 표현 lv4 도둑질
21.02.23. 풀었던 문제들
백준 단계별 - 백트래킹 backtracking 15649 : N과 M (1) 15650 : N과 M (2) 15651 : N과 M (3) 15652 : N과 M (4) 9663 : N-Queen 프로그래머스 완전탐색 brute-force lv2 소수 찾기 -> 다시 풀것. int에서 string[i]로 바꿀때는 +'0' 하고, char에서 int로 바꿀 땐 -'0'해주는 걸 자꾸 잊음. 탐욕법 greedy lv1 체육복 lv2 조이스틱
21.02.22. 풀었던 문제들
heap lv2 - 더 맵게 lv3 - 디스크 컨트롤러 lv3 - 이중순위 큐 -> 다시 풀어보기 나중에! 소요시간 3시간 더 맵게, 디스크 컨트롤러 1시간 걸렸는데 이중순위 큐에서 시간이 너무 오래 걸림. sort K번째수 H-index -> 다시 풀어보기. 식이 도통 이해가안됨 ㅋㅋ 소요시간 1시간 brute-force 모의고사 카펫 소요시간 30분 소수 찾기는 아무리 생각해도 순열 문제고 backtracking은 아직 안익숙해서 걍 내비뒀다. 내일 풀어야징 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
21.02.21. 풀었던 문제들
프로그래머스 고득점 kit hash lv1 - 완주하지 못한 선수 lv2 - 전화번호 목록 lv2 - 위장 lv3 - 베스트앨범 stack/queue lv2 - 다리를 지나는 트럭 lv2 - 주식가격 lv2 - 기능개발 lv2- 프린터 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 총 소요시간 약 5시간. 프로그래머스 백준 단계별 leetcode weekly/biweekly - 아직 수준이 한참 먼 것 같다. DP, D/BFS를 자연스레 구사할 수 있게 되면 그 때 보는 게 맞지 싶다. 코드포스 div3 - 마찬가지, 백준/프로그래머스 공부 끝나면 그때 시작할 계획. 이 4개 위주로 보고 있는데 일단 - 프로그래머스 고득점 kit(하..
그래프 알고리즘 - (7) BST의 간단한 구현과 Tree traversal
이 글은 포스텍 오은진 교수님의 알고리즘(CSED331) 강의를 기반으로 재구성한 것입니다. 1. Tree 앞선 글에서 설명했듯 Tree는 directed acyclic graph이다. 그 중 대표적인 binary search tree의 몇몇 method의 구현과, 그 순회를 살펴볼 것이다. struct node{ node *left, *right, *parent; int x; }; // root node 초기화 node* initRoot(){ node *root = new node; root->parent=root; root->left = root->right = NULL; root->num=rootnum; } void insertNode(node *root, int value){ node *paren..
그래프 알고리즘 - (6) 위상 정렬 Topological sort
이 글은 포스텍 오은진 교수님의 알고리즘(CSED331) 강의를 기반으로 재구성한 것입니다. 1. DAG란? Definition DAG는 directed acyclic graph이다. cycle이 없는 directed graph라는 말이다. Property DAG는 적어도 하나의 sink와 하나의 source가 있다. sink는 나가는 edge가 없는 vertex, source는 들어오는 edge가 없는 vertex이다. cycle이 없다 -> source가 있다, 이며 source가 없다 -> cycle이 있다, 라는 말이 된다. 2. 위상정렬 Topological Sort Definition 모든 directed edge (u, v)에 대해 u가 항상 v보다 더 빨리 오게 vertex를 정렬하는 방식..
그래프 알고리즘 - (5) Minimum Spanning Tree(Kruskal, Prim)
이 글은 포스텍 오은진 교수님의 알고리즘(CSED331) 강의를 기반으로 재구성한 것입니다. 1. Minimum Spanning Tree 정의 MST는 모든 vertex를 포함하면서 weight를 최소화한 tree이다. 이는 greedy하게 구할 수 있으며, Kruskal과 Prim 2가지 방법으로 구할 수 있다. 2. Kruskal Algorithm Cut Property MST T에 속해있는 edge들의 부분집합 X에 대해, X가 속해있는 영역 S와 나머지 영역 V\S로 나눈다. e가 S와 V\S를 weight가 가장 작은 edge라고 하자. 그러면 X ∪ {e}는 MST의 부분집합이 된다. proof) e가 MST T의 일부라면 X ∪ {e}는 T의 subset인 것은 자명하다. 그렇지 않고 T가 ..
그래프 알고리즘 - (4) Union-find(disjoint set)
이 글은 포스텍 오은진 교수님의 알고리즘(CSED331) 강의를 기반으로 재구성한 것입니다. 1. Disjoint Set과 Union-Find Disjoint Set disjoint set은 서로 중복되지 않은 부분 집합들로 이루어진 자료구조, "서로소 집합"이라고 이해하면 될 것 같다. Union-Find union-find는 disjoint set의 표현 및 연산에 사용하는 알고리즘이다. 보통 Directed Tree를 이용해 구현하며, tree의 root는 해당 set의 대표값으로 생각하면 된다. 아래 예시에서는 {1, 2, 3, 4,}, {5, 6, 7, 8}, {9}가 각각의 set이며, 첫 번째 set의 대표값은 4, 두 번째 set의 대표값은 5, 세 번째 set의 대표값은 9이며 이 값들을..
그래프 알고리즘 - (3) Dijkstra, Bellman-Ford, Floyd-Warshall
이 글은 포스텍 오은진 교수님의 알고리즘(CSED331) 강의를 기반으로 재구성한 것입니다. 세 알고리즘 모두 '최단 거리'를 알아내는 알고리즘이다. 다만 어디서부터 어디까지 알아내는가가 다를 뿐이다. 1. dijkstra : O((|V| + |E|) * log|V|) 한 vertex에서 다른 모든 vertex까지의 최단거리를 알아내는 알고리즘이다. BFS와 유사한 알고리즘으로, BFS는 queue를 사용하지만 dijkstra는 priority queue(heap)을 사용한다. 다만 dijkstra는 weight가 음수인 경우에는 풀리지 않는다! procedure dijkstra(G, s) for all vertex u in V do dist(u) = INF prev(u) = null end for di..
그래프 알고리즘 - (2) 넓이 우선 탐색 & 깊이 우선 탐색 BFS & DFS
이 글은 포스텍 오은진 교수님의 알고리즘(CSED331) 강의를 기반으로 재구성한 것입니다. 1. DFS DFS는 어떤 vertex s로부터 reachable한 vertex를 뽑아내는 과정이다. 요점은 아래 2가지이다. - visited인 vertex는 다시 가지 않는다 - 현재 explore 중인 vertex와 연결된 vertex를 바로 탐색한다 pseudo code procedure DFS(G) for all vertex v in V do visited[v] = false end for for visited[v] == false do explore(v) end for procedure explore(w) visited[w] = true for each edge (w, u) in E do if visi..
그래프 알고리즘 - (1) Graph의 기본
이 글은 포스텍 오은진 교수님의 알고리즘(CSED331) 강의를 기반으로 재구성한 것입니다. 1. graph란? graph G = (V, E)로 이루어지는 자료 구조 중 하나이다. V는 vertex(node)의 set, E는 edge의 set이다. graph G를 (V, E)로 표현할 수 있다. 2. graph의 종류 Undirected Graph G = (V, E) 중 edge set E의 모든 edge는 node가 연결되었다는 것만을 의미하는 것이다. 방향은 신경쓰지 않는다는 의미이며, 따라서 vertex 1과 vertex 2를 잇는 edge를 (1, 2)로 표현하든 (2, 1)로 표현하든 같은 말이다. Directed Graph G = (V, E) 중 edge set E의 모든 edge가 어떤 no..
PS에서 Master Theorem
Master Theorem은 알고리즘의 동작 시간을 대략의 수행시간을 big O notation으로 계산하는 방법이다. 일반적으로 divide-and-conquer와 같은 recursion에서 자주 사용하며, 입력이 n개인 task를 문제를 입력이 n/b개인 a개의subtask로 나눴을 때, 그 subtask를 f(n)만에 해결할 수 있다면 아래 식과 같이 표현한다. $T(n) = aT(\frac{n}{b}) + f(n)$ (단, a >= 1, b > 1, p >= 0) Master Theorem은 T(n)에 관한 점화식을 푼다. 그러나 대부분의 PS에서 f(n)은 $\Theta(n^{k}log^{p}n)$으로 정의되니, 이 식에서 답을 도출해 볼 것이다. 1. if $log_{b}a < k (\Left..
이진탐색 Binary Search, Lower/Upper Bound, Parametric Search
이진 탐색 : O(logn) 개념 Binary search는 정렬된 array에서 어떤 값 k를 찾는 방법이다. 이 또한 divide and conquer를 사용하는 방식으로, 재귀방정식을 세우면 아래와 같다. $T\left(n\right)\ =\ T\left(\frac{n}{2}\right)\ +\ c$ 따라서 시간복잡도는 O(logn). 다른 방식으로, 처음 n개를 탐색할 때, 중앙값을 보고 탐색할 부분을 절반으로 나눈다. 다음 n/2개를 탐색할 때, 중앙값을 보고 탐색할 부분을 절반으로 나눈다. ... 마지막 것이 탐색된다. 즉, n개의 input이 있을 때 탐색은 logn번 진행한다. 반복문으로 탐색 : O(logn) int search(vector& v, int input){ int star..