computer_study

소개 counting sort는 여러 정렬 알고리즘 중 하나로 n이 입력되었을 때, 문자열을 count해주는 부분에서 O(n) , result에 결과를 저장하는 부분에서 O(n), 출력부분에서 O(n)이 소요되어 Linear time( O(n) ) 안에 정렬을 끝낼 수 있다. Pseudo code 동작과정 1. 입력배열 A, 수를 세기위한 배열 B, 결과를 저장하기 위한 배열 result가 필요하다. 2. 입력 배열A에서 나오는 수를 count하여 B에 저장해준다. 3. 이후 B배열을 누적하여 새로운 배열을 만든다. 각 배열은, 정렬 시 해당 index가 몇번부터 시작하는지를 의미한다. (ex, B[2] = 4는 2가 result의 [4]부터 시작해서 앞 1 을 만날 때 까지 2를 채우면 된다는 의미이다..

문제 : www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해결 아이디어 1. 배열에 모두 저장하여 stl을 활용하여 해결하면 간단한 문제이지만, 최대 1000만개의 데이터가 주어지기에 stl을 이용하지않는다. 2. 입력받은 값들을 모두 저장하지않고 해결하기 위해 counting sort를 이용한다. ( counting sort에 대한 내용은 knowable.tistory.com/17에서 확인할 수 있다. ) python import sys n = int(sys.stdin..

문제 : www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 � www.acmicpc.net 문제 해결 아이디어 1. 각 언어의 sort stl의 특성을 이용한다. python python에선 sort함수로, list를 특정 인자로 정렬을 한다고 지정 시, 나머지 인자들은 원래 list 순서대로 유지한다는 특징을 이용한다. ex) (2,4),(2,3),(1,5) 를 첫번째 인자를 기준으로 정렬한다면 (1,5),(2,4),(2,3)이 된다. n = int(input()) array = [] for..

문제 : www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 문제 해결 아이디어 1. 단순 정렬 문제이므로 여러 정렬 방법이 사용 가능하다. 2. 버블정렬과 stl을 사용하여 문제를 해결한다. python stl을 사용한 풀이이다. python에서 list sort는 O(n x lgn)을 보장하기 때문에 이 문제를 풀기에 넉넉하다. num = int(input()) arr = list() for _ in range(num): arr.append(int(input())..

문제 : www.acmicpc.net/problem/4195 4195번: 친구 네트워크 문제 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다. 어떤 사이 www.acmicpc.net 문제 해결 아이디어 1. union-find 알고리즘을 사용하여 문제를 해결한다. 2. 자신의 상위 노드를 저장하는 배열 하나와, 자신의 현재 네트워크를 저장하는 배열을 선언한다. 3. 2명의 이름을 입력받고, 새로 들어온 사람이라면 상위노드를 자기자신, 네트워크 수를 1로 초기화한다. 4. find함수를 이용하여 해당 이름의 최상위 노드값을 찾아내고, 두 최상위 노드를 비교하여 다르다면 (다른 집합이라면) ..

문제 : www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안�� www.acmicpc.net python python을 이용했을 때, set자료형을 이용할 수 있다. set자료형은 집합처럼 중복없이 저장할 수 있고, 요소의 존재 여부를 간단하게 판단할 수 있다. n = int(input()) array = set(map(int,input().split())) m = int(input()) x = list(map(int,input().split()))..

문제 : www.acmicpc.net/problem/5397 5397번: 키로거 문제 창영이는 강산이의 비밀번호를 훔치기 위해서 강산이가 사용하는 컴퓨터에 키로거를 설치했다. 며칠을 기다린 끝에 창영이는 강산이가 비밀번호 창에 입력하는 글자를 얻어냈다. 키로거� www.acmicpc.net 문제 해결 아이디어 1. stack을 두개 사용하여 가운데에 cursor가 있다고 생각한다. 2. '-' 가 입력되면 left stack에서 pop을 한다. 3. ''가 입력되면 커서가 오른쪽으로 옮겨가야 되므로, right stack의 top값을 빼서 left stack으로 옮긴다. 5. 3,4번진행 중 stack이 비어있어 뺄 수 있는 top이 없다면 넘어간다. 6. 일반 문자가 입력되면 left stack에 넣어..

문제 : www.acmicpc.net/problem/1966 1966번: 프린터 큐 문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료�� www.acmicpc.net 문제 해결 아이디어 1. 문제의 흐름을 따라 코드를 작성한다. (최대 들어오는 data값이 100, 제한시간이 2초이므로 흐름에 따라 작성해도 충분하다.) 2. 현재 큐에서 priority의 최대값과, 큐의 가장 앞문서의 priority값이 같은지 확인한다. 3. 같다면 인쇄한다는 의미로 count를 증가시키고, 인쇄하는문서의 index번호와. 찾으려는 문서의 번호가 같은지 확인한다. 3-1. 같다면 ..