분류 전체보기

    [백준 1005] ACM Craft  C++

    [백준 1005] ACM Craft C++

    1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 위상 정렬, 다이나믹 프로그래밍 1. 문제해결 아이디어 indegree를 활용한 위상 정렬을 하는 문제이다. 위 그림에서 각각의 phase는 다음 phase로 넘어가기위해 모두 해결해야하는 과제와도 같다. 예를 들어서 phase2에서 phase3로 넘어가려면 phase2에 있는 건물을 모두 건설해야 넘어갈 수 있다. 따라서 phase2에서 가장 오래걸리는 건물이 해당 phase에서 걸리는 시간이 되고, 이전 phase의 최대 시간만큼만 next phase의..

    벽 부수기 게임

    벽 부수기 게임

    요새 알고리즘 실력이 정체가 된 것 같다. 나름 꾸준히 공부한다고 생각했는데 절대적인 양이 부족한건지 최근 백준 문제들이나 학교 과제들을 풀려고 하면 숨이 막히는 기분이 든다. 조고리즘 지난 2문제는 80점으로 대충 제출하고 마무리했다. 둘 다 branch and bound라는 백트래킹의 업그레이드 된 알고리즘이었는데, 시간을 줄이기 위한 bound를 찾기도 어려웠고, 찾는다 해도 세부적인 재귀 함수의 구현에서 벽을 느꼈다. 그래서 시간을 투자해도 내가 풀 수 있을거란 자신이 조금도 들지 않아서 둘 다 적당히 만들어서 제출했다. 2문제 연속 벽을 느끼는 문제였고, 최근 푸는 boj문제들도 시간이 너무 오래 걸리거나 스스로 풀이를 생각해 내지 못한 경우가 종종 있었다. 그래서 벽을 깨보려고 마음먹었다. 오..

    SystemSoftware - Linking #1

    SystemSoftware - Linking #1

    컴파일된 object 파일들을 linking해서 exe파일로 만드는 과정에서 어떤 일들이 일어나는지 알아보자 // main.c int sum(int *a, int n) int array[2] = {1, 2} int main(){ int val = sum(array, 2); return val; } // sum.c int sum(int *a, int n){ int i, s = 0; for(i = 0; i < n; i++){ s += a[i]; } return s; } main.c의 sum 함수는 어떤 과정을 통해서 sum.c의 sum 함수를 불러와서 기능을 수행할 수 있을까? 위와 같이 여러 개로 이루어진 파일들을 연결하는 과정을 Linking이라고 한다. 먼저 cpp(C Pre-Processor 전처리)..

    [백준 14939] 불 끄기 C++

    [백준 14939] 불 끄기 C++

    14939번: 불 끄기 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄 www.acmicpc.net 그리디 알고리즘 1. 문제해결 아이디어 전구의 가장 윗 라인에서 스위치를 누르는 모든 경우(2^10=1024)를 시도해 본다. 그리고 두 번째 라인을 부터는 현재 열의 바로 윗 행의 전구가 켜져있는지 꺼져있는지에 따라서 스위치를 누를지 말지가 결정된다. 만약 바로 윗 행의 전구가 켜져있는데 현재 열의 스위치를 누르지 않는다면 앞으로 윗 행의 전구를 끌 방법은 없기 때문이다.(방향 : 왼쪽 상단부터 오른쪽 하단) 이렇게 하면 1~9 행은 모든 전구가 꺼질..

    [백준 2011] 암호코드 C++

    [백준 2011] 암호코드 C++

    2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 다이나믹 프로그래밍 1. 문제해결 아이디어 현재 자릿수에서 어떤 암호가 만들어 질 수 있는지 dp를 이용해서 해결해야한다. 우선 0은 암호로 바꿀 수 없다. 하지만 0 이전에 1 또는 2가 있다면 암호로 바뀔 수 있다. 숫자 3 이상과 이어지는 암호는 없다. 현재 숫자가 2인 경우 다음 숫자가 0 ~ 6 인 경우만 숫자 2개를 사용해서 암호를 만들 수 있다. dp배열 : dp[i][2] -> i번 자리수 이후로 숫자를 1개 또는 2개를 사용해서 만들 수 있는 경우를 저장하는 배열..

    Attack Lab Solution  Phase_1 ~ Phase_5

    Attack Lab Solution Phase_1 ~ Phase_5

    - Code Injection Attacks : CTARGET %rsp를 0x38 만큼 빼주는 것으로 보아 buffer의 크기는 0x38bytes임을 알 수 있습니다. Phase1은 touch1을 호출만 하면 되므로 입력에 0x38bytes 만큼 dummy값을 준 후 touch1함수가 존재하는 주소인 40 18 c5 값을 리틀-엔디안 방식으로 입력해주었습니다. Answer : - Code Injection Attacks : CTARGET Touch2를 실행하고 %edi값과 Cookie값을 비교해서 같은 경우에 통과합니다. Touch2함수를 실행하기 전에 %rdi 레지스터에 Cookie값을 넣어주고 Touch2 함수를 실행해야 합니다. Buffer공간을 0x38만큼 할당 받은 후의 %rsp위치를 보니 0x..

    [백준 2143] 두 배열의 합 C++

    [백준 2143] 두 배열의 합 C++

    2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다 www.acmicpc.net 이분 탐색 1. 문제해결 아이디어 문제에서 정의된 부 배열의 최대 크기는 N(N+1)/2 가 됨을 알 수 있었다. (1~N까지의 합) N, M이 최대 1000이므로 부 배열의 크기는 최대 500,000 이다. 따라서 배열에 담은 후 nlogn 연산이 충분히 가능함을 알 수 있었다. 이분 탐색을 수행하기 위해 subB배열을 정렬한다. T 에서 subA의 원소를 뺀 값이 subB에 있는지 ..

    힙 정렬(heap sort) <priority queue> C++

    min heap 구현 heap[i]의 값은 heap[i * 2] 와 heap[i*2 + 1]의 사이에 있다 BST(이진 탐색 트리)구조를 기반으로 한다 STL의 priority queue를 사용하면 되므로 직접 구현할 일은 없겠지만 heap 자료구조를 직접 구현해 본다는 점에서 의미있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include #include using namespace std; vector heap; void push_heap(vector& heap, int newvalue){ heap.push_back(newvalue); int idx = he..

    [백준 16929] Two Dots C++

    [백준 16929] Two Dots C++

    16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net DFS 1. 문제해결 아이디어 DFS를 통해서 사이클을 찾는 문제이다. 시작 알파벳과 같은 칸만 이동하며 시작 좌표에 다시 돌아올 때까지 or 돌아오지 못할 때까지 dfs 를 돌린다. 하나의 dfs루프에서 방문한 점을 backtracking 하지 않고 방문처리 기록을 남겨둔다. 2. 코드 : dfs를 돌면서 방문을 했거나 시작점으로 지목된 점에 방문을 한 경우 + 현재 점이 시작점이 아닌경우 (시작하자마자 return 되는것 방지) 1 2 3 4 5 6 ..

    [백준 1309] 동물원 C++

    [백준 1309] 동물원 C++

    1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 다이나믹 프로그래밍 기초 1. 문제풀이 아이디어 row행에서 사자를 놓는 모든 경우의 수 = row행에 사자를 놓지 않는 경우 + row행의 1번에만 사자를 놓는 경우 + row행의 2번에만 사자를 놓는 경우 row행에 사자를 놓지 않는 경우 = row+1행에 사자를 놓지 않는 경우 + row+1행의 1번에만 사자를 놓는 경우 + row+1행의 2번에만 사자를 놓는 경우 row행의 1번에만 사자를 놓는 경우 = row+1행에 사자를 놓지 않는 경우 + row+1행의 2번에만 사자를 놓는 경우 row행의 2번에만 사자를 놓는 경우 = row+1행에 사자를 놓지 않는 경우 + row+1행의 1번에만..