본문 바로가기
728x90
반응형

Algorithm & Data Structure

Algorithm & Data Structure 2022. 3. 31. 백준 - 1149번(DP) https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net pypy3 import sys n = int(sys.stdin.readline()) arr = [] for i in range(n): arr.append(list(map(int,sys.stdin.readline().split()))) for i in range(1,len(arr)): arr[i][0] = min(arr[i-1][1],arr[i-1][2]) + arr[i][0]..
Algorithm & Data Structure 2022. 3. 31. 백준 - 1004번(기하) https://www.acmicpc.net/problem/1004 1004번: 어린 왕자 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주 www.acmicpc.net import sys n = int(sys.stdin.readline()) for _ in range(n): tmp = [0,0,0,0] tmp = list(map(int,sys.stdin.readline().split())) s = [tmp[0],tmp[1]] e = [tmp[2],tmp[3]] m = int(sys.stdin.readline()) cnt = 0 for i in ra..
Algorithm & Data Structure 2022. 3. 31. 백준 - 9935번(스택) https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net import sys arr = list(str(sys.stdin.readline().rstrip())) key = list(str(sys.stdin.readline().rstrip())) stack = [] for i in arr: stack.append(i) if i == key[-1] and stack[-len(key):] == key: del stack[-len(key):] i..
Algorithm & Data Structure 2022. 3. 31. 백준 - 2493번(스택) https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net import sys n = int(sys.stdin.readline()) arr = list(map(int,sys.stdin.readline().split())) ans = [0 for _ in range(n)] tmp = [[arr.pop(),len(arr)+1]] #가장 오른쪽에 있는 값, 해당 값이 몇번째 탑인지 while len(arr) > 0: t = arr.pop() if t >= t..
Algorithm & Data Structure 2022. 3. 31. 백준 - 10828번(스택) https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net import sys #sys 모듈 호출 n = int(sys.stdin.readline()) arr = [] for i in range(n): x = sys.stdin.readline().split() #띄어쓰기를 기준으로 입력받음(리스트 형태로 자동 저장) if x[0] == 'push': #x[0]는 첫번째 str arr.append(x[1]) #x[1]는 두번째 str 즉 ..
Algorithm & Data Structure 2022. 3. 31. 백준 - 17608번(스택) https://www.acmicpc.net/problem/17608 17608번: 막대기 아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 www.acmicpc.net import sys #sys 모듈 호출 n = int(sys.stdin.readline()) arr = [0 for _ in range(n)] for i in range(n): arr[i] = int(sys.stdin.readline()) #배열 입력 ans = arr.pop() # 가장오른쪽에 있는 막대기 pop cnt = 1 #가장 오른쪽 막대기는 무조건 보이기때문에 cnt 초기값은 1 while ..
Algorithm & Data Structure 2022. 2. 23. 백준 - 1012번(DFS,BFS 문제지만 완전 탐색으로 품) 바로 전에 풀었던 백준 2067번과 90% 유사한 문제다. 다른 점이 있다면 여기서는 입력받은 좌표값을 1로 치환해주고 전체 리스트를 0 을로 감싼 다음에 십자가 모양으로 전체 탐색을 한다. import sys sys.setrecursionlimit(10000) t = int(sys.stdin.readline()) def count(arr,i,j,tmp): arr[i][j] = '0' tmp.append(i) tmp.append(j) if arr[i + 1][j] == '1': if i + 1 >= 0 and j >= 0: count(arr, i + 1, j, tmp) if arr[i - 1][j] == '1': if i - 1 >= 0 and j >= 0: count(arr, i - 1, j, tmp)..
Algorithm & Data Structure 2022. 2. 23. 백준 - 2667번(DFS,BFS 문제지만 완전탐색으로 품) DFS BFS 문제지만 해당 방법으로 어떻게 접근하는지 감이 잘 안 잡혀서 떠오르는 방식으로 주먹구구식으로 풀어봤다. 사실 DFS 와 BFS도 재귀(Recursion)의 일종이다. 따라서 재귀 함수를 이용해서 십자가 모양으로 탐색하는 것으로 진행했다. 탐색한 애들은 모두 0으로 바꿔준다. 이를 반복해서 재귀가 끝나면 새로운 tmp배열을 만드는 것으로 단지 구분이 가능하다. 다만 여기서 문제점이 발생한다. 만약 이차원 리스트 안에서 arr[0,0]을 십자가 모양으로 탐색을 하게 되면 arr [-1,0]과 arr [0,-1]도 탐색을 하게 된다. 처음에는 try except를 이용하려 했지만 이는 바람직한 방법이 아니다. 따라서 단지 전체를 0으로 감싸줬다. 주어진 미로 예시는 아래와 같다. 0110100 ..
Algorithm & Data Structure 2022. 2. 22. 백준 - 1260번(DFS,BFS) DFS와 BFS는 해당 블로그에서도 한번 정리한 적 있고 이 문제도 아이디어를 떠올린 후 기본 구현법만 알면 쉽게 풀 수 있다. 핵심 아이디어는 입력받는 그래프의 구조를 재배열 는 것이다. 에를 들어 [1,2], [1,3], [1,4], [2,4], [3,4] 이렇게 전달을 받았다고 가정한다. 이를 다시 정리해서 첫번째 배열 자리에는 2,3 // 두 번째 배열 자리에는 1,4 이런 식으로 n번째 원소의 자리가 연관되어 있는 숫자들이 오도록 재배치해서 정렬해주는 것이다. 또한 문제 조건에서 작은 수 먼저 탐색하는 조건을 붙여줬으니 오름 차순으로 정렬한다. 전체 코드는 아래와 같다. import sys from collections import deque n, m, v = map(int,sys.stdin.r..
728x90
반응형

티스토리툴바