알고리즘90 Algorithm - 네트워크선 자르기(동적 계획법) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [네트워크선 자르기(동적 계획법)] 현수는 네트워크선을 1m, 2m의 길이를 갖는 선으로 자르려고 한다. 예를 들어, 4m의 네트워크 선이 주어진다면 아래와 같이 5가지의 방법을 생각할 수 있다. 2)와 3)과 4)의 경우는 왼쪽을 기준으로 자르는 위치가 다르기 때문에 다른 경우의 수로 고려한다. 네트워크선의 길이가 N일 때, 1m 혹은 2m의 길이로 네트워크선을 자르는 방법을 구하는 프로그램을 작성하시오. *입력 설명 첫 번째 줄에 네트워크 선의 총 길이인 자연수 N(3 ≤ N ≤ 45)이 주어진다. *출력 설명 첫 번째 줄에 길이가 N인 네트워크선을 자르는 경.. 2022. 1. 31. Algorithm - 퀵 정렬(선수지식) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 선수지식(algorithm) 간단한 예제를 통해 퀵 정렬의 원리를 이해하고자 한다. 예시(Python) 답안 def Qsort(lt, rt): if lt 오른쪽 자식노드) 방식으로 진행된다. 즉, 퀵 정렬이 실행되면 우선적으로 피봇값을 정하고 이를 중심으로 부모노드에서 파티션 작업이 이루어지며 해당 작업이 모두 끝나면 왼쪽 자식노드의 파티션 작업 -> 오른쪽 자식노드의 작업 순으로 전위순회가 이루어진다. 파티션 작업은 피봇(중심축)을 .. 2022. 1. 30. Algorithm - 병합 정렬(선수지식) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 선수지식(algorithm) 간단한 예제를 통해 병합 정렬의 원리를 이해하고자 한다. 예시(Python) 답안 def Dsort(lt, rt): if lt < rt: mid = (lt + rt) // 2 Dsort(lt, mid) Dsort(mid + 1, rt) p1 = lt p2 = mid + 1 tmp = [] while p1 2022. 1. 21. Algorithm - 피자 배달거리(DFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [피자 배달거리(DFS)] N x N 크기의 도시 지도가 있다. 도시지도는 1 x 1 크기의 격자칸으로 이루어져 있으며, 각 격자칸에서 0은 빈칸, 1은 집, 2는 피자집으로 표현된다. 각 격자칸은 좌표(행 번호, 열 번호)로 표현되며, 행 번호는 1번부터 N번까지이고 열 번호도 1부터 N까지이다. 도시에는 각 집마다 "피자 배달거리"가 있는데 각 집의 피자 배달거리는 해당 집과 도시의 존재하는 피자집들과의 거리 중 최소값을 해당 집의 "피자 배달거리"라고 한다. 참고로, 집과 피자집의 피자 배달거리는 " |x1-x2| + |y1-y2| " 이다. 예를 들어, 도.. 2022. 1. 19. Algorithm - 사다리 타기(DFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [사다리 타기(DFS)] 현수와 친구들은 과자를 사먹기 위해 사다리 타기를 한다. 사다리 표현은 2차원 리스트에 0과 1로 채워지며, 0은 평면을 의미하고 1은 사다리를 의미한다. 현수는 특정 도착지점으로 도착하기 위해 몇 번째 열에서 출발해야 하는지를 알고 싶어한다. 여기서 특정 도착지점은 2로 표기된다. 위의 조건을 모두 만족하는 프로그램을 작성하시오. 참고로, 사다리의 지도가 10 * 10이면 아래와 같이 2차원 리스트로 표현된다. 위의 조건들을 고려하여, 특정 도착지점인 2에 도달하려면 7번째 열에서 출발하면 된다. 단, 사다리 타기의 특성 상 네 방향(상.. 2022. 1. 18. Algorithm - 토마토(BFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [토마토(BFS)] 현수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤의 네 방향에 있는 토마토를 의미한다. 참고로, 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며 토마토가 혼자 저절로 익는 .. 2022. 1. 17. 이전 1 2 3 4 5 6 ··· 15 다음
