728x90 전체 글 썸네일형 리스트형 [백준알고리즘] 11047번: 동전 0 -Python [백준알고리즘] 11047번: 동전 0 -Python https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 그리디 알고리즘(탐욕 알고리즘)의 문제이다. 그리디 알고리즘의 경우에는 동적 계획법과 달리 항상 최적의 해를 준다고 보장되지 않는다. 각 Step에서 Decision에 의해서는 Optimization Value를 선택하지만, 전체를 봤을 때에는 Optimization이 보장되지는 .. 더보기 [백준알고리즘] 2293번: 동전 1 -C [백준알고리즘] 2293번: 동전 1 -C https://www.acmicpc.net/problem/2293 단계별로 풀어보기 마지막 '동적 계획법 1'의 마지막 문제였다. 그래서 기쁜 마음으로 봤는데 생각보다 쉬워서 흡족했다..ㅎㅎ 처음에는 일단 가볍게 동전 가치의 내림차순으로 정렬한 후에 재귀를 사용해서 해봤다. 역시나 시간초과가 발생했다. 그래서 다음에 사용한건 nsize와 target의 크기를 입력받아 nsize x target행렬을 만든 것이다. 이때부터는 점화식을 사용했기 때문에 내림차순 정렬이 필요없어진다. 사용했던 점화식은 다음과 같다. dp[i][j] = dp[i - 1][j] + dp[i][j - nlist[i]] (i번째 동전없이 j가치를 만들 수 있는 방법의 수) + (i번째 동전을.. 더보기 [pwnable.kr Toddler's Bottle] uaf write up Use After Free bug라서 uaf인가 보다. 들어가 보니 저한테는 끔찍한 일이 있었습니다. uaf@prowl:~$ ls -l total 24 -rw-r----- 1 root uaf_pwn 22 Sep 26 2015 flag -r-xr-sr-x 1 root uaf_pwn 15463 Sep 26 2015 uaf -rw-r--r-- 1 root root 1431 Sep 26 2015 uaf.cpp 저는 cpp을 잘 볼 줄 모릅니다.. hackctf도 g++로 풀어야 하는 거 건너뛰고 풀고 있었는데..! 그래도 일단 떨리는 손으로 침착하게 코드를 확인해봤습니다. #include #include #include #include #include using namespace std; class Human{.. 더보기 [pwnable.kr Toddler's Bottle] blackjack write up blackjack을 풀려고 보니 nc로 접속해서 해결하도록 되어있었습니다. 쓰여있는 주소로 일단 가서 소스코드부터 확인했습니다. 소스를 보고 취약점을 발견했습니다. 발견한 취약한 로직은 다음과 같습니다. int betting() //Asks user amount to bet { printf("\n\nEnter Bet: $"); scanf("%d", &bet); if (bet > cash) //If player tries to bet more money than player has { printf("\nYou cannot bet more money than you have."); printf("\nEnter Bet: "); scanf("%d", &bet); return bet; } else return b.. 더보기 [알고리즘]Knuth's optimization 크누스 최적화 백준의 11066번 문제를 풀다가 발견한 최적화 기법이다. (문제를 해결했던 코드) 이 알고리즘은 동적 계획법으로 해결하는 문제에서 특수한 조건일 때 시간 복잡도를 \(O(n^3)\)에서 \(O(n^2)\)까지 줄일 수 있는 강력한 알고리즘이다. 사용할 수 있는 동적 계획법의 종류에는 이차원 배열인 \(C\)와 \(C\)를 이용한 Dynamic Programming을 적용한 이차원배열인 \(DP\)가 있다고 했을 때 다음과 같은 조건이 필요하다. 점화식의 형태: \(DP[i][j] = min(DP[i][k] + DP[k][j]) + C[i][j]\) \((i < k < j)\) 사각 부등식: \(C[a][c] + C[b][d] 더보기 [백준알고리즘] 11066번: 파일 합치기 -Python [백준알고리즘] 11066번: 파일 합치기 -Python https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 www.acmicpc.net 추가) 새로 풀어봤다. 밑에 나오는 크누스 최적화를 사용 안 하고 그냥 .. 더보기 [smashthestack - io] level7 write up level7@io:~$ ls -l total 24 -rw-r--r-- 1 level7 level7 23261 Jul 25 22:33 tags level7은 사실 설마? 하고 풀었는데 맞아버렸습니다.. 코드는 아래와 같습니다. #include #include #include int main(int argc, char **argv) { int count = atoi(argv[1]); int buf[10]; if(count >= 10 ) return 1; memcpy(buf, argv[2], count * sizeof(int)); if(count == 0x574f4c46) { printf("WIN!\n"); execl("/bin/sh", "sh" ,NULL); } else printf("Not today so.. 더보기 [smashthestack - io] level6 write up level6@io:~$ ls -l total 96 -rw-r--r-- 1 level6 level6 97729 Aug 18 22:58 tags 오늘은 level6를 풀어보겠다. 확실히 pwnable.kr 보다는 아직 쉬운 수준입니다. level06.c의 소스코드는 다음과 같습니다. //written by bla //inspired by nnp #include #include #include enum{ LANG_ENGLISH, LANG_FRANCAIS, LANG_DEUTSCH, }; int language = LANG_ENGLISH; struct UserRecord{ char name[40]; char password[32]; int id; }; void greetuser(struct UserRecord u.. 더보기 이전 1 ··· 44 45 46 47 48 49 다음
