전체 글
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(하..
SWM 이후 정리/계획
SWM 이후로 지금까지 뭘 했지? 생각해 보면 - 비즈니스적 역량 조금 기른 듯. - Spring - MVC 형태로 Security를 이용한 로그인, 이제 만들고 싶은 것은 만들 수 있을 듯. - DevOps - 기본은 하는 것 같다. 이거 밖에 없넹,,, 좀 적은 감이 없잖아 있다. 본격적으로 뭔가 시작한 게 7월인 것 생각하면, 3개월동안 이것만 한 것 치곤 너무 적은 것 같다. 좀 더 열심히 살아야겠다. 항상 이랬다. 지나고 나서 좀 더 열심히 할 걸 후회했었다. 이제는 진짜 조금 달라져야한다. 떵떵거리면서 살기에는 우리나라는 너무 각박한 것 같으니까. 후회할 미래를 현재에 바꾼다는 생각으로, 죽기 아니라면 까무러치기라는 마인드로, 하지 않으면 도태된다는 전제를 깔고 다시 달려야겠다. 작년 이맘때쯤..
그래프 알고리즘 - (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..