![]()
문제 https://www.acmicpc.net/problem/16932 16932번: 모양 만들기 N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다. 1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 www.acmicpc.net 문제 풀이 항상 높은 난도의 BFS, DFS를 풀면 알 수 있듯이 최적화에 가장 신경을 써야 한다. 그렇지 않다면 무수히 많은 시간초과를 볼 수 있을 것이다... 문제의 핵심은 빈칸을 선택해서 사각형으로 바꾸고, 가장 길게 연결된 사각형의 크기를 구하는 것이다. 그렇다면 우리는 기존의 배열에서 사각형들을 라벨링 하는 것이 필요하다. 왜 라벨링을 해야하는가에 대해서 작업의 흐름을 판..
![]()
문제 https://school.programmers.co.kr/learn/courses/30/lessons/87377 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 문제를 끝까지 읽어야 한다. 끝까지 읽으면 교점을 구할 수 있는 공식을 친절하게 제공한다. 나는 공식의 존재를 모르고 있다가, 문제를 끝까지 읽고, 친절한 공식을 발견하고 좌절했다.. 참고 사항을 참고하자. 해당 공식을 이용하면 쉽게 교점을 구할 수 있다. 교점을 구하고, 교점의 x와 y좌표를 통해서 최종적으로 그리게 될 그래프의 위아래 끝점을 구해줘야 한다. 그러한 끝점을 구하면..
![]()
문제 https://www.acmicpc.net/problem/15659 15659번: 연산자 끼워넣기 (3) 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제 풀이 정말 까다로운 문제였다. 연산자들의 우선순위를 해결해줘야 했기에, 그 부분에서 사람들이 많이 어려움을 느꼈을 것이라고 생각한다. dfs를 이용해서 모든 경우의 수를 탐색하고, 해당 식의 최솟값과 최댓값을 구한다. 초기 풀이 방식에서는 숫자와 연산자들을 모두 포함하는 배열을 하나 생성했지만, 숫자들은 고정이고, 연산자들의..
![]()
문제 https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 문제 풀이 최적화에 신경 쓰지 않는다면 엄청난 시간초과를 맛볼 수 있는 문제이다. 최대한 경우의 수를 줄여서 최소한의 탐색으로 해결해야 한다. 학생들은 K개의 글자를 배우고, K개의 글자로 이루어진 단어만 읽을 수 있다. 즉 우리는 N개의 단어 중에서 K개의 글자를 골라서 주어진 N개의 단어들 중에서 최대한 많이 읽어야 한다. 문제에서는 친절하게 반드시 배워야 할 글자들을 제시해 준다..
![]()
문제 https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 문제 풀이 전형적인 백트래킹 문제의 예시라고 할 수 있다. 백트래킹에 대해 간단히 얘기하자면 사전적 정의는 되추적 알고리즘이라고 불린다. 결과를 찾는 도중 막히면 다시 되돌아가서 결과를 찾고, 모든 노드를 탐색해서 만드는 DFS와 비슷하다. DFS와 다른 점은 노드를 탐색하기 전에 특정한 조건을 걸고 해당 조건에 부합하지 않는다면 탐색을 진행하지 않는다. 해당 문제에서 특정한 조건이 이제 인접한 두 개의..
![]()
문제 https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 문제 풀이 문제는 정말 간단하다. 주어진 순서에서 최소한의 변경을 통해 오름차순으로 정렬하는 문제이다. 접근방법에 대해서 정말 많은 고민을 했었다. 최소한의 변경을 위해서는 기존 배열에서 최대한 고정시켜야 하는 부분을 길게 해야 한다고 이해했다. 그렇다면 고정시키는 번호를 어떻게 정할까? 문제 보기에서만 봐도 움직이는 번호들은 정해져 있는것을 보면 유추할 수 있다. 3 7 5 2 6 1 4 -> 1..
![]()
문제 https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 풀이 DP의 대표적인 유형이다. DP는 항상 DP 배열이 무엇을 의미하는지 정하는 것이 가장 중요하다. 내가 정한 DP 배열은 다음과 같다. DP[i]는 i일에 벌 수 있는 최대 금액 1일 2일 3일 4일 5일 6일 7일 3 5 1 1 2 4 2 10 20 10 20 15 40 200 문제에서 주어진 예시는 다음과 같다. 우리는 N일까지의 상담을 바탕으로 ..
![]()
문제 https://www.acmicpc.net/problem/1106 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net 문제 풀이 처음에 그리디인 줄 알고 접근했다가, 도저히 그리디로 할 수가 없어서 DP로 접근방식을 수정했다. DP문제에서 가장 중요한 점은 DP 배열을 어떤 식으로 설계하느냐이다. 다양한 방법으로 설계할 수 있지만, 문제에서는 최소한의 비용으로 목표 인원수를 모을 수 있느냐에 초점을 맞추기 때문에 DP배열의 index를 비용으로 잡았다. 그 부분이 나중에 최소 비용을 찾기 편하다고 생각했..
![]()
문제 https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 문제 풀이 문제가 조금 길어서 요약해 보면 다음과 같다. 궁수의 위치는 N행 즉 주어진 배열 한 칸 아래에 있다. 궁수는 3명이고, 한 칸의 한 명만 있다. 궁수의 사정거리는 D이하이고, 여러명의 궁수가 하나의 적을 공격할 수 있다. 궁수는 반드시 가장 가까운 적을 공격해야하고, 가장 가까운 적이 여러 명이라면 가장 왼쪽의 적을 공격한다. 중요한 점은 하나의 적이 여러 명의 궁수에게 공격받을 수 있다는..
