전체 글

[BOJ] 16946번: 벽 부수고 이동하기 4

16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 제한 조건 - 시간 제한 : 2s - 공간 제한 : 512MB 풀이 사용 - 사용 언어 : C++17 - 사용 시간 : 184ms - 사용 공간 : 25992KB 풀이 설명 - Connected Component를 그래프 순회(BFS)를 통해 분류 - Connected Component의 크기는 따로 리스트에 기록 #include #include #include #include using namespace std; int rows, cols;..

[BOJ] 9240번: 로버트 후드

9240번: 로버트 후드 첫째 줄에 로버트 후드가 발사한 화살의 수 C (2 ≤ C ≤ 100,000)가 주어진다. 다음 C개 줄에는 화살의 좌표가 주어진다. 좌표는 정수이고, 절댓값은 1,000을 넘지 않는다. www.acmicpc.net 제한 조건 - 시간 제한 : 1s - 공간 제한 : 256MB 풀이 사용 - 사용 언어 : C++17 - 사용 시간 : 180ms - 사용 공간 : 2228KB 풀이 설명 - Graham Scan으로 Convex hull을 구하는 문제 1) 좌하단 점을 기준으로 정점들을 기울기 크기(x축과 각도)로 순으로 정렬한다. 2) 순회하며 ccw로 회전하는 점들만 스텍에 넣는다. 3) 결과적으로 스텍엔 Convex Hull만 남게된다. - Roatating Calipers를 ..

[BOJ] 7620번: 편집 거리

7620번: 편집 거리 가장 짧은 편집 스크립트를 출력한다. 한 명령을 한 줄에 하나씩 출력하며, 문제의 괄호에 나와있는 (a, d, m, c)중 하나를 출력하고, 그 명령을 수행하는데 사용한 글자를 출력한다. (출력할 글자 www.acmicpc.net 제한 조건 - 시간 제한 : 8s - 공간 제한 : 128MB 풀이 사용 - 사용 언어 : C++17 - 사용 시간 : 2292ms - 사용 공간 : 72044KB 풀이 설명 - DP문제 - 메모리 제한을 극복하기 위한 테크닉 연습문제 1) 편집거리: (knapsack에서 배웠던) 1차원 배열 두 줄(2N) 이용 2) 경로 출력을 위한 4가지 연산 저장: int 대신 bitset 등의 자료형에 비트연산 이용해 정보 압축 - 4가지 경우 (a, d, c, ..

[Algorithm] Backtracking

백트래킹은 DFS를 기반으로 한 문제풀이방법이다. DFS (Depth-First Search, Preorder Tree Traversal) 란? 뿌리가 되는 노드부터, 그 노드의 모든 후손노드를 차례로 방문하는것이다. // DFS pseudo code void depth_first_search(node v) { node u; visit v; for (each child u of v) depth_first_search(u); } Backtracking 방법은, State Space Tree (상태 공간 트리)를 제작한다. 상태공간 트리의 유망하지 않은 가지를 pruning(가지치기) 하여, 모든 경우를 순회하지 않고 답을 찾을 수 있다. Promising 이란? - 이후 전혀 해답이 나올 가능성이 없는 노..

[BOJ] 17136번: 색종이 붙이기

17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 제한 조건 - 시간 제한 : 1s - 공간 제한 : 512MB 풀이 사용 - 사용 언어 : C++17 - 사용 시간 : 92ms - 사용 공간 : 1176KB 풀이 설명 - 백트랙킹을 이용하여 풀이 - Matrix를 순회하며 1이 존재하는 위치를 찾아 그 위치에 크기 5 종이를 붙혀본다. - 유효했다면 같은 행동을 계속 반복하고, 그렇지 않으면 행동을 되돌리고 더 작은 색종이를 붙힌다. - 정답이 될때까지 반복한다. #include #include #in..

[Visual Studio] #pragma warning(disable:4996)

Microsoft Visual Studio의 C++는 scanf 가 버퍼 오버플로우 해킹의 우려가 있어 scanf_s 사용을 강제한다. 이는 #pragma warning(disable:4996) 혹은 #define _CRT_SECURE_NO_WARNINGS 전처리를 삽입하여 에러를 무시할 수 있다. +추가) SDL 검사 설정을 해제하여 위의 문제를 해결할수도 있다. /sdl(추가 보안 검사 사용) Microsoft C/C++ 컴파일러 /sdl 옵션을 사용하면 권장되는 SDL(보안 개발 수명 주기) 검사 및 경고를 사용할 수 있습니다. docs.microsoft.com

[BOJ] 6236번: 용돈 관리

6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 제한 조건 - 시간 제한 : 1s - 공간 제한 : 128MB 풀이 사용 - 사용 언어 : C++17 - 사용 시간 : 20ms - 사용 공간 : 2008KB 풀이 설명 - 이분탐색을 통한 Parametric Search 방법 - 답을 도출해내는 방법을 찾는게 아니고 계속해서 답을 가정하고 검증하는 방식 - 내가 원하는 인출회수 M번보다 가정한 금액의 인출회수가 적다면 금액을 줄이고, 인출회수가 많다면 금액을 늘린다. #include #include using nam..

[BOJ] 1992번: 쿼드트리

1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 제한 조건 - 시간 제한 : 2s - 공간 제한 : 128MB 풀이 사용 - 사용 언어 : C++17 - 사용 시간 : 0ms - 사용 공간 : 1228KB 풀이 설명 - Top-down 흐름의 Divide-and-conquer 문제 #include #include #include using namespace std; vector matrix; string GetQaudTreeString(int offset_y, int offset_x, int si..

[BOJ] 2448번: 별 찍기 - 11

2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 제한 조건 - 시간 제한 : 2s - 공간 제한 : 128MB 풀이 사용 - 사용 언어 : C++17 - 사용 시간 : 20ms - 사용 공간 : 2460KB 풀이 설명 - 프랙탈 형태의 패턴 출력 문제 - divide-and-conquer로 작은 문제로 쪼개 해결하였다. - 재귀형식으로 Top-down으로 문제를 접근하였다. #include #include #include using namespace std; int GetHeight(int generation) { return 3 * pow(2, generati..

[Git] .gitignore 적용안될때

git rm -r --cached . git add . git commit -m "fixed untracked files" 캐쉬를 삭제하고 다시 커밋해봅니다.