목록문제풀이 (42)
이호진
문제 설명 1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.) 예를 들어 1234 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 가 있다면 가장 큰 정사각형은 1234 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다. 제한사항 표(board)는 2차원 배열로 주어집니다. 표(board)의 행(row)의 크기 : 1,000 이하의 자연수 표(board)의 열(column)의 크기 : 1,000 이하의 자연수 표(boar..
문제 설명 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다. 예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면 array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다. 2에서 나온 배열의 3번째 숫자는 5입니다. 배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 array의 길이는 1 이상 100 이하입니다. a..
문제 설명 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다. 1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다. 2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다. 3. 그렇지 않으면 J를 인쇄합니다. 예를 들어, 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 됩니다. 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 ..
문제 설명 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다. ※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다. 예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다. 경과 시간다리를 지난 트럭다리를 건너는 트럭대기 트럭 0 [] [] [7,4,5,6] 1~2 [] [7] [4,5,6] 3 [7] [4] [5,6] 4 [7] [4,5] [6] ..
문제 설명 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ... 1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작..
문제 설명 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요. 제한사항 numbers는 길이 1 이상 7 이하인 문자열입니다. numbers는 0~9까지 숫자만으로 이루어져 있습니다. "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다. 입출력 예 numbersreturn "17" 3 "011" 2 입출력 예 설명 예제 #1 [1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다. 예제 #2 [0, 1, 1]으로는 소수 [11, 1..
leehojin0719.tistory.com/31 이코테 - 음료수 얼려먹기 - DFS - 2021/03/10 DFS란 깊이 우선 탐색을 말한다. 스택에 넣어 방문처리하고 그래프에서 시작노드를 for문을 이용하여 순서대로 돌린다. -> 재귀함수 이용 음료수 얼려먹기 문제는 001 010 101 이처럼 주어질 때 1을 leehojin0719.tistory.com 여기서 풀었던 음료수 얼려먹기 문제는 상하좌우 검사할 때, dfs(x-1,y) dfs(x,y-1) dfs(x+1,y) dfs(x,y+1) 로 풀었던 문제를 dx와 dy로 풀어봤다. n, m = map(int, input().split()) graph = [] for i in range(n): graph.append(list(map(int, inpu..
DFS란 깊이 우선 탐색을 말한다. 스택에 넣어 방문처리하고 그래프에서 시작노드를 for문을 이용하여 순서대로 돌린다. -> 재귀함수 이용 음료수 얼려먹기 문제는 001 010 101 이처럼 주어질 때 1을 벽이라고 생각하고 0끼리 있는 개수를 세는 문제다. 이 경우에는 3 n, m = map(int, input().split()) graph = [] for i in range(n): graph.append(list(map(int, input()))) n과 m을 맵을 이용하여 입력받고 그래프를 입력받는다. def dfs(x, y): if x = n or y = m: return False if graph[x][y] == 0: graph[x][y] = 1 dfs(x - 1, y) dfs(x, y - 1) ..
BFS란 너비우선탐색을 말한다. 큐에 삽입하고->큐가 빌 때 까지 반복한다 (큐에서 하나 꺼내고 그거의 그래프에서 방문처리가 안됐으면 큐 삽입 후 방문처리) -> 삽입된 큐 때문에 큐가 비지 않고 계속 반복하게 된다. BFS에서는 큐를 사용하기 때문에 from collections import deque를 해주어야 한다. 이 문제에서는 nxm 좌표가 주어지고 1또는 0으로 이루어져 있는데 (1,1)에서 (n,m)까지 미로를 탈출하는 문제이다. 문제에서 길은 1로 벽은0으로 되어있는데 무조건 탈출되게끔 주어진다. from collections import deque n,m=map(int,input().split()) 5 6 graph=[] for i in range(n): graph.append(list(..
이 문제는 볼링공의 무게가 주어졌을 때, 그 볼링공들 중 두 개를 뽑는다. 이 때, 같은 무게는 선택하지 않는다. ex) 1 3 2 3 2 -> 1, 3 / 1, 2 / 1, 3 / 1, 2 / 3, 2/ 3, 2 / 2, 3 / 3, 2 로 총 8가지가 나온다. 생각한 알고리즘은 먼저 정렬을 하고, 이중 for문을 이용하여 비교하는 값이 같지 않을 때, 카운트한다. 이 때, 두 번째 for문에서 범위설정을 for j in range(i+1,len(k))로 하여 이미 더했던 값은 중복하지 않게 더한다. n,m=map(int,input().split()) 8 5 k=list(map(int,input().split())) 1 5 4 3 2 4 5 2 k.sort() count=0 for i in range(..