분류 전체보기(61)
-
RadixSort 기수 정렬 java
기수 정렬이란? 기수 정렬(radix sort)은 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘이다. 자릿수가 고정되어 있으니, 안정성이 있고(이때 데이터들 간의 상대적 순서는 보존되어야 한다.) 시간 복잡도는 {\displaystyle O(dn)}이다.({\displaystyle d}는 가장 큰 데이터의 자리수)기수 정렬은 비교 연산을 하지 않으며, 무엇보다도 전체 시간 복잡도 역시 {\displaystyle O(dn)}이어서, 정수와 같은 자료의 정렬 속도가 매우 빠르다. 하지만, 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다. 기수 정렬은 정렬 방법의 특수성 때문에, 부동소수점 실수처럼 특수한 비교 연산이 필요한 데이터에는 적용할 수 없지만, 사용 ..
2017.01.06 -
백준 10989 수 정렬하기 3 (java)
일단 문제는 아래 그림과 같다. 와 드디어 풀었다...이거 계속 시관 초과 나가지고 진짜 힘들었는데..ㅠㅠㅠ 시간제한이 5초라서 정말 힘들었다. Counting Sort 써서 푸는 건데 자바는 Scanner로 입출력을 받으면 아예 시간단축하기가 힘들다. (카운팅 소트 참고자료 : http://nhs0912.tistory.com/57 )그래서 사용한 것이 BufferdReader 와 BufferedWriter 이다. 여기서 중요한 것은 BufferedWriter 는 꼭 close()을 해야 출력이 된다. 아마 close() 전까지 계속 대기하는것 같다. 아래는 소스이다. 카운팅 소트에서 누적하진 않고 그냥 바로 출력하였다. 1234567891011121314151617181920212223242526272..
2017.01.02 -
계수 정렬(Counting Sort) java
계수 정렬(Counting Sort) 계수 정렬이란?In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence. Its run..
2016.12.27 -
백준 1193 분수찾기
문제 링크 : https://www.acmicpc.net/problem/1193요즘 알고리즘 문제 푸느라 시간을 보내고 있는데...역시 실력은 꾸준함만이 진리인듯하다. 일단 이 문제는 아래 그림과 같다. 문제를 읽어보면 일단 순서는 지그재그 형태로 나아간다. (그림 1)예제를 보면 14번째에 있는 분수를 찾아달라고 할 때 위에 그림을 보면 14번째에 2/4가 적혀있다. 그래서 출력은 2/4를 출력해야한다. 맨 처음 문제가 이해가 안되서 한참 걸렸다. 하지만 저 그림보면 금방 이해될듯 하다. 지금 현재 우리의 고개를 왼쪽으로 45도 정도 기울여주자! 그러면 밑에 있는 그림2처럼 보일것이다. (그림 2)일단 분자=up , 분모=down 이라는 변수로 치환하였다. (변수는 내가 편한대로 직관적으로 정했음)일단..
2016.12.16 -
숫자 팰린드롬(palindrome)
펠린드롬이란?회문(回文) 또는 팰린드롬(palindrome)은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말이다. 보통 낱말 사이에 있는 띄어쓰기나 문장 부호는 무시한다. 그렇다.내이름은 '이효리' 거꾸로 읽어도 '이효리'! 같은 단어나 문장을 회문 또는 팰린드롬이라고 부른다. 팰린드롬과 관련해서 흥미로운 수학적 관찰이 있다. 그것은 컴퓨터학자 그루엔버거(F.Gruenberger)는 1984년에 미국의 잡지 "사이언티픽 아케리칸(Scientific American)"에 실린 '컴퓨터 레크리에이션(Computer Recreations)'이라는 칼럼에서 다음과 같은 재미있는 알고리즘을 제기해서 많은 사람의 관심을 끌었다. 1) 숫자를 아무거나 고른다.2)그 수를 뒤집는다. 그 다음 뒤집어진 수와 원래의..
2016.12.12