티스토리

Change is the only constant

검색하기

블로그 홈

Change is the only constant

lecor.tistory.com/m

과연 그런가 왜 그런가

구독자: 5

방명록 방문하기

주요 글 목록

Greedy Algorithm 그리디 알고리즘 지금 이 순간 가장 좋은 것만 고르는 방법 힌트 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다. 그리디 알고리즘은 매 순간 최선을 선택한다라는 말 때문에 매우 쉽게 들리지만, 매 순간의 선택이 최선이 되도록 방법을 정하는 것 자체가 매우 어렵기 때문에 알고리즘중에 사람들이 가장 어려워 한다. 그리디 알고리즘의 정당성 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 함 즉, 그리디를 적용한 해가 최적해임을 증명할 수 있어야함 sample 문제들 📋 1 BOJ 5585: 거스름돈 더보기 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1.. 공감수 0 댓글수 0 2021. 8. 2.
프로그래머스 SQL kit 문제 정리 코딩테스트 연습 기초부터 차근차근, 직접 코드를 작성해 보세요. programmers.co.kr SQL 문 순서 SELECT --컬럼명 FROM --테이블명 WHERE --테이블 조건 GROUP BY --컬럼명 HAVING --그룹 조건 ORDER BY --컬럼명 SELECT 테이블의 모든 레코드를 ANIMAL_ID순으로 조회 SELECT * FROM ANIMAL_INS ORDER BY ANIMAL_ID; ORDER BY는 기본값이 오름차순(ASC) 테이블의 모든 동물의 이름과 보호 시작일을 조회. 이때 결과는 ANIMAL_ID 역순으로 보여주세요. SELECT NAME, DATETIME FROM ANIMAL_INS ORDER BY ANIMAL_ID DESC; 아픈 동물(INTAKE_CONDITION 이.. 공감수 0 댓글수 1 2021. 3. 15.
CheatSheet :: C++ <vector> container 활용법 container 장점 vector를 선언하면 heap 영역에 자동으로 할당되어 메모리 관리가 용이하다. 앞 뒤로 원소를 추가하고 삭제하는게 쉽다. 단점 vector도 배열처럼 메모리에 연속적으로 저장된다. 그런데 길이가 가변적으로 변하는 vector는, 공간이 없으면 전체적인 재할당이 이루어져야하기 때문에 데이터가 많아지면 속도가 느려질 수 있다. 선언과 초기화 #include vector v; // int타입 vector 생성 vector v(5); // 0으로 초기화된 5개의 원소를 가지는 vector 생성 vector v(5, 2); // 2로 초기화된 5개의 원소를 가지는 vector 생성 vector v = { 1, 2, 3 }; // int형 vector 생성 후 1, 2, 3 으로 초기화 .. 공감수 0 댓글수 0 2021. 3. 3.
[BOJ] DP 11053 가장 긴 증가하는 부분수열 C++ 11053번 가장 긴 증가하는 부분 수열 📝문제링크 : www.acmicpc.net/problem/11053 지금까지 풀었던 DP 중 제일 어려웠다. 정답코드를 보고도 접근 방법이 잘 연상되지 않았다. solved.ac 등급이 silver2 던데, silver1 문제보다 어려운 거 같은데...🤔 가장 긴 증가하는 부분 수열은 LIS 라고도 불리는데, 유명한 개념이니까 확실히 알고 넘어가는게 좋을 것 같다. 접근 과정 1. DP니까 당연하게도(?) memoization으로 접근해봐야지. $dp[i]$ : arr[i]이 배열의 마지막 원소일 때, 가능한 가장 긴 증가하는 부분 수열의 길이가 저장된다. dp[i] 에 저장될 값은, arr[i - 1] 까지의 가장 긴 증가하는 부분 수열에 arr[i] 값을 붙일.. 공감수 0 댓글수 0 2020. 12. 28.
[BOJ] DP 2156 포도주 시식 C++ 2156번 포도주 시식 📝문제링크 : www.acmicpc.net/problem/2156 $dp[i]$ 에는 i 번째 포도주가 마지막일 때, 마실 수 있는 최대 포도주의 양이 저장된다. 3개의 포도주를 연속으로 선택할 수 없다는 제약조건이 있으므로, 아래 그림과 같이 3개의 경우의 수를 생각해 볼 수 있다. ① x, y를 고르고 z는 선택하지 않는 경우 ② x, z를 고르고 y는 선택하지 않는 경우 ③ y, z를 고르고 x는 선택하지 않는 경우 이 세가지 경우의 수 중 max 값이 dp[i] 가 된다. 앞에서 풀었던 문제(9465 스티커)는 arr[i] 값을 선택한다는 걸 가정하고 경우의 수를 찾았는데, 이 문제는 arr[i]를 선택하지 않는 경우까지 고려해야한다는 점을 간과하기 쉬워 배울점이 있는 문제.. 공감수 0 댓글수 0 2020. 12. 27.
[BOJ] DP 9465번 스티커 C++ 9465번 스티커 📝문제링크 : www.acmicpc.net/problem/9465 2차원 배열이 주어져 처음 보는 새로운 유형이라고 생각했는데, 결국 다른 DP 문제와 크게 다르진 않았다. 문제는 내가 혼자 풀이방법을 떠올리지 못한다는 것 ㅠㅠ 처음접근 인접한 스티커를 선택할 수 없으므로, n = 1 일 때 부터 대각선 방향만 고려하며 쌓아나아가 봤다. 그러나 한 칸을 건너 뛰고 다음 칸에서 스티커를 선택하는게 더 유리한 케이스도 있어, 1부터 쌓아나가는 방법으로는 답을 찾을 수 없었다. 정답보고접근 2차원 배열 dp 를 선언한다. $dp[i][j]$ 엔 $i$행 $j$열의 스티커를 선택했을 때 얻을 수 있는 최대값이 저장된다. $[j - 2]$ 인덱스와 $[j - 1]$ 인덱스 값을 비교해 더 큰 값.. 공감수 0 댓글수 0 2020. 12. 24.
[BOJ] DP 11057번 오르막 수 C++ 11057번 오르막 수 📝문제링크 : www.acmicpc.net/problem/11057 이전에 풀었던 쉬운 계단수 문제와 아주 유사하다. 오르막수가 0으로 끝나려면 0의 앞자리엔 0만 올 수 있다. 오르막수가 1로 끝나려면 1의 앞자리엔 0과 1이 올 수 있다. 오르막수가 2로 끝나려면 1의 앞자리엔 0과 1과 2가 올 수 있다. . . . 오르막수의 끝자리가 L 인 경우 L의 앞자리엔 0부터 L까지의 수가 올 수 있다. i 는 2부터 N까지, j는 0부터 9까지, k는 0부터 j까지 3중 for문을 돌면 풀 수 있다. 소스코드 #include using namespace std; int main() { intN; cin >> N; // dp[N][L] : N자리 오르막수에 대해, 끝자리가 L인 수의.. 공감수 0 댓글수 0 2020. 12. 4.
[BOJ] DP 10844번 쉬운 계단 수 C++ 10844번 쉬운 계단 수 📝문제링크 : www.acmicpc.net/problem/10844 케이스들을 조금 나열해보면, 다음을 알 수 있다. 계단수가 0으로 끝나려면 0의 앞자리엔 1밖에 올 수 없다. 계단수가 9로 끝나려면 9의 앞자리엔 8밖에 올 수 없다. 계단수의 끝자리가 L = 1 ~ 8인 경우 L - 1 과 L + 1 이 모두 올 수 있다. 따라서 점화식은 다음과 같다. 그리고 N 자리수 계단수는, N자리 일때 끝자리 수가 0 ~ 9 인 수의 개수(dp[N][0] ~ dp[N][9]) 의 총합이다. 소스코드 #include using namespace std; int main() { intN; cin >> N; // dp[N][L] : N자리 계단수에 대해, 끝자리가 L인 수의 개수 int .. 공감수 0 댓글수 0 2020. 12. 3.
[BOJ] DP 9095번 1, 2, 3 더하기 C++ 9095번 1, 2, 3 더하기 📝문제링크 : www.acmicpc.net/problem/9095 #include #include using namespace std; voidfind_ans(int n, vector &dp) { for (int i = 4; i > T; vector dp; for (int i = 0; i > n; dp.assign(n + 1, 0); dp[1] = 1; dp[2] = 2; dp[3] = 4; find_ans(n, dp); cout 공감수 0 댓글수 0 2020. 11. 24.
[BOJ] DP 11726번 & 11727번 2xn 타일링 C++ 11726번 2xn 타일링 📝문제링크 : www.acmicpc.net/problem/11726 점화식 : $ dp[n] = dp[n - 1] + dp[n - 2] $ 소스코드 #include #include using namespace std; voidfind_ans(int n, vector &dp) { dp[n] = (dp[n - 1] + dp[n - 2]) % 10007; } int main() { intn; cin>> n; vector dp(n + 1); dp[0] = 1; dp[1] = 1; for(int i = 2; i 공감수 0 댓글수 1 2020. 11. 23.
[BOJ] DP 1463번 1로만들기 C++ 처음 접해본 DP 문제. 다이나믹 프로그래밍이란? 점화식을 잘 세워서 한번 한 계산은 다시하지 않도록 효율적인 계산을 하게 만드는 프로그래밍 1463번 1로 만들기 📝문제링크 : www.acmicpc.net/problem/1463 이 문제는 주어진 숫자 n에서부터 top down 방식으로 내려오면 경우의 수가 너무 많아 시간이 오래 걸린다. 1부터 시작해 bottom up 으로 올라가며 해당 숫자에 도달하는 최소의 경우를 계산해야 한다. 원리는, 1에서 2로 가는 최소 경로, 1에서 3으로 가는 최소 경로, 4로 가는 최소 경로 ... 이렇게 작은 문제푸터 풀어가는것이다. 4로 가는 최소 경로도 결국 2로 가는 최소 경로를 포함한다는 것을 이해하면 코드도 쉽게 이해할 수 있다. #include #incl.. 공감수 0 댓글수 0 2020. 11. 1.
[Python] 유사난수생성기 LCG(Linear Congruential Generator) 알고리즘 LCG의 존재는, random 모듈을 사용하지 않고 리스트 요소들을 shuffle 해야하는 파이썬 과제를 하다가 알게되었다. -과제의 출처는 42AI bootcamp python- Linear Congruential Generator(LCG)는 다음의 점화식을 따라 난수가 생성되는 알고리즘이다. $ X_{n+1} = (aX_{n}+c) \mod n $ 변수 a, c, m, 그리고 Xn 값이 난수의 주기에 큰 영향을 미친다. 0 ＜ a < m 0 ≤ c < m 0 < m $X_{n}$ = seed (시작값) 이 난수 생성기는 최대값이 m인 난수를 발생시킨다. 또한, 변수에 의해 난수가 결정되기 때문에, 변수를 알면 난수를 예상할 수 있다. 그러니까 Pseudo 난수 생성기인것이다. 그다지 좋은 알고리즘이라.. 공감수 0 댓글수 0 2020. 6. 4.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.