알고리즘

    알고리즘/[Python] 알고리즘

    (Python) 버블 정렬(bubble sort)

    (Python) 버블 정렬(bubble sort)¶ 버블 정렬(bubble sort)란? 서로 인접한 두 원소들을 순차적으로 비교하여 정렬하는 알고리즘이다. (인접해 있는 두 원소의 크기가 순서에 맞지 않다면 서로 교환한다.) In [1]: from IPython.display import Image Image("img/bubble_sort.png") Out[1]: 버블 정렬(bubble)의 시간복잡도 비교 횟수 best, average, worst가 모두 일정하다. n-1, n-2, n-3, ... , 2, 1번 비교하므로 총 n(n-1)/2번 비교한다. 교환 횟수 입력 자료가 이미 정렬되어 있는 경우라면, 자료의 이동이 일어나지 않는다. 최악의 경우는 입력 자료가 역순으로 정렬되어 있는 경우이다. 두..

    알고리즘/[Python] 알고리즘

    (Python) 리스트의 선형 탐색(linear search)

    (Python) 리스트의 선형 탐색 (linear search)¶ 정렬되지 않은 리스트에서 특정 항목을 찾으려면 어떻게 해야 할까? 이미 정렬된 리스트라면 이진 탐색(binary search)처럼 좀 더 효과적인 탐색 방법을 사용해 볼 수 있겠지만 그렇지 않다면 순차적으로 배열의 모든 항목을 검사해서 원하는 값이 있는지 찾아야 할 것이다. 선형 탐색(linear search)는 가장 기본적인 탐색 방법으로, 위에서 언급한 바와 같이 배열의 모든 항목을 검사해서 원하는 값이 있는지 찾아내는 선형 탐색 기법이다. In [1]: # 배열(=array)안에 찾고자 하는 특정 항목(=value)이 있으면 그 index값을 return, 없다면 -1을 return def linear_search(value, arr..

    알고리즘/[Python] 백준

    (Python) 백준 2178번 : 미로 탐색

    출처 : https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net (Python) 백준 2178번 : 미로탐색¶출처 : https://www.acmicpc.net/problem/2178 ※ 알고리즘 분류 BFS In [1]: from collections import deque # 입력값 받기 N,M = map(int, input().split()) maze = [list(map(int, input())) for _ in range(N)] 4 6 101111 101010 101011 ..

    알고리즘/[Python] 백준

    (Python) 백준 1094번 : 막대기

    출처 : https://www.acmicpc.net/problem/1094 1094번: 막대기 지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대를 만들려고 한다. 막대를 자르는 가장 쉬운 방법은 절반으로 자르는 것이다. 지민이는 아래와 같은 과정을 거쳐서 막대를 자르려고 한다. 지민이가 가지고 있는 막대의 길이를 모두 더한다. 처음에는 64cm 막대 하나만 가지고 있다. 이때, 합이 X보다 크다면, www.acmicpc.net 알고리즘 분류 수학 시뮬레이션 (Python) 백준 1094번 : 막대기¶출처 : https://www.acmicpc.net/pr..

    알고리즘/[Python] 알고리즘

    (Python) 이진 탐색(Binary Search) 구현하기

    (Python) 이진 탐색(Binary Search)¶ Binary Search : 이진 탐색, 이분 탐색, 또는 이원 탐색 서로 다른 정수들을 원소로 갖고 있는 정렬되어 있는 리스트가 있다고 가정하자. 특정 정수값 searchnum이 리스트에 존재하는지 알고싶다. 만일 searchnum이 리스트에 존재한다면 list[i] = searchnum인 인덱스 i를 반환하고, 그렇지 않다면 -1을 반환한다. 순차적으로 탐색하는 것보다 훨씬 효율적이다 (리스트가 정렬되어 있을 경우에 대해서만) left: 탐색하고자 하는 배열의 왼쪽 right: 탐색하고자 하는 배열의 오른쪽 middle: (left+right)/2 list[middle]과 searchnum을 비교하여 다음의 세가지 경우 중 하나를 선택한다. se..

    (Python) [2020카카오공채] 외벽 점검
    알고리즘/[Python] 프로그래머스

    (Python) [2020카카오공채] 외벽 점검

    출처 : https://programmers.co.kr/learn/courses/30/lessons/60062 코딩테스트 연습 - 외벽 점검 | 프로그래머스 레스토랑을 운영하고 있는 스카피는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하는 도중에 주기적으로 외벽의 상태를 점검해야 할 필요가 있습니다. 레스토랑의 구조는 완전히 동그란 모양이고 외벽의 총 둘레는 n미터이며, 외벽의 몇몇 지점은 추위가 심할 경우 손상될 수도 있는 취약한 지점들이 있습니다. 따라서 내부 공사 도중에도 외벽의 취약 지점들이 손상되지 않 programmers.co.kr 1. 제한사항 1

    (Python) [2020카카오공채] 자물쇠와 열쇠
    알고리즘/[Python] 프로그래머스

    (Python) [2020카카오공채] 자물쇠와 열쇠

    출처 : https://programmers.co.kr/learn/courses/30/lessons/60059?language=python3 코딩테스트 연습 - 자물쇠와 열쇠 | 프로그래머스 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr Hint. 1. 2차원 배열로 이루어진 열쇠를 시계방향으로 90도 회전하려면? 2. 자물쇠와 padding [2020 카카오 공채 문제] 자물쇠와 열쇠¶ In [1]: import copy In [2]: # key를 90도 회전시키기 def rotate(key): rotate_key = copy.deepcopy(key) y = len(key) - 1 for..

    알고리즘/[Python] 백준

    (Python) 백준 2455번 : 지능형 기차

    출처 : https://www.acmicpc.net/problem/2455 2455번: 지능형 기차 최근에 개발된 지능형 기차가 1번역(출발역)부터 4번역(종착역)까지 4개의 정차역이 있는 노선에서 운행되고 있다. 이 기차에는 타거나 내리는 사람 수를 자동으로 인식할 수 있는 장치가 있다. 이 장치를 이용하여 출발역에서 종착역까지 가는 도중 기차 안에 사람이 가장 많을 때의 사람 수를 계산하려고 한다. 단, 이 기차를 이용하는 사람들은 질서 의식이 투철하여, 역에서 기차에 탈 때, 내릴 사람이 모두 내린 후에 기차에 탄다고 가정한다. 내린 사람 수 www.acmicpc.net 알고리즘 분류 : 시뮬레이션 (Python) 백준 2455번 : 지능형 기차¶알고리즘 분류 : 시뮬레이션 출처 : https://..

    알고리즘/[Python] 알고리즘

    (Python) 너비 우선 탐색(BFS) 구현하기

    (Python) 너비 우선 탐색(BFS) 구현하기¶ In [1]: from IPython.display import Image Image("img/bfs_graph.png") ## code안에서 그림이 나오게 할 떄 # ![title](img/bfs_graph.png) ## markdown안에서 그림이 나오게 할 때 Out[1]: DFS에서는 반복문(iteration), 재귀(recursive)적인 방법으로 구현했었는데 BFS의 경우 반복문(iteration)을 이용해서 구현을 해야 한다. 반복문(iteration) DFS : stack 이용 DFS 방문 순서 : A B D E F C G H (왼쪽 노드부터 방문한다고 가정할때) BFS : queue 이용 BFS 방문 순서 : A B C D E G H F..

    알고리즘/[Python] 알고리즘

    (Python) 깊이 우선 탐색(DFS) 구현하기

    깊이 우선 탐색(DFS) 구현하기¶ In [1]: graph = {'A':['B','C'], 'B':['A','D','E'], 'C':['A','G','H'], 'D':['B'], 'E':['B','F'], 'F':['E'], 'G':['C'], 'H':['C']} 반복문(iteration)을 이용해서 DFS 구현하기¶dfs는 stack을 이용해서, bfs는 queue를 이용해서 구현할 수 있는..

티스토리툴바