문제 이해 단계 https://www.acmicpc.net/problem/2447 들어오는 입력 N은 무조건 3의 거듭제곱수로 들어온다(3,9,27...) 그리고 만들어지는 모양에 있는 맵의 전체 크기는 NxN이라고 한다. 패턴의 형식은 정사각형을 9 등분하여 이를 3으로 나누고.. 어쩌고 저쩌고 해서 하는 것 같은데, 사실 그냥 위에 있는 그림과 예시를 보는 게 빠르다. 사실 이 문제는 패턴을 파악하는 것부터가 문제풀이에 시작이기 때문에 문제 접근 단계에서 설명하겠다. 문제 접근 단계 패턴 특징 알아내기 해당 문제는 편하게도 "재귀적인 패턴으로 별을 찍어보자"라고 말해줘서 재귀를 사용해야 한다는 것을 쉽게 유추할 수 있다. 그럼 재귀함수와 해당 별 찍기 패턴을 어떻게든 엮어서 생각해 보자. 일단 재귀함..

문제 이해 단계 https://www.acmicpc.net/problem/21608 자리를 정하는 학생의 번호와 그 학생이 원하는 4명의 학생 번호가 한 줄씩 입력으로 들어온다. 입력 순서가 자리를 정하는 순서이다. 여기서 자리를 정하는 것은 3가지 우선순위가 존재한다. 1. 빈칸 중 자기가 원하는 학생들과 제일 많이 인접한 곳에 위치한다. 2. 1번 조건이 여러 개라면 그중에서 주위에 빈자리가 많은 곳에 위치한다. 3. 1,2번 조건이 여러 개면 작은 행, 작은 열로 자리를 앉는다. 여기서 "인접"이란 말은, 자신의 상하좌우 한 칸에 있으면 인접한 것이다. 이렇게 모두 자리를 앉고, 주위에 자신이 원하는 사람이 얼마나 앉았느냐에 따라 점수를 정한다. 0명 = 0점 1명 = 1점 2명 = 10점 3명 =..

문제 이해 단계 https://www.acmicpc.net/problem/22859 상당히 문제가 길고 조건이 많은 문제라 필요한 조건만 밑에 적어보자. HTML 문법 형식으로 줄 바꿈 없이 한 줄로 입력이 들어온다. 핵심이 되는 태그는 이다. 1. 모든 태그와 문자열은 ~ 사이에서 벌어져야 한다. 2. 안에 공백은 존재하지 않는다. 그러니까 이런 식으로 주어지진 않는다는 소리이다. 해당 조건이 주어질 때, 해 당 출력 형식으로 정확히 출력하는 문제이다. 문제 접근 단계 이 문제는 딱 봐도 구현문제다. 그냥 대놓고 구현해 볼 테 면 해봐라 이런 식인 것 같다. 구현해야 할 부분이 많을 것 같아서 함수를 잘 나눠서 설정해둬야 할 것 같다. 일단 필요한 기능을 살펴보자. 최우선적으로 (1) 들어온 문자열을 ..

백준에서 알고리즘 문제를 풀다 보면 띄어쓰기나 특정 단어를 기준으로 분리해야 할 때가 있다. 나도 그런 일이 잦아서 사용하기 편한 라이브러리 함수들을 쓰려고 하는데, 이상하게 Split 관련 부분은 항상 헷갈려서 검색을 하게 된다. 그래서 이번 기회에 블로그에 확실히 정리하려고 한다. istringstream #include 헤더를 포함시키면 사용 가능 문자열 format을 파싱(parsing)할 때 쓰는 클래스이다. 문자열에서 필요한 값을 추출하고 공백과 '\n'을 무시한다. 코딩 테스트에서 활용 #include #include using namespace std; int main(){ string str1 = "This is Test"; string str2 = "AB/CDE/DFDG/ASCD"; /..

문제 이해 단계 https://www.acmicpc.net/problem/22856 이진트리에서 왼쪽노드 -> 자기 -> 오른쪽 노드 순으로 방문하는걸 중위 순회라고 한다. 그래서 원래 중위 순회는 제일 왼쪽 노드에서부터 출발하는데, 여기 문제에선 조금 다르다. 해당 문제에서는 무조건 루트 노드인 1에서 출발한다고 가정하고 이동을 거쳐 중위순회를 흉내 내는 것이다. 이때 움직였던 모든 이동 횟수를 구하는 문제 문제 접근 단계 필요한 정보 찾기 일단 노드 1개의 관점에서 바라보자. 각 노드의 관점에서 몇 가지의 정보가 있을까? 총 4개가 있다. 해당 노드의 번호, 왼쪽 자식 노드의 번호, 오른쪽 자식 노드의 번호, 부모 노드의 번호 그리고 중위순회를 할 때 필요한 정보를 생각해 보자. 중위 순회를 할 때는..

문제 이해 단계 재료의 개수 N개가 주어지고 각 재료마다의 쓴맛과 단맛 정보가 주어진다. 쓴맛은 쓴맛끼리 곱연산을 하고 단맛은 단맛끼리 합연산을 해서 (총 쓴맛 - 총 단맛) 해서 최대한 절댓값이 작은 수를 구하는 문제. 문제 접근 단계 일단 문제 조건에서 봐야 할 점은 재료 N이 최대 10개까지만 있다는 점이다. 10개밖에 안되기 때문에 브루트포스가 가능하고, 시간적인 부담이 적다는 것을 알 수 있다. 우선 구해야 하는 것이 뭔지부터 살펴보자. 구하자고 하는 것은 연산의 결과인데, 크게 보면 N개의 재료 중에서 몇 가지를 골라서 그 안에 값을 계산하는 것이다. 여기서 중요한 점은 몇 가지라는 점, 1개가 될 수도 있고 2개가 될 수도 있고 전부가 될 수도 있는 것이다. 그래서 뭔가 공식을 세우거나, 재..

문제 이해 단계 https://www.acmicpc.net/problem/20207 문제가 헷갈리게 적혀있어서 풀면서 문제를 이해하였다. 이런 문제는 좀 예시를 명확히 줬으면 좋겠다. N개의 (시작일자, 종료일자)로 이루어진 블록이 들어오는데 이는 1 ~ 365 사이의 숫자로 이루어져 있다. 이를 열이 365까지 있는 2차원 맵에 1부터 채우는데 블록의 배열은 다음과 같은 규칙을 가진다. 1. 최대한 위쪽부터 채운다. 2. 각기 다른 블록의 시작과 끝이 연속(4,5,6) 이렇게 된다면 무조건 같은 라인(열)에 둔다. 3. 시작일이 같은 경우 긴 것부터 먼저 배열한다. 그리고 우리가 해야 하는 것은 코팅지의 길이를 정하는 것인데, 코팅지는 블록 전체를 감싸는 직사각형으로 만드는 것이다. 근데 이걸 또 최소..

문제 이해 단계 문제는 우리가 익히 아는 스도쿠 규칙과 다를 것이 없다. 9x9 스도쿠가 주어지고 빈칸은 0으로 주어진다. 이러한 입력이 주어졌을 때 빈칸을 채워 스도쿠를 완성시키는 문제이다. 여기서 스도쿠를 완성시킬 수 없는 경우는 존재하지 않는다. 문제 접근 단계 해당 문제에서의 특징은 맵(스도쿠)의 크기가 9x9로 고정되어 있다는 것이다. 그렇기 때문에 완전탐색, 백트래킹 등 다양한 탐색이 가능하다. 그래도 시간제한이 주어졌기 때문에 조건을 둬서 쓸데없는 탐색을 줄이는 편이 나아 보인다. 다른 건 다 제쳐두고 맵의 칸 하나의 관점으로 바라보자. 해당 자리가 비어있어서 숫자 1~9까지 하나를 넣어야 한다. 어떤 절차를 걸쳐서 넣을까? 스도쿠의 규칙에 따라 아래 세 곳에 똑같은 숫자가 있다면, 그 수는..