꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/14391 14391번: 종이 조각 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, www.acmicpc.net 이 문제의 핵심은 정사각형 칸을 어떻게 쪼갤 것인지를 구현하는 과정에 있었습니다. 아래와 같이 비트마스킹을 이용하여 모든 경우의 수를 탐색하면 풀 수 있습니다. 0: 숫자를 가로로 이어 붙인다 1: 숫자를 세로로 이어 붙인다 위 표를 비트마스킹으로 구현하면 아래와 같습니다. 0001110111110011 위 비트를 주어진 N, M을 기반으로 표로 만들면 다음과 같습니다. 개발환..

문제 링크입니다: https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net 얼핏 보면 시간 복잡도가 O(2^40)으로 보여 시간 안에 풀지 못할 문제처럼 보이는 문제였습니다. 하지만 다음과 같이 문제를 쪼개면 시간 내 풀 수 있는 문제입니다. (시간 복잡도: 400 * 2^20) 가능한 모든 조합에 대해 열을 직접 뒤집어 본다 (시간 복잡도: O(2^20)) 열은 이미 뒤집혔고 행을 뒤집을 차례인데 행 내 뒷면 동전 개수를 파악하면 직접 뒤집을 필요..

문제 링크입니다: https://www.acmicpc.net/problem/19942 19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net N이 최대 15이기 때문에 비트마스킹을 통해 완전탐색으로 풀어도 TLE가 발생하지 않는 문제였습니다. 적합한 재료 조합이 있고 같은 비용의 집합이 하나 이상이면 사전 순으로 가장 빠른 것을 출력해야 하므로 map와 같은 다소 기괴한 자료구조를 선언해야 합니다 key: 최소 비용 value: 재료 조합을 오름차순 한 set 개발환경:Visual Studio 2022 지적, 조언,..

문제 링크입니다: https://www.acmicpc.net/problem/1189 1189번: 컴백홈 첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다 www.acmicpc.net R, C, K 범위가 작기 때문에 완전탐색으로 풀어도 되는 문제였습니다. 개발환경:Visual Studio 2022 지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

문제 링크입니다: https://www.acmicpc.net/problem/14620 14620번: 꽃길 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므 www.acmicpc.net 전형적인 백트래킹 문제였습니다. 알고리즘은 아래와 같습니다. 1. 꽃은 상하좌우 칸이 모두 확보되어 있어야 하므로 y축, x축 모두 [0, N)이 아닌 [1, N - 1) 내에 꽃을 심어야 합니다. 2. 1번 로직에 따라 [1, N - 1) 내 가능한 칸마다 꽃을 심어봅니다. 2.1 꽃을 세 개 심었을 때 result 값을 갱신해줍니다. 3. 2번 과정을 마치면 최소 비용인 r..

문제 링크입니다: https://www.acmicpc.net/problem/9934 9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net 중위 순회 결과를 기반으로 트리를 그려나가면 되는 문제였습니다. 알고리즘은 아래와 같습니다. 1. 서브 트리의 root 노드는 서브 트리 중위 순회 결과의 가운데 노드입니다. 2. 문제에서 주어진 대로 서브 트리의 루트 노드 이후 왼쪽 서브트리, 오른쪽 서브트리를 방문하며 방문한 순서대로 벡터에 저장합니다. 3. 2번에서 구한 결과를 출력합니다. 개발환경..

문제 링크입니다: https://www.acmicpc.net/problem/14497 14497번: 주난의 난(難) 주난이는 크게 화가 났다. 책상 서랍 안에 몰래 먹으려고 숨겨둔 초코바가 사라졌기 때문이다. 주난이는 미쳐 날뛰기 시작했다. 사실, 진짜로 뛰기 시작했다. ‘쿵... 쿵...’ 주난이는 점프의 파 www.acmicpc.net 문제의 핵심은 주난이의 파동이 장애물을 만날 때까지 상하좌우 4방향으로 퍼진다는 것입니다. 알고리즘은 아래와 같습니다. 1. BFS 알고리즘을 수행하되 1.1 장애물이 없을 경우 현재 queue에 넣고 1.2 장애물을 만날 경우 해당 좌표는 다음 queue에 넣습니다. 1.3 현재 queue에 대한 탐색이 완료될 경우 현재 queue를 다음 queue로 세팅하고 점프 ..

문제 링크입니다: https://www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 동생의 위치가 계속 움직이기 때문에 기존 숨바꼭질 문제들의 심화 버전이었습니다. 알고리즘은 아래와 같습니다. 1. 주어진 N이 너무 크기 때문에 `visited[수빈이의 위치][경과한 초]`와 같이 이차원 배열을 선언하지 못합니다. 1.1 이 문제의 핵심은 수빈이가 [+1, -1] 혹은 [-1, +1]과 같이 이초에 걸쳐 동일한 위치로 이동할..

문제 링크입니다: https://www.acmicpc.net/problem/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net 주어진 N과 SCV의 최대 체력이 크지 않기 때문에 브루트포스로 풀어도 되는 문제였습니다. visited set의 키를 {scv 체력의 순열, 몇 번째 공격}으로 두는 것이 핵심이었습니다. 억지로 푼 느낌... 개발환경:Visual Studio 2022 지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

문제 링크입니다: https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net N의 최대 범위가 백만이기 때문에 O(N^2)으로는 풀 수 없는 문제였습니다. 알고리즘은 아래와 같습니다. 1. 원소 Ai에 대해 오큰수 페어를 지정해 주는 문제이므로 자료구조 스택을 이용했습니다. 2. 수열을 순회하며 다음과 같은 작업을 진행합니다. 2.1 스택이 비어있지 않을 경우 현재 원소와 스택의 top()과 비교합니다. 2.1.1 스택의 top()보다 현재 원소가 클 경우 스택의 ..