문제 이해 단계 문제가 이해하기가 어려웠는데 최대한 쉽게 풀어써보겠다. 전체 문자열이 존재하고 하나씩 드러나게 하는데 이걸 전체 단어로 볼 때 사전순으로 가장 빠르게 하는 것이다. 앞에 있는 알파벳이 높을수록 사전순으로 빠르기 때문에 맨 앞부터 높은 알파벳부터 채우는 것이다. 예제 출력 3번을 보면 어느 정도 이해가 된다. 문제 접근 단계 해당 문제에서 포인트가 되는 부분은 총 2가지이다. 1. 다음에 올 문자를 정하는 규칙 2. 그 문자를 적절한 곳에 위치시키는 방법 1번은 문제 조건에서 사전 순으로 빠르게 선택하라고 했기 때문에 빠른 순서대로 선택해야 하기 때문에 중요한 것이고, 2번은 문자가 무조건 뒤에 추가되는 것이 아닌, 사이사이에 들어갈 수도 있기 때문이다. 예를 들어 AIK 다음에 AINK ..

문제 이해 단계 https://www.acmicpc.net/problem/20164 홀수개의 숫자가 입력으로 들어온다. 이때 숫자의 개수에 따라 다음에 규칙에 따른다. 숫자의 개수가 1개 -> 그대로 숫자의 개수 2개 -> 두 수를 더함 숫자의 개수 3개 이상 -> 임의의 지점에서 세 수를 나누어서 더함 위 행위를 숫자의 자릿수가 하나가 남을 때까지 반복한다. 이 과정에서 홀수가 총 몇 번 등장하는지를 세는 것인데, 숫자의 개수가 3개 이상일 때는 임의의 지점에서 나누기 때문에 여러 가지 경우의 수가 생긴다. 그래서 나올 수 있는 홀수의 최댓값과 최솟값을 구하는 문제이다. 문제 접근 단계 해당 문제에서의 핵심은 숫자의 개수가 3개 이상일 때 숫자를 3개의 분할로 나누는 것이다. 이걸 어떤 식으로 나눠야 ..

문제 이해 단계 https://www.acmicpc.net/problem/2615 문제는 그냥 우리가 흔히 알고 있는 오목에 관한 문제이다. 흑돌과 백돌의 배치가 주어졌을 때 현재 상태가 누가 이긴 상태인지, 아니면 승부가 나지 않은 상태이지 판가름하는 문제이다. 이 문제 조건에서 5개 연속을 넘은 6개 연속, 7개 연속은 이긴 것으로 판정하지 않는다. 또한 오목이 발생하는 것은 단 하나이며, 흑돌과 백돌이 동시에 이기는 경우는 발생하지 않는다. 중요한 조건은 출력할 때, 가장 왼쪽에 있는 바둑알의 좌표를 출력하는 것이다. 만약 세로로 일자로 놓여있다면 가장 높이 있는 바둑알의 좌표를 출력한다. 문제 접근 단계 이 문제에서 중요한 것은 어떻게 오목을 판정할 것인가에 대한 문제이다. 오목은 5개의 같은 바..

문제 이해 단계 https://www.acmicpc.net/problem/16926 문제 조건만 보면 무슨 소리인지 전혀 모르겠는데 밑에 첨삭된 그림을 보면 어떤 식으로 배열하라는지 바로 알겠다. 그림처럼 가운데를 중심으로 X자 모양으로 2개의 직선과 + 모양으로 2개의 직선을 그리는 것이다. 그리고 가운데를 중심으로 45도를 단위로 돌렸을 때의 결과를 구하는 문제이다. 문제 접근 단계 해당 문제에서 요구하는 것은 배열을 회전시키는 것이다. 회전시켰다는 것을 확인하기 위해 12시 방향에 있던 5가 3시 방향에 위치하는 등, 어떤 그룹의 이동을 통해 확인한다. 여기서 생각이 든 게, 저 배열들을 확실한 그룹으로 나눌 수 없을까? 아래 그림같이 나누면 n이 아무리 늘어나도 같은 방식으로 포함시키면 되기 때문..

연결 리스트 스택 연결된 스택 구조 노드 = 데이터 필드 + 링크 필드 포인터 : 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번째 조건에서 순서가 고정되어..

문제 이해 단계 https://www.acmicpc.net/problem/14719 2차원 맵이 주어진다. 이때 같은 층에 열로 가둬질 때 (위 그림처럼) 빗물을 담을 수 있다. 이 조건에서 2차원 맵의 크기가 주어지고, 각 행마다의 높이가 주어질 때 빗물의 총량을 구하는 문제이다. 문제 접근 단계 빗물의 총량을 구하기 위해서는 주어진 2차원 맵을 탐색 하면서 연산할 수 있는 일반화된 알고리즘이 필요하다고 생각했다. 그래서 일반화된 연산식을 만드는 것을 중점으로 생각했다. 첫 번째부터 쌓인 블록부터 탐색한다고 생각한다. 첫 번째 블록과 어떤 블록 사이에는 빗물이 쌓인다. 첫 번째 블록이 빗물을 담는 시작점이라고 생각(즉, 왼쪽 벽)하자. 그렇다면 첫 번째 블록과 쌍이 되는 오른쪽 벽은 어떻게 결정할까? ..