본문 바로가기

분류 전체보기

 (79)
버킷정렬(Bucket Sort) 버킷 정렬(bucket sort) or bin sort 은 입력 값이 일정한 범위에 걸쳐 분포(uniformly distributed)되어있을 때 주로 유용하다. 예를들어 0.0에서 1.0 범위의 부동 소수점 숫자 집합을 정렬해야 하고 싶다고 할때 선택할수 있는 정렬의 방법은 여러가지이다. 간단한 방법은 비교 기반 알고리즘(comparision based sort alogrithm)을 적용하면 된다. 비교 기반 알고리즘 중 그래도 시간복잡도가 좀 빠른 병합 정렬(merge sort), 힙 정렬(heap sort), 빠른 정렬(quick sort)은 O(nLogn) 이다. 즉 O(nLogn)보다 좋을수는 없다. 선형 시간(linear time)으로 배열을 정렬할 방법은 없을까? 카운팅 정렬(counting..
백준 7785 - 회사에 있는 사람 문제링크 : https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 문제 상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다. 각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다. 상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성 www.acmicpc.net Note 이 문제는 출근시(enter) 사람의 이름을 특정 자료에 저장해 놓고 퇴근시(leave) 자료에서 삭제한 ..
백준 1620 - 나는야 포켓몬 마스터 이다솜 문제링크 : https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 물어봐도 괜찮아. 나는 언제든지 질문에 답해줄 준비가 되어있어. 둘째 줄부터 N개의 줄에 포켓몬의 번호가 1번인 포켓몬부터 N번에 해당하는 포켓몬까지 한 줄에 하나씩 입력으로 들어와. 포켓몬의 이름은 모두 영어로만 이루어져있고, 또, 음... 첫 글자만 www.acmicpc.net Note 이 문제는 해시테이블(HashTable) 자료구조를 이해하면 아주 쉽게 풀수 있는 문제이다. 해..
백준 5639 - 이진 검색 트리 문제링크 : https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 문제 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. 전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, www.acmicpc.net Note 이 문제를 풀기위한 설명은 이진탐색트리(Binary Search Tree) POST를 참고하면 되는데 pre..
백준 1920 - 수 찾기 문제링크 : https://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안에 존재하는지 알아내면 된다. 모든 정수들의 범위는 int 로 한다. www.acmicpc.net Note 이 문제는 N개의 정수 A[1], A[2], …, A[N] 중에서 입력된 정수가 있는지 없는지를 찾아야 하는 탐색(검색)문제이다. 사실 A[1], A[2], …, A[N] 중에서 특정 정수가 있는지 없는지 확인하기 위한 가장 간단한 방법은 선형(순차) 탐색(Linear..
백준 1991 - 트리 순회 문제링크 : https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현된다. www.acmicpc.net Note 이 문제를 풀기위한 설명은 트리(Tree)와 이진트리(Binary Tree) POST를 참고하면 된다. 첫 번째는 줄에는 노드의 개수이고 그 다음줄 부터 하나씩 읽어가면서 노드 , 왼쪽 자식노드, 오른쪽 자식노드 순으로 노드를 추가하면서 이진트리를 그성하고 pre-order, ..
백준 1764 문제 - 듣보잡 문제출처 : https://www.acmicpc.net/problem/1764 문제 김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 영어 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다. 출력 듣보잡의 수와 그 명단을 사전순으로 출력한다. 테스트케이스 입력 출력 3 4 ohhenrie charlie baesangwook obama baesangwook ..
(재귀)피보나치 수열(Fibonacci Sequence) 피보나치치 수열(Fibonacci Sequence)은 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열을 말한다. ▲ (출처: https://blogs.glowscotland.org.uk/glowblogs/jypetrieuodep/2018/10/09/fibonacci-sequence-significant-coincidence/) 피보나치 수열을 구현하기 위한 방법이 몇가지 존재하는데 여기서는 재귀함수를 이용하도록 하겠다. 재귀함수(Recursive Function)란? 글을 읽어보면 재귀함수에는 재귀가 수렴해야 할 베이스케이스와 재귀케이스가 있어야 하는데 0번째 항부터 피보나치 수열을 시작할 경우 베이스케이스와 재귀케이스는 아래와 같다. 베이스케이스 : F0 = 0 and F1 ..

티스토리툴바