본문 바로가기

분류 전체보기142

[Linked Lists]1. 단일 연결 리스트 - 1 목차 1. ADT(Abstract data type) 2. Array vs Linked list 3. Singly Linked List 1. ADT란? ADT는 Abstract data type의 약자로서, 추상적인 자료형을 의미합니다. 이는 특정 자료형이 1. 어떤 데이터를 사용(저장)? 2. (저장하는 데이터로) 어떤 기능? 3. 성능 분석 위 3가지를 분석하는 자료형을 뜻합니다. ADT의 종류에는 여러가지가 있으며, 우선 Array 와 Linked List에 대해서 알아보도록 하겠습니다. 2. Array vs Linked List? 어떤 연속된 데이터를 저장한다고 하였을 시, 흔히 사용하는 방식으로 Array(배열)과 Linked List(연결 리스트)가 있습니다. 두 방법 모두 연속된 데이터를 저.. 2021. 2. 18.
자료구조 정리 이 카데고리에서는 코딩테스트의 필수 덕목인 자료구조에 대해 정리해 보도록 하겠습니다. 코딩테스트 준비를 하면 할 수록 시간 복잡도 설계에 따라 문제를 해결할 수 있는 능력이 많이 달라진다는 것을 깨달았으며, 이를 처음부터 정리해보도록 하겠습니다. 2021. 2. 18.
[백준]1436. 영화감독 숌 문제풀이 (파이썬, python) www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 위 문제가 요구하는 점을 요약해보면, 1. 666이 들어가는 수를 순서대로 나열한다. 2. 숫자 N를 입력받고, N번째 666이 들어가는 수를 출력하라. ex) 수 순서는 666, 1666, 2666, 3666, 4666, 5666, 6660, 6661, ... 1. 문제 해결 방법 필자는 우선 경우의 수를 나누어 문제를 해결하고자 하였다. 우선 뒤에 세자리를 제외시킨 후, 앞에 붙는 숫자가 1. 뒤 세자리가.. 2021. 2. 17.
[백준]7568. 덩치 문제풀이 (파이썬, python) www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 위 문제는 사람의 키와 몸무게에 따라서 사람들의 덩치를 순위로 나누고자 하는 문제이다. 이 문제의 요점을 정리해보면, 1. 첫 줄에는 전체 사람수 N, 둘째 줄 부터는 N번 만큼 그 사람의 몸무게와 키를 공백을 하나 둔 채 입력 받는다. 2. 어떤 한 사람이 다른 사람보다 몸무게, 키가 모두 클 시 덩치가 크다고 판단한다. 3. 이가 성립되지 않는다면, 두 사람은 덩치가 같은 것으로 인식된다. 4... 2021. 2. 17.
[백준]11729. 하노이 탑 이동 순서 문제풀이 (파이썬, python) www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 위 문제는 문제의 제목과 같이, 하노이 탑의 이동 순서를 표현하는 문제이다. 우선 기본적인 하노이 탑의 규칙은 다음과 같다. 1. 세개의 막대가 있고, 첫 번째 막대에는 반지름이 각자 다른 N개의 원판이 있다. 2. 원판은 반지름의 크기가 큰 순서로 이루어져 있다. 3-1. 이때, 한 번에 한개의 원판만 이동 할 수 있다. 3-2. 쌓인 원판은 위의 것이 항상 아랫 것보다 작아야 한다. 4. 이 두.. 2021. 2. 14.
[백준]2447. 별 찍기 - 10 문제풀이 (파이썬, python) www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 위 문제는 재귀적인 패턴으로 별을 찍어보는 문제이다. 문제의 특징을 정리해보자면, 1. 3의 거듭제곱의 수가 입력된다 (이때 지수는 1 2021. 2. 14.
백준 문제풀이 정리 항목 이 게시판에는 백준에서 문제풀이를 하면서, 오답 풀이 혹은 필자가 햇갈렸던 문제, 중요하게 기억해야 할 것 같은 문제들을 서술하도록 하겠습니다. 2021. 2. 14.
20. 소수 판별, 에라토스테네스의 체 코드로 소수를 판별할 수 있는 방법은 다양합니다. 그 중에서 효과적인 방법인 에라토스테네스의 체에 대하여 설명하겠습니다. 에라토스테네스의 체로 N까지의 소수를 확인하는 방법은 다음과 같습니다. 1. 2 ~ N까지의 모든 자연수를 나열한다. 2. 남은 수중 아직 처리하지 않는 수 i를 고른다. 3. i의 배수를 모두 제거한다. 4. 2, 3번 과정을 반복한다. 여기서 i는 N의 제곱근 수 까지만 구해도, 소수 리스트를 만들 수 있습니다. 따라서 이를 파이썬 코드로 표현해 보자면 n = int(input()) # n 이하의 자연수 에서 소수 찾기 num = [True for i in range(n + 1)] # 소수 판단 bool list for i in range(2, int(n**0.5) + 1): # .. 2021. 1. 29.

티스토리툴바