PS/PS Log
22.04.06. 풀었던 문제들
프로그래머스 lv 2 1. 멀쩡한 사각형 #include #include #include using namespace std; typedef long long ll; typedef long double ld; long long solution(int w,int h) { if(w < h) swap(w, h); // w가 더 크게. ll answer = (ll)w * h; for(ll i = 1; i
22.04.05. 풀었던 문제들
1. n^2 배열 자르기 규칙 찾기 문제였다. n = 3이 주어졌다고 하자. 그러면 arr는 아래 그림과 같다. 1 2 3 2 2 3 3 3 3 idx에 따른 값은 아래와 같다. (0,0) : 1 (1,0), (1,1), (0,1) : 2 (2, 0), (2, 1), (2,2), (1,2), (0,2) : 3 보이는가? arr[i][j] = max(i, j) + 1이다. 또, n이 주어졌을 때, 특정 idx가 주어지면 배열의 그것으로 바꿀 수 있겠는가? -> Yes. n/4, n%4로 바꿀 수 있다. 2. 방문 길이 중복되는 경우는 세지 않으니, map이나 set으로 풀면 되는 문제다. 그리고 팁. 이 문제와 같이 좌표평면에서 상하좌우로 이동하는 경우, if나 case를 써서 나누지 말고 ..
22.04.04 풀었던 문제들
1. 쿼드 압축 후 개수 세기 backtrack을 이용해, 압축 가능하다면 탐색하지 않고, 압축 불가능하면 탐색하는 방식으로 진행하면 된다. 2중포문 안쓸려다가 시간 엄청나게 잡아먹은 문제. 생각해 보면, 모든 arr을 log(input size)만큼 탐색하는 것이므로 시간복잡도는 n^2logn이다. 입력이 1024까지니 이런 풀이가 가능함. // 쿼드압축 후 개수 세기 #include #include using namespace std; void div(vector& arr, vector& answer, int r, int c, int size){ if(size == 1){ answer[arr[r][c]]++; return; } int base = arr[r][c]; bool compressable =..
22.04.02. 풀었던 문제들
1. 소수 찾기 어떤 숫자의 list(0, 1, 2, 3, ...)이 주어졌을 때 size가 1인 순열 size가 2인 순열 ... size가 list.size()인 순열 을 모두 구하고, 소수인지 판정하면 되었다. 2. 조이스틱 greedy라고 나와 있지만.. 이 문제가 진짜 greedy인지 나는 모르겠다. 그래서 brute-force로 풀었다. 어떤 문자열이 있으면, 그 문자열의 제일 앞에 있는 문자를 제일 뒤로 보낸다. 이렇게 만들어진 문자열(temp)의 index 0으로 이동해야 하는 거리를 구하고, 그 temp 문자열에서 왼쪽으로 쭉 갈 때, 오른쪽으로 쭉 갈 때 좌/우 이동의 최솟값을 구한다(A가 아닌 idx를 찾으면 된다). 이 두 값의 합이 기존 문자열에서 이동해야 하는 좌우 이동 ..
22.04.01. 풀었던 문제들
1. 전화번호 목록 hash로도 풀 수 있고, sort 한 후 string 특성으로도 풀 수 있다. hash로 푸는 경우, unordered_map에 모든 phone number를 넣어두고, 모든 phone number의 자기 자신을 제외한 substring(해당 phone number 제외. 즉 01234라면 0, 01, 012, 0123만 본다는 것)에 대해 unordered_map에 있는지 검사한다. 있다면 접두어가 있는 것이므로 false, 아니면 true. sort로 푸는 경우, string을 사전식으로 정렬한 후, phone_book[i-1]가 phone_book[i]의 substring이라면, 즉 phone_book[i].substr(0, phone_book[i-1].length()) =..
22.03.31. 풀었던 문제들
1. 큰 수 만들기 greedy 문제다. 앞에서부터 str[i] < str[i+1]인 경우 str[i]를 지우는 방식으로 반복한다. string의 모든 substr가 monotonic decreasing을 만족한다면 제일 작은 char부터 지워나가면 된다. 2. 기능개발 size가 작기 때문에 simple하게 queue로 돌려도 되고 (brute-force하게) 아니면 최적화해서 풀 수도 있는 문제였다. 이 경우에는 남은 일자를 계산하고, 예를 들어 3 1 1 4 2 1 5 이라면 3 1 1을 하나로 묶어 배포하고 4 2 1을 하나로 묶고, 5를 묶어 배포해야 된다. 규칙은, 남은 일자가 오름차순이라면 따로 배포해야 한다는 것이다.( 남은 일자가 단조 내림차순인 것들을 찾아 묶으면 된다) // 기..
22.03.30. 풀었던 문제들
1. 구명보트 greedy / two-pointer느낌도 난다. vector를 정렬해서 max값 + min값이 limit보다 크면 둘다 보트에 태우고, 그렇지 않다면 max값만 보트에 태우면 된다. 2. 삼각 달팽이 규칙 찾기 + 구현 문제다. 3. 주식가격 pq를 잘 이용해 보는 문제였다. -> 같은 방법으로 stack으로도 풀린다... prices를 앞에서부터 하나씩 pq에 넣는다. (pq의 top은 넣은 값 중 최댓값이 올라오게 한다) prices[i] 이에 따른 처리를 해 주면 된다. prices[i] >= pq.top()이 될 때 까지 pq.pop()을 해 주고, pq.top()에 있는 것의 index와 prices[i]와의 in..
22.03.29. 풀었던 문제들
* stringstream, istringstream 정리하기 * dp * 빠른 피보나치 구하기(고속행렬곱) programmers lv. 2 1. 피보나치 수 기본적으로는 db로 풀면 된다. 시간복잡도가 올라가면, 고속 행렬 곱으로 풀면 된다. 2. 최솟값 만들기 규칙 찾기 문제다. 3. 최댓값과 최솟값 string parsing 문제이다. 그냥 for문 돌려서 풀 수도 있지만.. 아무래도 stringsteam을 공부하긴 해야 겠다. istringstream도 한번 봐 보자. 4. 다음 큰 숫자 2진수에서 1의 개수를 세는 방법이다. 이것도 정리해 보자. 5. 땅따먹기 되게 유명한 DP 문제다. land[i]를 보고 있을 때, land[i+1]에서 최댓값을 뽑기 위해서..
22.03.28. 풀었던 문제들
유클리드 호제법 시간복잡도 증명 programmers lv.2 1. N개의 최소공배수 gcd / lcm 문제였다. 2. JadenCase 문자열 만들기 기초 문자열 다루기 문제였다. toupper, tolower 함수를 쓰면 된다. *기억하자! toupper, tolower 함수는 cctype header에 있다. 3. 행렬의 곱셈 슈트라센 알고리즘까지는 아니어도, cache를 이용한 행렬곱까지는 기억해 두자. http://www.secmem.org/blog/2021/03/20/strassen-algorithm/ 지금까지 풀었던 문제 따라잡으려면 30문제쯤 남았는데... 그때그때 생기는 정리해야 하는 알고리즘 정리하면서 풀면 끝이 없을 것 같다. 그래서 정리해야 하는 알고리즘은 포스..
22.03.27. 풀었던 문제들 *** 정규표현식 정리하기
1. 크레인 인형뽑기 게임 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 2. 키패드 누르기 간단한 구현 문제였다. 3. 숫자 문자열과 영단어 string 문제였다. 침착하게 잘 풀어보자. 특히 string parsing을 할 때 index가 잘 저장되는지 기억하자. 그리고 정규표현식으로 이 문제를 쉽게 풀 수 있다. 정규표현식도 정리해 보자. 4...
22.03.26. 풀었던 문제들
1. 나머지가 1이 되는 수 찾기 기초 반복문 문제였다. 2. 두 개 뽑아서 더하기 중복을 허락하지 않고, 정렬되어 있는 set 자료구조의 특징을 이용하면 쉽게 풀 수 있다. 3. 3진법 뒤집기 string 기본 문제였다. 4. 내적 loop 기본 문제였다. 5. 약수의 개수와 덧셈 simple for문이 아니라 조금 더 시간복잡도를 줄여보자. 6. 음양 더하기 기본 loop문이었다. 7. 없는 숫자 더하기 set으로 풀었지만... 그냥 총 합에서 빼는 방법도 있다. 8. 폰켓못 set으로 풀었다. set에 vector들의 원소를 넣고 싶을 때는 for문을 사용해서 하나하나 삽입해 주어도 되지만 초기화 하는 방법이 있으니 이를 참고하자. 9. 소수..
22.03.25. 풀었던 문제들
1. 약수의 합 brute-force 기초 문제였다. 2. 소수 찾기 에라토스테네스의 체를 이용해야 한다. 소수 판정법 등에 대해서는 나중에 포스팅 해 보자. 3. 최소공배수와 최대공약수 유클리드 호제법 - gcd, lcm 알고리즘에 대해 정리해 보자. 시간복잡도는 log(min(a, b))이다. 4. 최소직사각형 간단한 greedy 문제였다. 5. 부족한 금액 계산하기 언제나 문제 조건에 따른 자료형의 길이를 잘 생각해 두자. 6. 2016년 for문의 시작 idx를 잘 보자.
22.03.24. 풀었던 문제들
programmers lv.1 1. 정수 내림차순으로 배치하기 c++의 algorithm header에 있는 sort 함수의 마지막 열(정렬 하는 방식)에 greater(), less()를 숙지해 두자. * string도 정렬이 된다. 알아두자. 이 경우, to_string()함수와 stol함수(자료형 변환 함수)를 기억해 두자. 2. 자연수 뒤집어 배열로 만들기 자릿수만 잘 계산해 두면 된다. 자릿수 계산은 알겠지만, 외워두자. while(n != 0){ n % 10; n /= 10; } 3. 자릿수 더하기 자릿수 구하기만 하면 된다. 기초문제. 4. 이상한 문자 만들기 string의 split은 외우자. #include vector split(string input..
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 전부 백준 냅색 작년 소마 기출. 모의테스트.