hw.dev

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 📌 해결순서 처음에는 for i in range(1, max_height) 이렇게 비가 오는 높이를 1부터 시작했는데 런타임 에러가 났다 생각해보니까, 모든 지역의 높이가 1이면 비가 안와야지 안전영역의 갯수가 최대가 되기 때문에 비의 높이를 0부터 시작해야 했다. 1. 0부터 모든 지점중 최대 높이까지만 dfs 탐색을 진행한다. 최대 높이가 9인 경우, 비의 높이가 9라면 모든 지점이 잠기기 때문에 안..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 📌 해결순서 1. 탐색을 시작하기전에 먼저 0일째에 이미 익은 토마토의 좌표를 que에 추가한다 2. 그 다음에, day를 +1 해주는 기준을 어떻게 잡을지 정말 많은 고민을 했는데 ex) 0일째에 익은 토마토의 갯수가 2라면 len(que) = 2 cnt = 0 으로 시작 1개의 토마토에 의해서 익은 토마토의 갯수가 3이면 que에는 추가로 3개의 좌표가 저장 cnt += 1 해..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 📌 해결순서 문제의 범위를 확인하는것이 중요하다!! 수빈이의 위치가 0에서 출발한다면 -1, +1, *2 총 3가지의 경우가 있기 때문에 수빈이가 -1 위치로 이동하기 때문에 문제의 조건에서 벗어나게 된다. 따라서 문제의 범위에 대한 조건을 추가로 만들어 줘야한다 MAX = 10 ** 5 for nx in (x - 1, x + 1, x * 2): if 0

https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 📌 해결순서 "인접한 두 부분수열"의 의미를 이해하는게 가장 중요한 문제였다. 인접한 이라는 말에 집중하지 않고 이런 풀이 과정을 생각했다. 1. 추가하려는 숫자 앞에 같은 숫자가 있으면 더이상 탐색하지 않고 return 2. 길이가 2부터 현재 길이까지의 부분수열을 만들어서 중복되는 부분수열이 있으면 더이상 탐색하지 않고 return 3. 백트래킹으로 완탐.. 이렇게 생각하고 길이에 맞는 부분수열을 백트래킹..

https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 📌 해결순서 1. 백트래킹 dfs 완탐으로 암호를 일단 생성한다 2. 모음 갯수가 자음에 비해서 굉장히 적기 때문에, 모음 알파벳으로만 이루어진 배열을 만든다 3. 암호의 길이가 l 과 같은 경우에, 모음 자음의 갯수가 문제의 조건과 일치 하는지 확인한다 4. 암호의 각 단어가 모음인지 자음인지 판단하고 모음 갯수 >= 1 , 자음 갯수 >= 2 인 경우만 출력한다 📌 코드 import sys inpu..

https://www.acmicpc.net/problem/1405 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 📌 해결순서 '4개의 방향중 임의로 하나를 선택한다' 를 읽고 rand 라이브러리를 빌려와서, 좌표를 이동 할때마다 이동방향을 랜덤으로 설정 해줘야하나...? 이렇게 생각했지만 갈수 있는 모든 방향에 대해서 탐색을 진행해야함을 깨닫고 백트래킹 완탐으로 풀어야 겠다고 생각했다 확률값을 출력해야 하므로, (단순한 경로의 수 / 로봇이 이동할수 있는 전체 경로의 수) 를 출력하면 되겠다고 생각을 한..

https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 📌 해결순서 알파벳을 숫자로 바꾸는 현재시점에서 할수 있는 최선은? 예제의 ACDEB를 숫자로 바꾸면 98753 이 되는데 A를 9로 바꾼 이유는? 숫자의 최댓값을 구하기 위해서 자릿수가 가장 큰 자리에 가장 큰 수를 주면 된다. A의 자릿수는 만의자리 , 10000 이기 때문에 가장 큰 수인 9로 바꾼다 1. 숫자의 자릿수를 저장하는 딕셔너리를 만든다 2. 알파벳이 key, 그 알파벳을 숫..

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 📌 해결순서 모든 부분수열의 합을 구해야 하므로, 완탐으로 구해야함을 알수 있고 더하는 숫자들의 중복이 있으므로 백트래킹으로 하나씩 제거하고 다음 수를 추가해주는 식으로 풀어야한다고 생각했다. 1. 부분수열의 크기가 양수여야 하므로 부분수열을 담는 배열의 길이가 1 이상인 경우에만 합을 구한다 2. 항상 부분수열을 담는 배열에 저장되는 숫자들의 원래 인덱스 값은..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 📌 해결순서 퀸은 현재 위치에서 상하좌우, 4방향 대각선을 칸의 제한없이 이동할 수 있다. 체스판위의 모든 퀸이 서로를 공격할 수 없게 만들기 위해서는 1. 모든 퀸이 서로 같은 열, 행에 위치하면 안됨 2. 하나의 퀸에 대한 모든 4가지 대각선 방향에 퀸이 위치하면 안됨 만약, 모든퀸이 서로를 공격할 수 없게 만든다면 각 행에 하나의 퀸만 존재하기 때문에, row = [0] * n 인 1차원 배열을 생성해서 배..

https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 📌 해결순서 처음에는 각 도시에서 다음 도시로 가는 비용이 가장 싼 경우 + 그 다음도시를 아직 방문하지 않은 경우에 대해서만 탐색을 했는데 틀려서 완탐으로 풀어야 하는 문제겠구나 생각했다 우선, 0번째 도시에서 출발해서 다시 0번째로 돌아오는 순회구조를 트리로 그려보면 이렇다. 0번째 도시에서 출발해서 다시 0번째 도시로 돌아오는 경우는 이렇게 6가지..