전체보기
22.08.16. 풀었던 문제들
백준 단계별 26 Shortest Path 1753 최단경로 - dijkstra 문제 1504 특정한 최단 경로 - dijkstra 조금 응용 문제 11404 플로이드 - floyd-warshall 문제 11657 타임머신 - bellman-ford 문제 1956 운동 - floyd-warshall 문제 13549 숨바꼭질 3 - dijkstra 문제. max를 어리도 잡냐가 중요한 문제였다. 9370 미확인 도착지 - 1504와 비슷한 문제. 다만 처음에 문제를 잘못 이해해서 'route가 최소값인 target들'을 고르는 건줄 알았는데, 그게 아니라 's에서 target까지 shortest path weight == s -> g -> h(또는 h -> g) - target)의 weight가 같은 ta..
[N2T] 네이버 에디터와 티스토리 에디터 분석
1. 네이버 에디터 html을 뜯어 보면 아래와 같다. 제일 상위에 se-main-container가 있고, 그 아래에 각각 글, 코드, 이미지 단락들이 존재한다. 좀 더 상세하게 뜯어본 결과, 네이버 블로그 본문의 구조는 아래와 같다. se-main-conatiner ┗ se-component se-text ... (글인 경우) ┗ se-component se-code {코드블럭 종류} (코드인 경우) ┗ se-component se-image ... (이미지인 경우) ┗ se-component se-quotation ... (인용구인 경우) ┗ se-component se-horizontalLine {구분선 종류} (구분선인 경우) ┗ se-component se-table (표인 경우) 네이버 블로..
[N2T] N2T - 네이버 블로그 이사 프로그램
N2T, Naver2Tistory란? 한 줄로 설명하자면 네이버 -> 티스토리 블로그 이사 프로그램입니다. 좀 더 자세하게 설명하자면, 네이버 블로그 링크를 올리면, 해당 포스팅의 내용을 티스토리 에디터에 맞게 형식을 고쳐 업로드 해 주는 프로그램입니다. 필요성 네이버에서 티스토리로 글을 옮길 때, 본문을 Ctrl+C - Ctrl+V를 하게 되면 복사한 글과 티스토리 에디터에 있는 양식에 맞지 않아 글 내용 수정에 애로사항이 생깁니다. 대표적으로 문단 제목 양식, 소스 코드 블럭, 사진과 캡션이 문제가 되고, Table Of Content도 제대로 출력되지 않습니다. 네이버 블로그 글을 티스토리로 복사해 왔을 때 문제점 재현 기능 v1.0.0 네이버 블로그 HTML 및 이미지 저장 티스토리 블로그에 공개..
22.08.15. 풀었던 문제들 *** vector erase, remove
프로그래머스 코딩테스트 실전 대비 모의고사 3회 1번 주어진 대로 반복문을 써서 풀면 되는 문제. int solution(int give, int take, int cur) { int answer = 0; while(cur >= give){ // 현재 가지고 있는 게 주는 것보다 많으면 줄 수 이씅ㅁ int ret = (cur / give) * take; // 돌려받는 것 answer += ret; cur = cur - ((cur / give) * give) + ret; // 현재 개수 = 현재 개수 - 준 것 + 돌려받은 것 } return answer; } 2번 뒤에서 4개가 주어진 조건을 만족한다면, 그것을 빼고 추가하면 되는 문제. list를 쓸까 vector를 쓸까 고민하다가 결국 더 빠른 ve..
22.08.14. 풀었던 문제들
프로그래머스 코딩테스트 실전 대비 모의고사 2회 1번 3중포문으로 간단하게 풀면 되는 문제 int solution(vector number) { int answer = 0; int n = number.size(); for(int i = 0; i
22.08.13. 풀었던 문제들
Codeforces #805 Div. 3 Upsolving G번 빼고 했다.(아직 배우지 않은 lca) 프로그래머스 코딩테스트 실전 대비 모의고사 1회 1번 두 수에서 각 숫자의 개수를 xcnt, ycnt에 기록한 후 xcnt[i], ycnt[i] 중 작은 값 만큼 정답에 붙여넣으면 된다. 0은 special case기 때문에 따로 예외처리 해 주면 된다. #include #include using namespace std; string solution(string X, string Y) { vector xcnt(10, 0), ycnt(10, 0); for(char c : X){ xcnt[c-'0']++; } for(char c : Y){ ycnt[c-'0']++; } string answer = "";..
22.08.12. 풀었던 문제들 - Codeforces #805 Div. 3 4/7
백준 단계별 25 그래프와 순회 7562 Knight Moves 1697 Catch That Cow 2178 미로 탐색 1012 유기농 배추 2667 단지번호붙이기 1260 DFS와 BFS Codeforces #805 Div. 3 https://codeforces.com/contest/1702 Dashboard - Codeforces Round #805 (Div. 3) - Codeforces codeforces.com 결과 언제쯤 4/7의 벽을 통과할까. A번 주어진 수보다 작은 10^k 중 k의 최댓값을 찾으면 되는 문제다. void solve(){ int m; cin>>m; int value = 1000000000; vector rounds; while(value >= 1){ rounds.push_b..
22.08.11. 풀었던 문제들
백준 단계별 25 그래프와 순회 2606 바이러스 24445 알고리즘 수업 - 너비 우선 탐색 2 24444 알고리즘 수업 - 너비 우선 탐색 1 24480 알고리즘 수업 - 깊이 우선 탐색 2
22.08.12. 취준 큰그림 (갑자기 의욕이 솟아나는 기분!)
전역 전까지, 일단 PS는 PS대로 하고, 해커톤은 해커톤대로 하고, 강의는 강의대로 듣고, 개인 플젝은 개인 플젝대로 할 것 같다! (아마 티스토리 글 자동 정렬기능, 네이버 포스트에서 글 불러오는 기능 정도를 플러그인 구현하지 싶다. 그리고 BE 서버 만족할 만한 수준으로 하나 정도?) 그리고 시간 날 때마다 기술 포스트 정리(남들이 알아볼 수 있을 만 한 수준으로 풀어서) + 조금 deep하게 조사 전역 전까지 CS(네트워크, OS, 알고리즘, DB) 관련 면접대비용 개념 포스팅 github 관리 (지금까지 했던 코드들 정리-정렬, 리팩토링, 주석 정리 등-, readme 꾸미기) 우선순위 1순위 대학 강의 - 끝! 2순위 PS 3순위 포폴 준비(해커톤, 개인 플젝) - 끝! 4순위 github 코..
[Figma] 소프트웨어 마에스트로 프로젝트 프로토타입 초안
소프트웨어 마에스트로 프로젝트로 진행한, 비즈킥스 프로토타입 초안이다. 디자이너를 한 분 모셔왔고, 대충 플로우를 보여주기 위해 에브리타임과 인터파크 UI와 유사하게 만들었다. 영상은 아래와 같다. 이 플로우를 참고해서 발전시켜 나갈 것 같다!
[Figma] Prototype Tool, Figma
0. 참고자료 UI를 제작하기 위해 Figma의 정말정말 간단한 기능들만 배워보려 한다. 아래 강의들이 이해하기 쉬웠다. https://www.youtube.com/watch?v=GsZk8s5JdWg&t=1s https://www.youtube.com/watch?v=6e46VxYgcpI https://www.youtube.com/watch?v=6mbl6hdbivI https://www.youtube.com/watch?v=t5G87A3t2CM https://www.youtube.com/watch?v=ccR7cIOh6no Youtube 연정's Figma 님의 강의를 정리한 것이다. 잘 가르쳐 주셔서 따라가기 쉬웠다. 1. Figma에서 사용하는 기초 개념들 Frame Figma의 모든 component(객..
22.08.10. 풀었던 문제들
백준 단계별 24 DP 2 2293 동전 1 dp[k] : k원 만드는 경우의 수라고 생각하면, 점화식은 dp[i] = dp[i] + dp[i - coin[j]]이 된다. 7579 앱 냅색 응용. 문제에서 주어진 대로라면 dp[i][j] = i번째 앱까지 봤을 때 memory j까지 사용했을 때 cost의 최솟값 이런 식으로 정의했겠지만, memory의 입력이 1천만, 앱의 종류가 100개기 때문에 두 개를 곱하면 1억이 넘어간다. 다른 방식으로 풀어야 한다. dp[i][j] = i번째 앱까지 봤을 때, cost j까지 사용했을 때 memory의 최댓값으로 생각하면 냅색과 같은 문제가 되고, "c - cost[a] >= 0 then dp[a-1][c-cost[a]] + memory[a]"의 점화식을 가지..
22.08.09. 풀었던 문제들
백준 단계별 24 DP 2 1520 내리막길 bottom-up dp로는 풀면 안 되는 게, 순서대로 채워나가면 역순으로 오는 예외가 있다. 따라서 무조건 top-down dp로 풀어야 한다. 사실상 DFS인데 이전에 구한 값을 memoization해서 사용해야 하는, DFS + DP이다. DFS 하는 것처럼 도착점에 다다르면 +1, 그렇지 않다면 다다르는 경우에 대해서만 그 경우의 수를 더해주었다. int dr[4] = {1, 0, -1, 0}; int dc[4] = {0, 1, 0, -1}; int board[501][501], dp[501][501]; int M, N; int search(int r, int c){ if(r == M-1 && c == N-1) return 1; if(dp[r][c] !..
22.08.08. 풀었던 문제들
백준 단계별 24 DP 2 오랜만에 보니까 정신이 혼미하군. DP 1은 대부분 1차원 array에서 해결할 수 있는 문제(+한 방향으로만 진행하면서 규칙을 찾으면 되는)였다면 DP 2는 대부분 2차원 array에서 해결할 수 있는 문제 같다. dp[i][j] = min{dp[i][m] + dp[m+1][j]}라던가, ... 11066 파일 합치기 dp[i][j] : index i부터 index j까지 합치는 데 필요한 cost 두 파일을 합칠 때 필요한 cost = 두 파일 크기의 합이다. 그러면 dp[i][i] = 0 dp[i][i+1] = files[i] + files[i+1]로 초기화 할 수 있고, 다음으로는 dp[i][i+2] = min{dp[i][i] + dp[i+1][i+2], dp[i][i+..
22.08.07. 풀었던 문제들
Codeforces #811 Div. 3 Upsolving D번 풀었고 G번 풀었음 F번은 내 수준으로 안 될 문제 같다. 오늘 안에 이거 끝내고 내일부턴 백준 다시 해야징~ 낮에는 업무한다고 바쁠거니까~으으윽
22.08.05. 풀었던 문제들 - Codeforces #811 Div. 3 4/7
Codeforces #811 Div. 3 https://codeforces.com/contest/1714 Dashboard - Codeforces Round #811 (Div. 3) - Codeforces codeforces.com 결과 많이 멀었군. A, B, C, E번은 시간 내에 풀고 제출했다. 7문제 중 4문제를 맞췄다. A번 주어진 시간인 H, M에 대해 입력 시간이 더 느리다면 그대로 두고, 더 빠르다면 24*60을 더한 후 [입력 시간 - 주어진 시간]의 최솟값을 구하는 손풀기 문제 int timeToInt(int H, int M){ return 60 * H + M; } pii intToTime(int t){ return {(t/60)%24, t%60}; } void solve(){ int ..
22.08.04. 풀었던 문제들
LIS 5 문제에 LIS 정리를 해 뒀고 pq 정렬 기준에 대한 정리도 해야 함(pq 첫 문제에 정리 해 둠) 22 binary search 12015 LIS 2 12738 LIS 3 14002 LIS 4 14003 LIS 5 23 priority queue 11279 최대 힙 1927 최소 힙 11286 절댓값 힙 1655 가운데를 말해요 상당히 재밌는 문제였다. pq 2개를 써서 가운데 값을 표현할 수 있다. [max heap] - middle value - [min heap]으로. 그러나 수가 짝수 개, 홀수 개일 때 middle value를 수정하는 것이 번거롭기 때문에 수가 짝수일 때는 max heap과 min heap의 크기를 동일하게 유지해서 max heap의 top을 middle value..
22.08.03. 풀었던 문제들
오랜만이다! 코로나19 (아마도) 확진 + 휴가로 인해 거의 2주 쉰 것 같다. 너무 오래 쉬니까 이렇게까지 오래 쉬어도 되나..?라는 생각밖에 들지 않는다. 전역 후에는 바로 취업할 수 있게(겨울학기에는 SES와 같은 겨울 인턴을 하지 싶다) 파이팅 하고, 학점도 열심히 들어서 포상휴가를 노려보자. 백준 단계별 22 이분 탐색 1920 수 찾기 10816 숫자 카드 2 1654 랜선 자르기 2805 EKO lower bound로 푸는 것보단 upper bound로 상한을 구한 후 거기서 -1을 하면 답이 된다. 2110 공유기 설치 '최대 설치 거리'를 binary search로 찾아가면 된다. '최대 설치 거리'를 기준으로 C개 설치 가불 여부를 따지면 O(n), 이걸 log n번 할 것이니 O(nl..
[GCP Tutorial] Window Gaming Server + Graphics Card using RDP (feat. GCP)
언제 어디서나 피시방처럼 게임을 하고 싶을 때, GCP의 무료 크레딧을 이용해 무료 원격 피시방을 즐겨보자. 1. 그래픽카드 사용 신청 먼저 그래픽카드 quota를 올려야 한다. IAM > 할당량 > 필터에 all_regions 검색 - all regions GPU클릭 - 할당량 증가 클릭해서 GPU 한도 0에서 1로 늘려달라고 요청하고, 메일로 한도 변경 되었다고 연락 올때까지 기다린다. 메일이 오면 해당 페이지에서 Nvidia T4 GPUs로 필터링한다. 그래픽카드 위치는 asia-northeast3-b나 asia-northeast3-c로 해야 한다. 2. Instance 생성 일단은 gcp에서 NVIDIA Gaming PC - Windows Server 2019를 찾는다. 실행 누른다. 높은 핑을 ..
22.07.14. 풀었던 문제들
백준 단계별 21 분할 정복 11401 이항계수 3 - 페르마의 소정리 쉣... 페르마 그는 신인가? 풀이는 아래와 같다. 이항계수 $_{n}C_{k} = \tfrac{n!}{(n-K)! \cdot k!} = \tfrac{n \cdot (n-1)\cdots (n-k+1)}{k \cdot (k-1) \cdots 1}$이다. 편의를 위해 $A = n \cdot (n-1) \cdots (n-k+1), B = k \cdot (k-1) \cdots 1$라고 두자. 한편, 페르마의 소정리에 의해 나누는 값 1,000,000,007(p라고 두자)은 소수이므로 $a^{p-1} \equiv 1 \% p$이다. 그러면 이항계수를 $\tfrac{A}{B} \% p = (AB^{-1}) \% p = (AB^{-1} \time..
22.07.13. 풀었던 문제들
백준 단계별 21 분할 정복 2630 색종이 만들기 1992 쿼드트리 1780 종이의 개수 1629 곱셈 2740 행렬 곱셈 10830 행렬 제곱 11444 피보나치 수 6 행렬의 고속 거듭제곱, 이를 이용한 피보나치 수 O(logn)에 구하기 정리.
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..