본문 바로가기

Algorithm/알고리즘 문제풀이92

오늘의 알고리즘(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.
오늘의 알고리즘 (4월 9일) 1. 백준, SHA-256, 10930번 www.acmicpc.net/problem/10930 10930번: SHA-256 첫째 줄에 문자열 S가 주어진다. S는 알파벳 대문자와 소문자, 그리고 숫자로만 이루어져 있으며, 길이는 최대 50이다. www.acmicpc.net 2. 생각해보자 이번 문제는 쉬어가는 문제다. 해시함수를 어떻게 사용하는지 알기만 하면 풀 수 있는 문제이기 때문이다. 어떻게 사용하는지 알아보자. 3. 풀이 및 코드분석 해시 함수는 암호화 작업이다. 어떤 문자를 넣었을 때, 해당 문자를 굉장히 긴 길이의 문자열로 변환시켜준다. SHA-256 는 여러 해시 알고리즘 중에서 가장 효율적(=빠름)이고 안정적인 해시 함수라고 할 수 있다. SHA-256을 안정적인 이유중 하나가 단방향성 암.. 2021. 4. 9.
오늘의 알고리즘(4월 8일) 1. 백준, 5397, 키로거 www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L의 길이 ≤ 1,000,000) 강산이가 백스페이 www.acmicpc.net 2. 생각해보자 a) 문제 정보 첫줄은 테스트케이스의 개수다. 백스페이스는 - 로 표현한다. 화살표는 로 커서의 움직임을 표현한다. 나머지 문자는 비밀번호다. b) 어떻게 풀 수 있을까? 테스트 케이스를 하나의 배열에 담는다. 비밀번호를 기록하기 위한 배열을 하나 더 만든다. 비밀번호 배열의 길이가 0일 때, 테스트케이스 배열에서 방향키가 나오면 아무런 영향이 없다. 다음 .. 2021. 4. 8.
오늘의 알고리즘(4월 7일) 1. 백준, 프린터 큐, 1966번 www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 2. 생각해보자 - 문제부터 이해 해보자. 첫번째 예시 3 1 0 5 최초의 입력은 총 테스트 케이스의 개수를 의미한다. 그러므로 3개의 테스트 케이스가 있다는 뜻이다. 두번째 줄의 1은 총 문서의 개수를 의미한다. 그러므로 총 1개의 문서가 있다는 뜻이다. 두번째 줄의 0은 현재 찾고 있는 문서가 몇번 인덱스에 위치했는지를 의미한다. 그러므로 0번 인덱스에 있다. 세번째 줄의 .. 2021. 4. 7.
오늘의 알고리즘(4월 6일) 1. 백준, 스택수열, 1874번 www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 2. 생각해보자 - 먼저, 문제에서 주어진 정보를 정리해보자. 1) 스택을 구현한다. (LIFO 특성) 2) push 와 pop 메소드를 사용한다. 3) 첫번째 입력값 n이 입력된 다음부터 입력되는 정수의 개수다. ex) 8이 첫번째 입력값이라면 이를 제외하고 앞으로 8개 정수가 더 입력된다. 4.. 2021. 4. 6.

티스토리툴바