본문 바로가기

Algorithm120

시간복잡도 완전정복(1) 0. 시작에 앞서 요즘 백준을 통해 알고리즘 문제를 열심히 풀고있다. 문제를 작성하면 내 코드가 다른 사람들의 코드보다 10ms 정도 더 걸리는 경우도 있고, 올바른 답은 나오지만 시간초과로 인해서 문제를 틀리는 경우가 있다. 이럴 때 내 코드가 어떤 시간복잡도를 갖고 있는지를 계산한다면, 개선점을 확인할 수 있을 거라고 생각했다. 그래서 이번 포스팅은 시간 복잡도를 계산하는 방법에 대해서 완전 정복을 해보려고 한다. 1. Big - O 표기법 a) 기본 개념 - 입력값에 따른 알고리즘의 사용량을 예측하는 방법이다. - 더 자세한 설명을 원한다면, 아래의 링크를 참고하기를 바란다. https://devraphy.tistory.com/40 Data Structure - 시간 복잡도(Time Complexi.. 2021. 8. 4.
파이썬 배열 - 개념 및 메소드 정리 1. 파이썬의 배열은 리스트다. 파이썬의 배열은 배열이 아니라 리스트이다. 왜 그럴까? 같이 알아보자. a) 파이썬의 배열은 배열의 특징을 갖지 않는다. 컴퓨터 공학의 측면에서 보면 '배열'은 고정된 크기를 갖는다. 그리고 배열의 요소는 모두 동일한 크기를 갖는다는 특징이 있다. 하지만, 파이썬의 배열은 고정된 크기를 갖지 않는다. 이는 '리스트'의 특징이다. b) Dynamic Array 컴퓨터 공학에서 리스트는 index가 아니라 pointer를 사용한다. 포인터는 다음 요소의 값을 가리키는 주소값을 담고 있는 변수다. 이를 메모리 관점에서 보면, 리스트의 요소들은 연속적인 메모리 주소값을 할당받는게 아니라(이는 배열의 특징이다.) 메모리의 여기 저기의 주소값을 할당받아 그 위치에 값이 저장되는 구조.. 2021. 7. 30.
입출력과 사칙연산 메소드 정리 1. 단계별 풀이 https://www.acmicpc.net/step 단계별로 풀어보기 단계별은 @jh05013님이 관리하고 계십니다. 단계제목설명정보총 문제내가 맞은 문제1입출력과 사칙연산입력, 출력과 사칙연산을 연습해 봅시다. Hello World!112if문if문을 사용해 봅시다.53for문for문을 www.acmicpc.net 대기업 코딩테스트를 준비하기 시작한 시점에서 백준의 단계별 풀이를 차근차근 풀어나가려고 합니다. 정말 쉬운 문제푸터 중/고급 정렬문제 까지 단계별로 잘 나뉘어 있습니다. 2. 많이 쓰는 메소드 1. map() - map()은 입력값을 특정 자료형으로 변경하여 받기 위해 사용한다. - 만약 입력값을 정수형으로 받고 싶다면 다음과 같이 사용할 수 있다. userInput = m.. 2021. 7. 26.
오늘의 알고리즘(백준 11004) 1. 백준 11004, K번째 수 https://www.acmicpc.net/problem/11004 11004번: K번째 수 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 요구사항 - 입력값 두개를 받는다. ex) N K - 입력값 N은 입력 받을 숫자의 개수 - 입력값 K는 자리 번호이다. - N개 만큼의 수를 입력받고 이를 오름차순으로 정렬한다. - 그리고 K-1번째 자리에 있는 숫자를 출력한다. index는 0번부터니까 3. 어떻게 풀까? n, k = map(int, input().split()) array = list(map(int, input().split())) arr.. 2021. 7. 23.
오늘의 알고리즘(백준 2751) 1. 백준 2751, 수 정렬하기 2 https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 2. 요구사항 - 첫번째 입력값 N은 몇개의 수가 입력되는 지를 정한다. - N개의 수가 입력되고 나면 이를 오름차순으로 정리해야 한다. 3. 어떻게 풀어야 할까? - int(input())으로 첫번째 입력값 N을 받는다. - map을 이용하여 N개의 input을 배열로 정리한다. - N개의 요소를 갖는 배열을 오름차순으로 정렬한다. - 1개씩 출.. 2021. 7. 23.
오늘의 알고리즘(백준 7490) 1. 백준 7490, 0 만들기 https://www.acmicpc.net/problem/7490 7490번: 0 만들기 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다. www.acmicpc.net 2. 요구사항 - 첫번째 입력값은 테스트 케이스의 개수(N < 10)가 주어진다. ex) 2가 입력된다면, 테스트 케이스가 2개라는 뜻 - 그 다음 N개 만큼 테스트 할 숫자의 범위(3 2021. 7. 22.
오늘의 알고리즘(5월 5일) 1. 백준, Z, 1074번 www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 www.acmicpc.net 2. 생각해보자 a) 문제 이해하기 2의 N승 곱하기 2의 N승 크기의 행렬이 있다. 행렬의 크기와는 상관없이 2 곱하기 2 크기의 배열로 나누어 방문한다. 방문 순서는 Z 모양 순서다. (0, 1, 2, 3 순서로 방문) 입력값은 N, r, c 순서대로 주어진다. 입력값 N에 따라서 행렬의 크기가 정해진다. 입력값 r은 row(행), 입력값 c는 column(열)을 의미한다.. 2021. 5. 5.
오늘의 알고리즘(5월 4일) 1. 백준, 피보나치 수, 2747번 www.acmicpc.net/problem/2747 2747번: 피보나치 수 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 2. 생각해보자 피보나치 수열에 대해 이해한다. 피보나치는 0과 1로 시작한다. 0번째 수는 0, 1번째 수는 1이다. 그 다음, 2번째 수는 앞의 두 수의 합이 된다. 피보나치 수열의 기본 공식을 이용한다. Fn = Fn-1 + Fn-2 (n ≥ 2) 첫번째 입력값 N은 45보다 작거나 같은 자연수다. fibonacci = [0, 1] n .. 2021. 5. 4.
오늘의 알고리즘(4월 29일) 1. 백준, 수 정렬하기3, 10989번 www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 2. 생각해보자 첫 입력값 N은 앞으로 입력될 정수의 개수 N개의 입력값을 array에 입력받는다. 파이썬 기본 정렬 알고리즘을 사용하여 오름차순 정렬 후 한개씩 출력한다. n = int(input()) array = [] for _ in range(n): data = int(input()) array.append(data) array.sort() for data in array: pri.. 2021. 4. 29.

티스토리툴바