본문 바로가기

알고리즘 삽질장

 (228)
[인프런] 안전영역 문제설명 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한 후 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어지는지를 조사하려고 한다. 이 때, 문제를 간단하게 하기 위해, 장마철에 내리는 비의 양에 따라 일저한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다. 이제 위와 같은 지역에 많은 비가 내려서 높이가 4이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을 회색으로 표..
[인프런] 섬나라 아일랜드 문제설명 섬나라 아일랜드의 지도가 격자판의 정보로 주어진다. 각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다이다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하라. 입력조건 첫 줄에 자연수 N(3
[인프런] 단지 번호 붙이기 문제설명 그림1과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌,우 혹은 아래,위로 다른 집이 있는 경우를 말한다. 대각선 상에 집이 있는 경우는 연결된 것이 아니다. 그림 2는 그림1을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성해라. 입력조건 첫 줄에는 지도의 크기 N(5
[인프런] 등산경로 문제설명 등산을 매우 좋아하는 철수는 마을에 있는 뒷산에 등산경로를 만들 계획을 세우고 있다. 마을 뒷산의 형태를 나타낸 지도는 N by N 구역으로 나누어져 있으며, 각 구역에는 높이가 함께 나타나 있다. 만약 N=5 라면, 아래와 같이 표현된다. 어떤 구역에서 다른 구역으로 등산할 때는 그 구역의 위, 아래, 왼쪽, 오른쪽 중 더 높은 구역으로만 이동할 수 있도록 등산로를 설계하려고 한다. 등산로의 출발지는 전체 영역에서 가장 낮은 곳이고, 목적지는 가장 높은 곳이다. 출발지와 목적지는 유일하다. 지도가 주어지면 출발지에서 도착지로 갈 수 있는 등산 경로가 몇 가지 있는지 구하는 프로그램을 작성해라. 입려조건 첫 줄에 N(5
[인프런] 미로탐색 문제설명 7 by 7 격자판 미로를 탈출하는 경로의 총 가지수를 출력하는 프로그램을 작성해라. 출발점은 격자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7) 좌표이다. 격자판의 1은 벽이고, 0은 도로이다. 격자판의 움직임은 상,하,좌,우로만 움직인다. 미로가 다음과 같다면, 위 지도에서 출발점에서 도착점까지 갈 수 있는 방법의 수는 총 8가지이다. 입력조건 7 by 7의 격자판이 주어진다. 출력조건 첫 줄에 경로의 가지수를 출력한다. 사고과정 경로의 총 가지수를 구하는 것이므로 DFS를 활용해야 한다. 처음에 입력 인풋을 잘 못 넣어서 시간을 낭비했다...윾 어쩄건 백 트래킹을 활용해서 잘 구현해주었다! 풀이 arr = [list(map(int, input().split())) for _ in ra..
[인프런] 미로의 최단거리 통로 문제설명 7 by 7 격자판 미로를 탈출하는 최단경로의 경로수를 출력하는 프로그램을 작성해라. 경로수는 출발점에서 도착점까지 가는데 이동한 횟수를 의미한다. 출발점은 격자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7) 좌표이다. 격자판의 1은 벽이고, 0은 도로이다. 격자판의 움직임은 상,하,좌,우로만 움직인다. 미로가 다음과 같다면, 위와 같은 경로가 최단 경로이며, 경로 수는 12이다. 입력조건 7 by 7 격자판의 정보가 주어진다. 출력조건 첫 줄에 최단으로 움직인 칸의 수를 출력한다. 도착할 수 없으면 -1을 출력한다. 사고과정 최솟값을 출력하라고 한 것에서 BFS를 캐치했어야 한다. 전형적인 BFS 문제로, 방문테이블을 새로 정의하여 방문하는 노드를 테이블에 체크해주어야 한다. 도달할 수 ..
[인프런] 사과나무(BFS로 풀기) 문제설명 저번에 구현 유형으로 풀어본 사과나무 문제랑 동일하다. 하지만 BFS로 풀어야 한다. https://techblog-history-younghunjo1.tistory.com/377 [인프런] 사과나무(다이아몬드) 문제설명 위 그림과 같이 N*N처럼 5*5로 사과나무가 존재할 때, 색깔로 칠해진 사과나무에 존재하는 사과들의 개수 합을 구하여라. 사과들의 개수는 한 칸 내에 있는 값을 의미한다. 사고과정 처 techblog-history-younghunjo1.tistory.com 사고과정 문제에서 요구하는 영역을 어떻게 상태트리로 만들어야 할지 도저히 몰랐다. 그래서 강의를 보고 아이디어만 보고 어느정도 구현은 했는데, BFS하는 레벨을 도중에 중간에 멈추는 것을 어떤 방식으로 해야할지에서 또 막..
[인프런] 송아지 찾기 문제설명 현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아지의 위치가 직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다. 현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성해라. 입력조건 첫줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000까지이다. 출력조건 점프의 최소횟수를 구한다. 사고과정 그동안 매번 DFS를 풀다가 이 문제를 풀 때도 자연스레 DFS로 풀려고 했다. 하지만 BFS로 풀어야 햇던 문제이다.. 아직 BFS에 대해서는 많이 ..
[인프런] 알파코드 문제설명 철수와 영희는 서로의 비밀편지를 암호화해서 서로 주고받기로 했다. 그래서 서로 어떻게 암호화를 할 것인지 논의하고 있다. 영희는 알파벳 A를 1로, B는 2로, ..., Z는 26으로 할당해서 번호를 보내기로 하자고 제안한다. 하지만 철수는 이에 반대한다. 왜냐하면 만약 BEAN을 보내서 암호화하면 25114 이다. 그러면 이를 다시 알파벳으로 복원할 때는 많은 방법이 존재한다고 한다. 즉, 25114를 분할하는 여러가지 방법을 생각해보자. 2/5/1/1/4, 2/5/1/14, 2/5/11/4 ,... 등등.. 만약 호화된 코드가 주어지면 그것을 영희가 제안한 방법으로 알파벳으로 복원하는 데 얼마나 많은 방법이 있는지 구하라. 입력조건 첫줄에 숫자로 암호화된 코드가 입력된다. 단, 코드는 0으로..
[인프런] 동전 분배하기 문제설명 N개의 동전을 A, B, C 세명에게 나누어 주려고 한다. 세명에게 동전을 적절히 나누어 주어, 세 명이 받은 각각의 총액을 계산해, 총액이 가장 큰 사람과 가장 작은 사람의 차가 최소가 되도록 하자. 단 세사람의 총액은 서로 달라야 한다. 입력조건 첫줄에는 동전의 개수 N(3
[인프런] 동전 바꿔주기 문제설명 명보네 동네 가게의 현금 출납기에는 k가지 동전이 각각 $n_1, n_2, ..., n_k$개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꾸어 주려고 한다. 이 때, 동전 교환 방법은 여러가지가 있을 수 있다. 예를 들어, 10원, 5원, 1원 동전이 각각 2개, 3개, 5개씩 있을 때, 20원 짜리 지폐를 다음과 같은 4가지 방법으로 교환할 수 있다. 20 = 10원 x 2개 20 = 10원 x 1개 + 5원 x 2개 20 = 10원 x 1개 + 5원 x 1개 + 1원 x 5개 20 = 5원 x 3개 + 1원 x 5개 입력으로 지폐의 금액 T, 동전의 가지수 k, 각 동전 하나의 금액 $p_i$와 개수 $n_i$가 주어질때 지폐를 동전으로 교환하는 방법의 가지 수를 계산해라...
[인프런] 양팔저울 문제설명 무게가 서로 다른 K개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0으로 간주한다. 양팔저울은 한 번만 이용하여 원하는 물의 무게를 그릇에 담고자 한다. 주어진 모든 추 무게의 합을 S라 하자. 예를 들어, 추가 3개이고, 각 추의 무게가 {1, 2, 6}이면, S=9이고, 양팔저울을 한 번만 이용하여 1부터 S사이에 대응되는 모든 무게의 물을 다음과 같이 그릇에 담을 수 있다. X는 그릇에 담는 물의 무게이고, 아래 표의 사각형은 그릇을 나타낸다. 만약 추의 무게가 {1, 5, 7} 이면 S=13이고, 그릇에 담을 수 있는 물의 무게는 {1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13}이고, 1부터 S사이에서 무게에서 9와 10에 대응하는 무게의 물을 담..
[인프런] 퇴사 문제설명 저번에 다이나믹 프로그래밍으로 풀어본 퇴사 문제이다. 이번에 브루트포스(완전탐색)인 DFS를 활용해 해당 문제를 풀어보자. https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 사고과정 스스로 풀 때 상태트리를 만드려고 하는데, 여러갈래 길로 만들었다.. 1일차를 상담할때, 2일차를 상담할때,, 이런식으로..애써 구현은 했는데, 테스트 케이스 일부가 틀려서 구현 실패했다.. 강의를 보니 두 갈래길로 상태트리를 만들어야 했다. 1일차 상담을 했는지 안했는지로, 만약 했다면 1일차 상담 하는 데 걸린 시간 이후의 k일차의 상담으로 이동해서 탐색한다. 만약 1일차 상담하지 않았다면 ..
[인프런] 최대점수 구하기 문제설명 이번 정보올림피아드대회에서 좋은 성적을 내기 위해 현수는 선생님이 주신 N개의 문제를 풀려고 한다. 각 문제를 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 된다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 한다.(해당 문제는 해당 시간이 걸리면 푸는 걸로 간주한다. 한 유형 당 한 개만 풀 수 있다.) 입력조건 첫줄에 문제의 개수 N(1 answer: answer = score - arr[L-1][0] return if time == m: if score > answer: answer = score return if L == n: if time > m: if score - arr[L-1][0] > answer: answer = score - arr[L-1][..
[인프런] 경로 탐색 문제설명 방향그래프가 주엊면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성해라. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 총 6가지이다. 입력조건 첫 줄에는 정점의 수 N(2
[인프런] 수들의 조합 문제설명 N개의 정수가 주어지면 그 숫자들 중 K개를 뽑는 조합의 합이 임의의 정수 M의 배수인 개수는 몇개가 있는지 출력해라. 예를 들어, 5개의 숫자 2 4 5 8 12 가 주어지고, 3개를 뽑은 조합의 합이 6의 배수인 조합을 찾으면, 4+8+12, 2+4+12로 2가지가 있다. 입력조건 첫 줄에 정수의 개수 N(3
[인프런] 조합 구하기 문제설명 1부터 N까지 번호가 적힌 구슬이 있다. 이 중 M개를 뽑는 방법의 수를 출력해라. 입력조건 첫 줄에 자연수 N(3
[인프런] 수열 추측하기 문제설명 가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀있다. 그리고 둘째 줄부터 차례대로 파스칼의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다. 예를 들어, N이 4이고, 가장 윗 줄에 3 1 2 4 가 있다고 할 때, 다음과 같은 삼각형이 그려진다. 3 1 2 4 4 3 6 7 9 16 N과 가장 밑에 있는 숫자가 주어져 있을 때, 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성해라. 단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력해야 한다. 입력조건 첫줄에 두개의 정수 N(1 맨 처음과 끝은 무조건 1이니깐! ch = [0] * (n+1) # 중복허용하지 않으니까 방문체크 테이블 # 이항 계수 n에 맞게 갱신 -> math 라이브러리 사용하지 않고! for i in ..
[인프런] 순열 구하기 문제설명 1부터 N까지 번호가 적힌 구슬이 있다. 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력해라. 입력조건 첫줄에 자연수 N (3
[인프런] 동전교환 문제설명 다음과 같이 여러 단위의 동전들이 주어져있을 때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 하면 될까? 각 단위의 동전은 무한대로 쓸 수 있다. 입력조건 첫 줄에는 동전의 종류개수 N(1

티스토리툴바