목록2022/01 (70)
Developer_Neo
https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 문제 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다. 예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자 긴급전화: 911 상근: 97 625 999 선영: 91 12 54 26 이 경우에 선영이에게 전화를 걸 수 있는 방법이..
https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 문제 수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자. 산술평균 : N개의 수들의 합을 N으로 나눈 값 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값 최빈값 : N개의 수들 중 가장 많이 나타나는 값 범위 : N개의 수들 중 최댓값과 최솟값의 차이 N개의 수가 주어졌을 때..
정렬이란 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것 정렬 종류 버블 정렬 삽입 정렬 선택 정렬 퀵 정렬 병합 정렬 평균 시간복잡도 최악의 시간복잡도 최선의 시간복잡도 O(n) O(n) Runtime (60,000개 입력시) 단위 : sec 22.894 7.438 10.842 0.014 0.026 버블 정렬 (bubble sort) 란? 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘 서로 비교해서 큰 값을 뒤로 보내는 것이다. (오름차순으로) 핵심 SWAP 방식 2021.09.04 - [프로그래밍/알고리즘 with Java] - [자바] 정렬 알고리즘 - 버블정렬 [자바] 정렬 알고리즘 - 버블정렬 버블 정렬(Bubble So..
힙 (Heap) 트리를 기반으로 해 어떠한 목적에 따라 변환시킨 자료구조이다. 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 사용하는 이유 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n) 이 걸림 이에 반해, 힙에 데이터를 넣고, 최대값과 최소값을 찾으면, O(logn) 이 걸림 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨 구조의 조건 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다. (최대 힙의 경우) 최소 힙의 경우는 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나..
https://www.acmicpc.net/problem/4673 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net 문제 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 ..
트리 (Tree) 구조 Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 즉 노드로 이루어진 자료 구조이다. 트리는 하나의 루트 노드를 갖는다. 루트 노드는 0개 이상의 자식 노드를 갖고 있다. 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다. 노드(node)들과 노드들을 연결하는 간선(edge, Branch)들로 구성되어 있다. 트리에는 사이클(cycle)이 존재할 수 없다. 노드들은 특정 순서로 나열될 수도 있고 그럴 수 없을 수도 있다. 각 노드는 부모 노드로의 연결이 있을 수도 있고 없을 수도 있다. 각 노드는 어떤 자료형으로도 표현 가능함 어디에 많이 사용되나? 트리 중 이진 트리 (Binary Tree) 형태의 구조로, 탐색(검색)..
테이블이란? 표와 같은것으로 모든표를 가리켜 테이블이라 하지않는다. 따라서 저장된 데이터의 형태가 키(key)와 값(value)로 하나의 쌍을 이룰때에만 테이블로 구분짓는다. 이때 키는 데이터를 구분하는 기준이 되기 때문에 모든 키는 중복 되지않고 키가 존재하지 않는 값은 저장할 수 없다. 해쉬 테이블이란? Key와 Value로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조 해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 인덱스 혹은 주소 삼아 데이터의 값(value)을 키와 함께 저장하여 검색을 빠르게 하기 위한 자료 구조 위에서 말했던 테이블과 다른점은 해쉬함수를 이용한다는 것이다. 예) 파이썬 사전(Dictionary) 자료형 - Key를 가지고 바로 데이..
왜? 배우는가 하나의 문제를 푸는 알고리즘은 다양할 수 있다 이 다양한 알고리즘 중 어느 알고리즘이 더 좋은지 분석하기 위해, 복잡도를 정의하고 계산한다. 종류 시간복잡도 : 얼마나 빠르게 실행되고 결과를 도출하느냐 공간복잡도 : 얼마나 공간(메모리 사이즈)을 쓰느냐 둘 중에 더 중요한 것은 시간복잡도이다. 왜냐하면 요즘은 메모리가 매우 커졌기 때문에 시간복잡도보다는 중요도가 후 순위이다. 시간복잡도의 주요요소 - 반복문이 주요요소이다. 즉 반복문이 가장 영향을 많이 미친다.(입력의 크기가 커지면 반복문이 알고리즘 수행시간을 지배한다.) 그러면 시간복잡도를 우리 눈에 보기 좋게 객관적으로 표현을 해야 비교가 가능하다. 그래서 나온것이 빅오 표기법이다. 알고리즘 성능 표기법 Big O (빅-오) 표기법: ..