문제 이해 단계 주어지는 입력은 사용할 수 있는 숫자 N과 만들어야 하는 Number 2개이다. 숫자 N을 통해 할 수 있는 작업은 아래의 2가지 작업 밖에 없다. 1. 사칙연산 2. N을 연속해서 이어 붙이기(ex : 22, 33, 555) 이를 이용해서 Number를 만드는데, 숫자 N을 최대한 적게 사용해야 한다. 이때 숫자 N은 몇 개일까? 만약 8개가 넘는다면 -1을 반환한다. 문제 접근 단계 처음에는 해당 문제가 단순한 사칙연산을 이용한 수학 연산 문제라고 생각했는데, N을 연속해서 이어 붙일 수 있다는 조건에서 단순한 수학 연산은 아닐 것이라는 생각이 들었다. 그래서 일단 N이 1개 일 때부터 만들 수 있는 조합에 대해 적어보기로 했다. N이 1개일 때 N N이 2개일 때 NN, (N+N),..

문제 이해 단계 0과 1로만 이루어진 2개의 서로 다른 2차원 맵이 주어진다. 왼쪽 맵은 0일 때 있는 퍼즐이 있는 것, 오른쪽 맵은 1일 때 퍼즐이 있는 것이다. 왼쪽 맵의 빈칸에 오른쪽 퍼즐을 끼우는데 딱 맞는 퍼즐만 끼울 수 있다. 이때 중요한 것은 퍼즐을 회전해서 끼울 수 있다는 것이다. 이러한 조건일 때 최대한 많은 퍼즐을 끼웠을 때 총퍼즐의 칸 수를 구하는 문제이다. 문제 접근 단계 일단 해당 문제의 유형부터 유추해 보자면 0과 1로만 이루어진 2차원 맵이 주어진 점, 그리고 퍼즐을 알아내야 하는 점을 보면 곧바로 그래프 탐색을 포함한 문제라는 것을 유추할 수 있다. DFS나 DFS 중 하나로 풀면 될 것 같은데 딱히 경로 자체는 그렇게 중요한 점이 아닌 것 같아서, 두 개 중 아무거나 상관없..

문제 이해 단계 알파벳 대문자 3글자로 이루어진 공항(정점)이 존재한다. 그리고 입력으로 티켓(간선) [a, b] 형태로 a->b 로이 단방향 정보로 주어진다. 이때, 모든 항공권을 사용한다는 말은 모든 간선을 사용한다는 말이다. 모든 도시를 방문할 수 없는 경우는 주어지지 않는다는 말은 결국엔 모든 정점을 방문한다는 소리이다. 이때 방문했던 공항 순서대로 출력하도록 하는 게 해당 문제이다. 여기서 한 공항에서 티켓이 여러 개 있다면 사전순(오름차순)으로 더 빠른 것이 우선시된다. 문제 접근 단계 해당 문제는 위에서 말했듯이 공항은 정점이고, 티켓은 두 정점을 잇는 단방향 정보인 간선이다. 그렇기 때문에 해당 문제는 그래프 탐색 문제일 가능성이 높다. 그래서 BFS 또는 DFS로 접근해야 할 것 같은데,..

문제 이해 단계 n개의 섬이 주어지고, 정보로는 각 섬이 이어지는 정보와 그 거리 비용이 주어진다. 이 조건에서 모든 섬을 방문할 수 있도록 선을 이을 때, 돈을 최소한으로 쓰게 하는 문제. 문제 접근 단계 해당 문제는 그림으로만 봐도 알겠지만, 가중치가 주어진 노드 문제이다. "최소한 적은 비용을 골라라" 이 말은 그리디에서 자주 쓰는 말이어서 일단 그리디라고 가정하고 문제를 풀어보겠다. 비용을 최소화하려면 어떻게 해야 유리할까? 1. 비용이 싼 선(다리)을 고른다. 2. 선(다리)을 최대한 적게 쓴다. 2가지 일단 생각난다. 2번 조건이 확실한지 나도 잘 모르겠어서 그림을 여러 번 그려봤다. 왜냐하면 직통으로 가는 다리가 엄청 비싸고, 돌아서 가는 다리가 엄청 싸면 "돌아서 가는 게 더 싼 거 아닌가..

문제 이해 단계 숫자로 이루어진 문자열이 주어지고, 그중에서 없애야 할 문자의 수 k가 주어진다. k개를 지워서 문자열 중 가장 큰 숫자를 만드는 것이다. 여기서 중요한 점은 무조건 k개를 다 써야 한다는 것이다. 문제 접근 단계 상식적으로 한번 접근해 보자. 어떤 문자열(숫자배열)일수록 크다고 할 수 있을까? 당연히 기본적으로 다른 숫자들보다 자릿수가 많으면 비교할 필요도 없이 더 큰 숫자일 것이다. 예를 들어 두 자릿수의 최솟값 (10)은, 한 자릿수의 최댓값(9)보다 무조건 큰 것처럼 말이다. 그럼 비교하는 두 숫자의 자릿수가 같다면? 가장 높은 10의 자리(숫자 배열의 첫 인덱스)가 높은 숫자가 큰 것이다. 예를 들어, "399"와 "400"을 비교하면, 가장 높은 자릿수인 '3'과 '4'만 보고..

연결 리스트 스택 연결된 스택 구조 노드 = 데이터 필드 + 링크 필드 포인터 : top 연산 init, is_empty, is_full, push, pop 장점 크기가 제한되지 않는다. 단점 동적 메모리 할당이나 해제함 → 삽입이나 삭제 시간이 좀 더 걸림 연결 리스트 스택 연산 초기화 함수 top 포인터 값을 NULL로 한다. is_empty top 포인터 값이 NULL(true) → 공백(true) top 포인터 값이 false → 적어도 한 개의 노드가 있음 is_full 동적 메모리 할당받아 새 노드를 사용하므로 힙 공간의 크기만큼 사용 가능 → 많은 메모리 공간 사용 가능 → 포화상태 안됨(false) push(삽입연산) 먼저 동적 메모리 할당으로 새 노드를 만들고 데이터를 넣는다. temp ..

문제 이해 단계 https://www.acmicpc.net/problem/12933 "quack"이라는 문자열이 존재하면 오리가 한 마리 있다는 의미인데, 이 문자들이 여러 개 겹쳐있다. 특이한 점은 quackquack 이런 식으로 연속적으로 문자열을 이을 수 있는 경우에는 한 마리로 취급한다는 것이다. 이런 조건일 때 오리를 최소로 했을 때의 오리 수를 구하는 문제. 문제 접근 단계 어떻게 풀지 고민하다가 힌트를 보고 감을 잡았다. 녹음: quqaquuacakcqckkuaquckqauckack 오리 1: ____q_u__a___ck_______________ 오리 2: __q__u_ac_k_q___ua__ckq_u__ack 오리 3: qu_a_______c___k__qu___a_ck___ 힌트에서는 오..

문제 이해 단계 https://www.acmicpc.net/problem/18427 N명의 학생이 각각 최대 M개의 블록을 가지고 있다. 학생들이 가지고 있는 블록은 전부 길이가 다르다. 예를 들어 1번 학생이 높이가 2,3,4인 블록을 가지고 있는 것처럼 모두 길이가 다르다. 높이 H가 주어지는데, N명의 학생이 순서대로 최대 1개를 사용해서 블록을 쌓을 때 정확히 높이 H가 될 수 있는 경우의 수를 구하는 문제 문제 접근 단계 일단 해당 문제의 키워드에 주목했다. 1. 최대 1개까지 쓸 수 있다.(안 써도 된다) 2. 1번 학생 ~N번까지 순차적으로 블록을 쌓는다. 1번 조건에서 해당 문제가 여러 가지 경우의 수로 나뉘는 것을 계산하는 문제라는 것을 알았고, 무엇보다도 2번째 조건에서 순서가 고정되어..