본문 바로가기

알고리즘 공부16

오늘의 알고리즘(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.
오늘의 알고리즘(4월 28일) 1. 백준, 좌표 정렬하기, 11650 www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 2. 생각해보자 a) 문제 이해 첫번째 입력값 N은 앞으로 입력될 좌표의 개수를 의미한다. 주어진 좌표의 x와 y 값을 기준으로 오름차순 정렬을 한다. b) 어떻게 풀까? 데이터를 튜플 형식으로 입력받는다. x값을 비교하여 정리하는데, x값이 동일한 경우 y값을 비교하는 조건문을 만든다. 3. 코드 해설 및 분석 파이썬.. 2021. 4. 28.
오늘의 알고리즘(4월 19일) 1. 백준, 나이순 정렬, 10814번 www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 2. 생각해보자 a) 기본조건 첫 입력값 N은 주어질 데이터의 개수 N개의 나이와 이름을 한 쌍으로 하는 데이터가 주어진다 나이를 기준으로 오름차순 정렬시킨다. 나이가 같으면 가입한 순서로 정렬시킨다. b) 이렇게 풀면 될까? 튜플을 이용하여 데이터의 짝을 형성시킨다. 나이를 기준으로 정렬한다. 나이가 같은 경우, 입력된 순서를 기준으로 정렬한다. 3. 해설 및 코드분석 n =.. 2021. 4. 19.
오늘의 알고리즘(4월 16일) 1. 백준, 소트인사이드, 1427번 www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하고자하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 2. 생각해보자 숫자를 문자열로 입력받는다. 입력받은 문자열을 for문을 사용하여 문자 단위로 나눈다. 나눠진 문자를 리스트에 넣는다. 내림차순 정렬 후 재조립하여 문자열로 만든다. n = input() array = list() for data in n: array.append(data) array.sort(reverse = True) #내림차순 정렬 n = "".join(array) print(n) 3. 해설 및 코드분석 - 이번 문제의 핵심은 각 자리수를 .. 2021. 4. 16.
오늘의 알고리즘(4월 15일) 1. 백준, 수 정렬하기, 2750번 www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 2. 생각해보자. 첫번째 입력 N은 입력될 숫자의 개수다. 첫번째 입력 N을 이용하여 N번의 for문을 통해 숫자를 입력 받는다. N개의 숫자는 리스트에 저장한 후 정렬 함수(sort)를 이용하여 정렬한다. n = int(input()) numbers = [] for _ in range(n): numbers.append(int(input())) numbers.sort() for .. 2021. 4. 15.
오늘의 알고리즘(4월 14일, feat.Union Find) 1. 백준, 친구 네트워크, 4195번 www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 2. 생각해보자 - 입력값은 다음과 같다. 2는 테스트 케이스의 수(N) 3은 친구 관계의 수(F) / F는 100,000을 넘지 않음 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있다 / 알파벳 대문자 또는 소문자로 길이 20 이하의 문자열 친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇명이 있는.. 2021. 4. 14.
오늘의 알고리즘 (4월 13일) 1. 백준, 수 찾기, 1920번 www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 2. 생각해보자 첫 입력값은 숫자의 개수 N이 주어진다. 두번째 입력값에는 N개의 숫자만큼 정수가 주어진다. 세번째 입력값에는 찾을 숫자의 개수 M이 주어진다. 네번째 입력값에는 M개의 숫자만큼 정수가 주어진다. - 배열 두개를 만들어서 이중 for문을 돌려서 비교하면 될 것 같다. n = int(input()) sample = .. 2021. 4. 13.

티스토리툴바