회전, 달팽이를 더 디테일하게 인덱스로 접근해보자. 이전에 zip 함수를 통한 접근도 괜찮은 방법이지만, 이렇게 인덱스로 접근해서 문제를 푸는 법도 공부하는게 좋다. 정사각형 시계방향 회전 회전하기 전의 인덱스와 회전하기 후의 각각 인덱스 변화를 보고, 규칙을 찾으면 아래와 같다. 아래 코드는 정올 회전(#1229) 문제에 대한 답이다.n = int(input()) maps = [list(map(int,input().split())) for _ in range(n)] while True: a = int(input().rstrip()) if a == 0: break cnt = (a // 90) % 4 for _ in range(cnt): new_maps = [[0]*n for _ in range(n)] f..

*문제 출처는 정올에 있습니다. 문제 제목: 도형회전문제 사이트: https://jungol.co.kr/problem/4731 문제 - JUNGOLhistory 최근 본 문제jungol.co.kr회전 기본기 문제이다. 나의 풀이w,h = map(int,input().split())maps = []for i in range(h): maps.append(list(input().rstrip()))c = int(input())# 시계방향으로 if c == 0: # 90도 회전 answer = list(map(list,zip(*maps[::-1])))elif c == 1: # 180도 회전 answer = [x[::-1] for x in maps[::-1]]elif c == 2: # 270도 회전..

*문제 출처는 정골에 있습니다.  문제 제목: 회전문제 사이트: https://jungol.co.kr/problem/1229 문제 - JUNGOLhistory 최근 본 문제jungol.co.kr나의 풀이 입력받는 각도만큼 90도 회전을 계속 해주면된다. ** 90도 회전: list(map(list,zip(*maps[::-1])))list(map(list,zip(*maps[::-1])))  코드n = int(input())maps = [list(map(int,input().split())) for _ in range(n)]while True: angles = int(input()) if angles == 0 : break for i in range(angles//90): ..

문제 제목: 가방 문제 가방문제(냅색 알고리즘) 최고 17kg의 무게를 저장할 수 있는 가방이 있다. 그리고 각각 3kg, 4kg, 7kg, 8kg, 9kg의 무게를 가진 5종류의 보석이 있다. 이 보석들의 가치는 각각 4, 5, 10, 11, 13이다. 이 보석을 가방에 담는데 17kg를 넘지 않으면서 최대의 가치가 되도록 하려면 어떻게 담아야 할까요? 각 종류별 보석의 개수는 무한이 많다. 한 종류의 보석을 여러 번 가방에 담을 수 있 다는 뜻입니다. 냅색알고리즘 첫 번째 줄은 보석 종류의 개수와 가방에 담을 수 있는 무게의 한계값이 주어진다. 예를 들어 보석 종류의 개수는 4개, 무게의 한계 값은 11이라고 하자 1. 가방에 담을 수 있는 최대 보석의 무게의 한계값 만큼 리스트를 만든다. for 문..

문제 제목: 돌다리 건너기(Bottom-Up) 철수는 학교에 가는데 개울을 만났습니다. 개울은 N개의 돌로 다리를 만들어 놓았습니다. 철 수는 돌 다리를 건널 때 한 번에 한 칸 또는 두 칸씩 건너뛰면서 돌다리를 건널 수 있습니다. 철수가 개울을 건너는 방법은 몇 가지일까요? ▣ 입력설명 첫째 줄은 돌의 개수인 자연수 N(3≤N≤45)이 주어집니다. ▣ 출력설명 첫 번째 줄에 개울을 건너는 방법의 수를 출력합니다. ▣ 입력예제 1 7 ▣ 출력예제 1 34 돌다리를 건널때 한칸 씩 건너뛴다 ** 입력값이 7이라고해서 7을 도착지점으로 출력하면 안된다. 문제에서 함정은 마지막에 도착했을 때까지 구해야하는 것이므로 출력해야하는 값은 8(도착지점)에 대한 출력이다. 나의 풀이 def solution(n): dy..

문제 제목: 계단오르기(Top-Down : 메모이제이션) 철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면 그 방법의 수는 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 로 5가지이다. 그렇다면 총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인가? ▣ 입력설명 첫째 줄은 계단의 개수인 자연수 N(3≤N≤45)이 주어집니다. ▣ 출력설명 첫 번째 줄에 올라가는 방법의 수를 출력합니다. ▣ 입력예제 1 7 ▣ 출력예제 1 21 나의 풀이 (동적 계획법) def solution(n): dy = [0] * (n+1) dy[1] = 1 # 높이 1인 계단을 올라가는 방법 1칸씩 (1가지) dy[2] = 2 # 높이 2인 계단을 올라가는 방법 ..

문제 제목: 동전 교환 (DFS - cut edge) 다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환 해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다. ▣ 입력설명 첫 번째 줄에는 동전의 종류개수 N(1

문제 제목: 중복 순열 구하기 1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열 하는 방법을 모두 출력합니다. ▣ 입력설명 첫 번째 줄에 자연수 N(3

문제 제목: 바둑이 승차(DFS) 철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태 울수가 없다. 철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다. N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요. 기본기 문제에 있는 부분집합 구하기 문제를 참고하였다. 먼저 입력받는 값을 구현함 arr = [0] m, n = map(int,input().split()) for _ in range(n): arr.append(int(input())) 그리고 각각 구한 부분집합들을 저장하기위해 dfs_list 를 선언해주었다. (전역변수로 해서 DFS를 통해 구한 부분집합을 dfs_li..

문제 제목: 합이 같은 부분집합(DFS) N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요. 둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어 합니다. 예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다. ▣ 입력설명 첫 번째 줄에 자연수 N(1 total // 2: return 모범답안 def DFS(L,sum): if sum > total // 2: return..

문제 제목: 부분집합 구하기 (DFS) 자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램 을 작성하세요 기본적으로 부분 집합을 구하는 방법 사용하는 상태와 사용하지 않는 상태가 있는 트리 => 상태트리 ch[v] = 1 # 해당 수를 사용 한다 (부분 집합에 포함한다.) ch[v] = 0 # 해당 수를 사용 하지 않는다 (부분 집합에 포함하지 않는다.) 1 2 3 출력함 모범답안 def DFS(v): if v == n+1: for i in range(1, n+1): if ch[i] == 1: print(i, end= ' ') # 원소만 출력 print() else: ch[v] = 1 DFS(v+1) ch[v] = 0 DFS(v+1) print() if __name..

문제 제목: 이진 트리 순회(깊이 우선 탐색) 개념 전위 순회 방식: 함수 출력시 부모 -> 왼쪽 자식 -> 오른쪽 자식 순서로 출력 중위 순회 방식: 함수 출력시 왼쪽 자식 -> 부모 -> 오른쪽 자식 순서로 출력 후위 순회 방식: 함수 출력시 왼쪽 자식 -> 오른쪽 자식 - >부모 순서로 출력 1. 전위 순회 방식 함수 출력시 부모 -> 왼쪽 자식 -> 오른쪽 자식 순서로 출력 def DFS(v): if v>7: return else: print(v, end=' ') DFS(v*2) DFS(v*2+1) if __name__=="__main__": DFS(1) 2. 중위 순회 방식 함수 출력시 왼쪽 자식 -> 부모 -> 오른쪽 자식 순서로 출력 def DFS(v): if v>7: return else:..