hong_mok

버블 정렬(Bubble Sort) - 시간 복잡도 : O(n^2) - 인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식이다. 알고리즘 - 첫 번째 인덱스 요소부터 인접한 원소랑 비교하여 자료를 바꾸면서 마지막 인덱스 요소 까지 반복한다. - 한 단계가 끝날 시 가장 큰 원소가 마지막에 정렬된다. - 정렬된 부분을 제외하고 나머지 부분에 대하여 정렬을 반복한다. 정렬과정을 그림으로 나타내면 다음과 같다. 코드 def bubble_sort(arr): # 버블 정렬(오름차순) n = len(arr) # 배열의 길이 저장 # 한 스텝마다 정렬된 자료가 뒤부터 쌓이므로 # 정렬범위 n-1부터 0까지 1씩 줄여주기 for i in range(n-1, 0, -1): for j in range(i): # 인접..

백트래킹(Backtracking) 이란? 비선형 구조의 자료를 탐색할 때 깊이 우선 탐색(DFS) 방식으로 경로를 따라가다가, 조건을 확인하였을 때 그 경로가 해결책으로 이어질 것 같지 않다면 더이상 그 경로를 따라가지 않음으로써 시도의 횟수를 줄이는 방식이다. 이를 가지치기(Prunning) 라고 한다. 깊이 우선 탐색(DFS) 방식과 유사하지만 DFS는 가능한 모든 경로를 추적하는데 비해서 백트래킹은 가지치키를 통해 불필요한 경로를 차단한다. 일반적으로는 경우의 수가 줄어들지만 최악의 경우에는 여전히 많은 탐색을 요하므로 처리가 불가능하다. 절차 트리의 깊이 우선 탐색을 실시한다. 조건을 확인하여 각 노드가 유망한지(Promising) 점검한다. 노드가 유망하지 않다면, 그 노드의 부모 노드로 돌아가..

https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net 문제 세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다. 문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다. 모든 왼쪽 소괄호("(")는 오른쪽 소괄호..

스택(Stack) - 스택이란 물건을 쌓아 올린 것 처럼 자료를 쌓아 올린 형태의 자료구조 이다. - 스택에 저장된 자료는 자료간의 관계가 1대1의 관계를 갖는 선형 구조이다. (반대의 경우는 1대N 구조인 트리가 있다.) - 가장 마지막에 들어간 자료가, 가장 처음에 나온다. (후입선출 LIFO(Last-in-First-out)) - 위와 같은 특징 떄문에, 가장 위에서만 데이터의 삽입 & 삭제가 일어난다. 프링글스 통을 생각하면 된다. 스택의 데이터 구조 - top : 스택의 가장 위에 있는 위치를 저장하고 있는 데이터 - size : 스택의 크기를 저장하고 있는 데이터 - items : 스택에 담길 데이터를 저장할 데이터 구조 스택의 연산 - CreateStack : 스택을 생성하는 연산. size..

이진 검색(Binary Search) 자료의 가운데 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법이다. 원하는 값을 찾을 때 까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가며 검색한다. 이때, 이진 검색을 하기 위해서는 자료가 정렬된 상태여야 한다. 알고리즘 - 자료의 중앙에 있는 원소를 고른다. - 중앙 원소의 값과 찾고자 하는 목표 값을 비교한다. - 목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해서 새로 검색을 수행한다. - 찾고자 하는 값을 찾을 때 까지 위의 과정을 반복한다. 위의 알고리즘을 그림으로 나타내면 다음과 같다. 파이썬 코드 def binary_sear..

그리드 시스템(Grid system) - 요소들의 디자인과 배치에 도움을 주는 시스템 - 기본 요소 Column : 실제 컨텐츠를 포함하는 부분 Gutter : 칼럼과 칼럼 사이의 공간 (사이 간격) Container : Column들을 담고 있는 공간 Bootstrap Grid System Bootstrap Grid 공식 문서 Bootstrap 을 이용하면 Gird System을 쉽게 구현할 수 있다. (Bootstrap CDN) Bootstrap Grid System은 flexbox로 제작된다. Container, Row, Column을 사용하여 컨텐츠를 배치하고 정렬한다. 하나의 Row당 Column은 12개로 배치 된다. 또한 6개의 grid breakpoints를 활용하여 화면 너비에 따라 다른..

2108번: 통계학 문제 수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자. 1. 산술평균 : N개의 수들의 합을 N으로 나눈 값 2. 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값 3. 최빈값 : N개의 수들 중 가장 많이 나타나는 값 4. 범위 : N개의 수들 중 최댓값과 최솟값의 차이 N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. 5 1 3 ..

딕셔너리 정렬하기 파이썬 내장 함수인 sorted와 lambda 를 사용하여 딕셔너리를 정렬할 수 있다. 이때, dict.items() 함수를 사용하여 인자로 전달해준다. key로 정렬하기 sorted 함수 인자로 key=lambda x : x[0] 을 전달한다. dict1 = {'a': 1, 'd': 2, 'c': 4, 'b': 3} sorted_dict = dict(sorted(dict1.items(), key=lambda x : x[0])) print(sorted_dict) {'a': 1, 'b': 4, 'c': 3, 'd': 2}Value로 정렬하기 sorted 함수 인자로 key=l..

합병 정렬(Merge Sort) - 시간 복잡도 : O(n log n) - 분할 정복 알고리즘 이다. 알고리즘 - 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는 - 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. - 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. - 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병(merge) 한다. - 복사(copy) : 임시 배열에 저장된 결과를 원래 배열에 복사한다. 과정 합병 정렬 과정을 그림으로 나타내면 다음과 같다. - 상단의 붉은색 부분은 정렬되지 않은 리스트들을 나누는 분할(devide) 과정이다. 길이가 1이..

CSS Flexible Box Layout Flexbox란 아이템 간 공간 배분과 정렬 기능을 제공하기 위한 행과 열 형태로 아이템을 배치하는 1차원 레이아웃 모델입니다. 가장 큰 특징은 main axis(주축) 과 cross axis(교차 축) 이 존재하고, 이 두개의 축을 기준으로 아이템을 배치하고 정렬할 수 있습니다. Flexbox 구성요소 Flex Container (부모 요소) - Flexbox 레이아웃을 형성하는 가장 기본적인 모델. - Flex Item들이 놓여있는 영역 - display 속성을 flex 또는 inline-flex로 지정. .flex-container { display: flex; }Flex Item (자식 요소) - Container에 속해 있는 컨텐츠(박스) Main Ax..