Gaegul's devlog

문제 N과 시작 숫자 S가 주어지면 숫자 피라미드를 만드는 프로그램을 작성하시오. 예를 들어, N이 5이고 S가 3 이라면, 그 숫자 피라미드는 다음과 같다. 3 456 21987 3456789 987654321 시작 숫자 S는 꼭대기부터 1씩 증가한다. 시작 행의 번호가 1번이라고 했을때, 짝수번째 행은 왼쪽에서 오른쪽으로 1씩 증가하도록 적고, 홀수번째 행은 거꾸로 적는다. 숫자가 만약 10이 될 경우, 1로 바꾸고 다시 증가한다. 입력 입력의 첫 번째 줄에 N과 시작 숫자 S가 주어진다. ( 1≤N≤100, 1 ≤S≤ 9) 출력 첫 번째 줄부터 숫자 피라미드를 출력한다. (각 줄에 존재하는 공백의 개수와 숫자의 개수를 정확하게 확인해주시바랍니다.) 입력예제 5 3 출력예제 3 456 21987 34..

1) 트리 (Tree) 란? 트리는 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조 2) 이진 탐색 트리 (Binary Search Tree) 란? 이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조의 일종. 이진 탐색 트리의 특징 : 왼쪽 < 부모 < 오른쪽 부모 노드보다 왼쪽 자식 노드가 작습니다. 부모 노드보다 오른쪽 자식 노드가 큽니다. 3) 트리의 순회 (Tree Traversal) 트리 자료구조에 포함된 노드를 특정한 방법으로 한 번씩 방문하는 방법. 트리 순회 방법 종류 전위 순회 (pre-order traverse) : root - left -right 중위 순회 (in-order traverse) : left - root - right 후위 순회 (po..

최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미. 1. 다양한 문제 상황 1) 한 지점에서 다른 한 지점까지의 최단경로 2) 한 지점에서 다른 모든 지점까지의 최단경로 3) 모든 지점에서 다른 모든 지점까지의 최단경로 - 각 지점은 그래프에서 노드로 표현. - 지점 간 연결된 도로는 그래프에서 간선으로 표현. 2. 알고리즘 동작 과정 1. 출발 노드를 설정. 2. 최단거리 테이블을 초기화. 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 (weight)를 선택. 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신합니다. But! 총 O(V)번에 걸쳐서 최단거리가 가장 짧은 노드를 매법 선형 탐색해야 한다. 따라서 전체 시간 복잡도는 O(V2) 이다...

문제 얼마전에 큰맘 먹고 새로운 절단기를 구입한 목수 윤성이는 나무 M미터가 필요하다. 절단기는 다음과 같이 동작한다. 먼저, 윤성이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 윤성이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다) 목수 윤성이는 과유불급을 좌우명으로 삼고 있..

문제 n개의 오름차순으로 정렬된 숫자가 주어지고, 그 후 q개의 질문이 주어진다. 각각의 질문은 특정 숫자가 n개의 숫자 내에 존재하는지를 판별하는 것이다. 모든 q개의 질문에 대하여 답을 하는 프로그램을 작성하시오. 입력 첫 번째 줄에 숫자의 개수 n, 그리고 질문의 개수 q가 주어진다 ( 1 ≤ n ≤ 100,000, 1 ≤ q ≤ 100,000) 이는 오름차순으로 정렬되어 주어진다. 두 번째 줄에 n개의 숫자가 주어진다. 세 번째 줄에 q개의 질문이 주어진다. 각 수는 21억보다 작은 정수다. 출력 각 질문에 대하여 숫자가 존재하면 YES, 아니면 NO를 한 줄에 하나씩 출력한다. CODE import sys n , q = map(int, input().split(" ")) nums = list(m..

문제 임의의 자연수는 그보다 작은 자연수들의 합으로 표현될 수 있다. 예를 들어 4의 경우, 4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1 위와 같은 방법으로 표현 될 수 있다. 이 때 , 숫자의 구성이 같으면서 그 순서만이 다른 경우는 같은 경우로 생각하는데, 예를 들어 다음 세 가지 경우는 모두 같은 경우이다. 2 + 1 + 1, 1 + 2 + 1 , 1 + 1 + 2 자연수 n을 입력 받아 이를 n보다 작은 자연수들의 합으로 나타내는 방법을 모두 출력하는 프로그램을 재귀 호출을 사용하여 작성하시오. 입력 첫 줄에 2 이상 20 이하의 자연수 n이 주어진다. 출력 첫째 줄부터 모든 방법을 한 줄에 하나씩 출력한다. 하나의 식 안에는 큰 숫자가 앞으로 오도록 하고, 전체적으로는 앞의 숫자가 ..

본 문제는 중복 수열 문제이다. 문제 서로 다른 n개의 원소들 중에서 r개만을 뽑아 일렬로 나열하는 것을 순열이라 한다. 예를 들어, 3개의 원소 a, b, c 중에서 2개만을 뽑아 나열하면 ab, ac, ba, bc, ca, cb 의 6가지 경우가 있다. n과 r이 주어질 때, n개의 소문자 중에서 r개만을 뽑아 나열하는 모든 경우를 출력하는 프로그램을 작성하시오. 단, a부터 시작하여 연속으로 n개의 알파벳을 갖고 있다고 하자. 입력 첫 번째 줄에 n과 r이 주어진다. ( 1 ≤ n ≤ 10, 0 ≤ r ≤ min(n, 7) ) 출력 각 줄에 n개의 소문자 중에서 r개만을 뽑아 나열하는 경우를 사전순으로 나열한 결과를 출력한다. 예제 입력 4 2 예제 출력 ab ac ad ba bc bd ca cb ..

1) 입력 / 출력 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 2) 입력 / 출력 3 1 0 0 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 ..

[완전 탐색 대표문제] 이번 문제는 색종이들의 넓이를 구하는 문제이다. (겹치는 부분을 처리하는 것이 관건인 문제!!) 입력 : 2 0 0 10 10 2 2 6 6 출력 : 64 36 ## template n = int(input()) input_list = [list(map(int, input().split(" "))) for _ in range(n)] arr = [[0] * (101) for _ in range(101)] for i in range(n): start_x = input_list[i][0] start_y = input_list[i][1] width = input_list[i][2] #가로 height = input_list[i][3] # 세로 for j in range(start_x, s..

탐색 알고리즘에는 크게 1. 이진 탐색 2. BFS 3. DFS가 있다. 이번 챕터에서는 이진 탐색에 관해 알아볼 것다. 이진 탐색 순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서 부터 차근히 확인하는 방법. 이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법. 재귀문 구현 def binary_search(array, target, start, end): if start > end: return None mid = (start + end) // 2 #찾은 경우 중간점 인덱스 반환 if array[mid] == target: return mid elif array[mid] > target: return binary_search(array, target,..