목록파이썬/알고리즘 (52)
차밍이
목차 1. 삽입 정렬 방식 두 번째 인덱스에서부터 시작하여 데이터를 확인한다. 앞에 있는 데이터들과 하나씩 비교하면서 자신의 자리를 찾아나간다. 가장 작은 값이면 맨 앞까지 계속 이동한다. 혹은 자기보다 작은 데이터가 앞에 있으면 그 뒤쪽으로 데이터를 삽입한다. 2. 소스 코드 import random data_list = random.sample(range(100), 10) print(data_list) >>> [24, 62, 17, 81, 74, 55, 92, 93, 82, 53] 랜덤으로 정렬하기 위한 숫자 데이터 리스트를 생성한다. for i in range(1, len(data_list)): for j in range(i-1,-1,-1): if data_list[j] > data_list[j+1..
목차 다양한 링크드 리스트 구조 1. 더블 링크드 리스트 (Doubly linked list) 더블 링크드 리스트 기본 구조 이중 연결 리스트라고도 함 단방향 링크드리스트인 경우 가장 끝 노드를 찾기 위해서는 처음부터 끝까지 모든 노드를 지나서 검색해야하는 한계가 있다. 데이터가 뒷쪽에 더 가깝다는 것을 안다면 뒤에서부터 검색하면 더 빠르게 접근할 수 있다. 장점 : 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능 단점 : 앞쪽 주소와 뒷쪽 주소를 모두 저장해야함. 저장 효율이 낮아진다. ![](https://www.fun-coding.org/00_Images/doublelinkedlist.png) (출처: wikipedia, https://en.wikipedia.org/wiki/Linked\..
목차 대표적인 데이터 구조: 링크드 리스트 (Linked List) 1. 링크드 리스트 (Linked List) 구조 연결 리스트라고도 함 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조 본래 C언어에서는 주요한 데이터 구조이지만, 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원 링크드 리스트 기본 구조와 용어 노드(Node): 데이터 저장 단위 (데이터 값, 포인터)로 구성 포인터(pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간 배열의 단점 배열의 경우 미리 데이터의 길이를 선언해야한다. 선언한 길이만큼 공간을 미리 차지하고 있다. 데이터가 인덱스에 따..
목차 꼭 알아둬야 할 자료 구조: 스택 (Stack) 데이터를 제한적으로 접근할 수 있는 구조 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조 큐: FIFO 정책 스택: LIFO 정책 1. 스택 구조 스택은 LIFO(Last In, Fisrt Out) 또는 FILO(First In, Last Out) 데이터 관리 방식을 따름 LIFO: 마지막에 넣은 데이터를 가장 먼저 추출하는 데이터 관리 정책 FILO: 처음에 넣은 데이터를 가장 마지막에 추출하는 데이터 관리 정책 대표적인 스택의 활용 컴퓨터 내부의 프로세스 구조의 함수 동작 방식 주요 기능 push(): 데이터를 스택에 넣기 pop(): 데이터를 스택에서 꺼내기 Visualgo 사이트에서..
목차 자료구조란? 자료의 구조, 데이터의 구조 대량의 데이터를 효율적으로 관리할 수 있는 데이터의 구조를 의미한다. 코드상으로 얼마나 효율적으로 데이터를 처리하기위해 구조적으로작성하는가를 논하는 것 알고리즘이란? 어떤 문제를 풀기 위한 절차나 방법 자료구조와 알고리즘이 중요한 이유? 어떤 자료구조와 알고리즘을 쓰냐에 따라, 성능이 매우 크게 차이가 발생된다. 프로그래밍을 잘 할 수 있는 기술과 역량을 검증하는 척도로 사용된다. 배열 배열의 장점 데이터의 시작점만 알면 내부의 데이터들의 순서를 바로 알 수 있다. 순차적인 데이터를 손쉽게 다룰 수 있다. 빠르게 데이터에 접근 가능하다. 배열의 단점 데이터가 가변적인 경우 추가나 삭제가 쉽지 않음 최대 길이를 미리 지정해야함 큐 (Queue) 큐의 구조 FI..
The candy war 문제 알고리즘 유치원 선생님인 영희는 간식시간이 되자 아이들에게 사탕을 나누어 주려고 하였다. 하지만 욕심 많고 제멋대로인 유치원 아이들은 차례대로 받으라는 선생님의 말을 무시한 채 마구잡이로 사탕을 집어 갔고 많은 사탕을 집어 간 아이가 있는가 하면 사탕을 거의 차지하지 못하고 우는 아이도 있었다. 말로 타일러도 아이들이 말을 듣지 않자 영희는 한 가지 놀이를 제안했다. 일단 모든 아이들이 원으로 둘러앉는다. 그리고 모든 아이들은 동시에 자기가 가지고 있는 사탕의 절반을 오른쪽 아이에게 준다. 만약 이 결과 홀수개의 사탕을 가지게 된 아이가 있을 경우 선생님이 한 개를 보충해 짝수로 만들어 주기로 했다. 흥미로워 보이는 이 놀이에 아이들은 참여했고 이 과정을 몇 번 거치자 자연..
걸그룹 마스터 준석이 문제 정우는 소문난 걸그룹 덕후이다. 정우의 친구 준석이도 걸그룹을 좋아하지만 이름을 잘 외우지 못한다는 문제가 있었다. 정우는 친구를 위해 걸그룹 개인과 팀의 이름을 검색하여 외우게 하는 퀴즈 프로그램을 만들고자 한다. 입력 첫 번째 줄에는 총 입력받을 걸그룹의 수 N(0 < N < 100)과 맞혀야 할 문제의 수 M(0 < M < 100)을 입력받는다. 두 번째 줄부터는 각 걸그룹마다 팀의 이름, 걸그룹의 인원수, 멤버의 이름을 한 줄씩 차례대로 입력받는다. 팀과 멤버의 이름은 최대 100글자이며, 모든 글자는 알파벳 소문자이다. 하나의 걸그룹이나 서로 다른 두 걸그룹에 이름이 같은 두 멤버가 있는 경우는 없다. 그다음 줄부터는 M개의 퀴즈를 입력받는다. 각각의 퀴즈는 두 줄로 ..
연구소 문제 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1 ×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다. 예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 ..
이름궁합 테스트 문제 시윤이는 좋아하는 이성이 생기면 가장 먼저 이름궁합부터 본다. 이름궁합을 보는 방법은 간단하다. 먼저 이름을 알파벳 대문자로 적는다. 각 알파벳 대문자에는 다음과 같이 알파벳을 적는데 필요한 획수가 주어진다. 예를 들어, 두 사람의 이름인 LEESIYUN, MIYAWAKISAKURA 를 같이 표현했을 때 다음과 같이 먼저 주어진 이름부터 한 글자씩 적는다. 두 사람의 이름을 알파벳 대문자로 표현한 뒤, 한 글자씩 번갈아가며 적는다. 예시 : L M E I E Y S A I W Y A U K N I S A K U R A 예시처럼 이름이 남을 경우엔 뒤에 남은 글자인 S A K U R A를 맨 뒤에 적는다. 그러고 나서 알파벳을 대응하는 숫자로 바꾸고 각 숫자와 그 숫자의 오른쪽 숫자와..
미로 탐색 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 192 MB 63743 23204 14792 35.340% 문제 N×M크기의 배열로 표현되는 미로가 있다. 1 0 1 1 1 1 1 0 1 0 1 1 1 0 1 0 1 1 1 1 1 0 1 1 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다. 입력 첫째 줄에 두 ..