IT,프로그래밍/알고리즘

    Python 선택정렬, 삽입정렬 알고리즘

    선택정렬 남아있는 데이터의 전체를 검색하여 가장 작은 데이터를 맨앞으로 보내면 된다. 시간복잡도는 O(N^2)이다. ARRAY = [1, 4, 2, 3, 7, 8, 5, 9, 1, 6] def sort(array): for startIndex in range(len(array)): minIndex = startIndex for i in range(startIndex, len(array)): if array[minIndex] > array[i]: minIndex = i array[minIndex], array[startIndex] = array[startIndex], array[minIndex] return array print(sort(ARRAY)) 삽입정렬 처리되지 않는 데이터를 하나씩 골라 적절한 위..

    파이썬(python) 코테 연습용 파일 읽는방법

    항상 자바 스크립트로만 코딩테스트를 보다가 최근 파이썬으로 언어를 바꿨다. 이유는 1. 자료 및 문제의 총량 차이 2. 문법에서 오는 간결함과 그로인해 얻어지는 시간적이다 이다. 특히나 vscode에서 디버깅을 통해서 변수값을 알수있는것도 마이너하지만 확실한 이득이라고 생각한다. 백준등의 문제에서는 input으로 입력을 받는경우가 많다. 이때, vscode에서 테스트케이스를 테스트할때 터미널에서 매번 타이핑해야하는것이 귀찮았다. 물론, 테스트케이스를 다른데 복사한다음에 ctrl c + v하면 되긴하겠지만 그런 원시적인 방법대신 나는 txt 파일을 읽게 함으로서 테스트케이스를 적용하고 싶었다 import sys sys.stdin = open( '~~~~~/iceMaker.txt', 'r') temp = l..

    프로그래머스[lv.3] [DFS/BFS] - 여행경로

    문제설명 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 모든 공항은 알파벳 대문자 3글자로 이루어집니다. 주어진 공항 수는 3개 이상 10,000개 이하입니다. tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다. 주어진 항공권은 모두 사용해야 합니다. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다. 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다. 입출력 예 tickets return [["ICN",..

    프로그래머스[큐/스택][lv.2] - 기능개발

    문제 설명 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다. 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요. 제한 사항 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다. 작업 진도는 100 미만의 자연수입니다. 작업 속도는 100 이하의 자..

    [자료구조] 큐(Queue)란?

    자료구조에서 스택과 함께 가장 많이 볼수있는 선형구조 입니다. 스택이 한쪽이 막혀있는 프링글스를 생각하신다면, 큐는 놀이동산에서 기다리는 줄을 생각하시면 이해하기가 수월합니다. 혹시 스택에 관하여 개념이 헷갈리시는분은 전에 써놓은 스택에 대한 글을 읽어보시는걸 추천드립니다 https://burning-camp.tistory.com/66 큐는 FIFO(First In First Out) 혹은 LILO(Last In Last Out) 혹은 선입선출이라고 합니다. 즉, 스택이랑 다르게 먼저 들어간게 먼저 나오는 구조입니다. 큐에는 몇가지 대표적인 행동(함수)가 있습니다 Enqueue : 큐의 맨뒤에 data를 넣는다 (대기줄 맨끝에서 기다린다) Dequeue : 큐의 맨앞에 data를 뺴낸다 (대기줄 맨 앞에..

    프로그래머스[lv.2] - 스킬트리(Summer/Winter Coding(~2018))

    문제 설명 선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다. 예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다. 위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다 . 선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요. 제한 조건..

    프로그래머스[lv.1] - 크레인 인형뽑기 (19년도 카카오 겨울 인턴십)

    문제설명 게임개발자인 죠르디는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다. 죠르디는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다. 게임 화면은 1 x 1 크기의 칸들로 이루어진 N x N 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 5 x 5 크기의 예시입니다). 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은 1 x 1 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓이게 되는 데, 이때 바구니의 가장 아..

    [자료구조] 스택(Stack)이란?

    스택이란 자료구조중에서 선형구조에 해당하는 자료구조입니다. 쉽게 생각할수 있는것은 프링글스를 연상하시면 편합니다 위에는 뚫려있고, 위에서 부터 가져올수 있으며 반대로는 뺄수없는 형태를 스택구조 라고합니다 이것을 FILO(First In Last Out) 혹은 LIFO(Last In First Out) 혹은 선입후출 이라고 합니다 스택에는 몇가지 대표적인 행동(함수)가 있습니다 pop : 스택에서 맨위의 data를 꺼낸다 (감자칩을 꺼낸다) push : 스택의 맨위에 data를 넣는다 (감자칩을 넣는다) peek : 스택의 맨위의 data 를 조회한다 (맨위의 감자칩을 살펴본다) 이해를 돕기 위해 아래의 이미지를 보시면 좋습니다! 이러한 스택 개념을 코드로 옮겨서 구현을 할수가 있습니다 class Stac..