전체 글 검색 결과

해당 글 904건
java queue : 어떻게 사용하는지 간단히 알아봅시다.

java에서 Queue는 어떻게 사용할까요? 저번 시간에 리스트를 잘 보셨다면, 대략적으로 감이 오실 거에요. 아. 이건 빼박 리스트구나. 사실 동적 배열을 이용해도 되는데요. 이것은 잘 생각해 보세요. 예제 프로그램을 봅시다. 일단 저는 my_Object 객체를 Queue에 넣을 거에요. 이건 아마 딱 봐도, 미로 찾기나, 어느 지점에서부터 최단 거리를 구할 때 쓰는 것 같군요. 이제 main 함수를 볼까요? 16번째 줄이 보이시나요? 저는 LinkedList를 쓸 거에요. LinkedList는 deque를, deque는 queue를 implements를 한 관계입니다. 이것은 Collections 시간에 다시 정리해 봅시다. 일단 오늘은, 아 이런 게 있구나. 정도만 보시면 되겠습니다. 사실 큐의 특..
자료알고/자료구조 2019. 8. 5. 17:48
약수 구하기 알고리즘 : n^0.5만 보고도 구할 수 있다.

약수를 구하는 것은, 정수론 문제를 풀 때 기본이 되는 연산 중 하나입니다. 우리는 약수를 구하는 알고리즘을 다음과 같은 구현을 생각할 수 있을 겁니다. 이것은 간단합니다. n의 약수를 구할 때, 나누는 수를 1부터 n까지 모두 검사해 봅니다. 만약에 n을 나누는 수 r로 나눴을 때, 나머지가 0이라면, r로 나누어 떨어지는 겁니다. 이것은 올바른 결과를 냅니다. 하지만, 오래 걸립니다. 예를 들어서, n의 값이 10^12만 되어도 아래와 같은 연산을 10^12번 해야 할 겁니다. 10^12번. 상당히 끔찍하지 않나요? 1초에 단순 연산을 10^9회 정도 한다고 한다면, 1000초, 약 20초, 어마무시한 시간이 걸려버립니다. 이 끔찍한 시간을 줄일 수 있는 방법이 없을까요? Lemma 하나 들고 옵시다..
자료알고/알고리즘 2019. 8. 4. 23:51
cp949 vs euc-kr : 어떤 차이점이 있는지 간단히 알아봅시다.

인코딩에 대한 이야기 3편. 오늘은 EUC-KR과 CP949에 대해서 잠깐 이야기 해 보도록 하겠습니다. EUC는 아시아계 문자를 표현하기 위해서 개발을 한 코드 체계인데요. 뒤에 KR이 붙었으니까, 한국에서 쓰는 것입니다. 이것은 어떤 특징을 가질까요? 그 전에 KS X 1001이라는 체계가 있어요. 이것은 한국 산업 규격으로 지정된, 한국어 문자 집합 체계입니다. 0x30부터 0x48까지, 그러니까 제가 초록색으로 칠한 부분에 '가', '조', '힝'과 같은 완성형 한글 글자 마디가 속해 있어요. 그런데, 그렇게 문자가 많아보이지는 않습니다. 실제로 자주 쓰이는 2350자만, 가나다, 그러니까 사전 순으로 배열했는데요. 한글 문자 갯수가 11176개이니까, 나머지 8000여개는 없는 셈이 됩니다. E..
코딩/Java 2019. 8. 4. 19:10
백준 1406 에디터 : List를 이용해서 해결해 봅시다.

링크드 리스트를 이용해서 간단한 편집 프로그램, 그러니까 vim과 같은 것들을 구현할 수 없을까요? 물론, 실제로 제가 구현할 것은 이것보다는 간단한 녀석입니다. 보통, 자료구조 프로젝트 때 적지 않게 하실 수도 있을 듯 싶네요. 사실 기능은 생각보다 단순해 보입니다. 커서를 이동시킵니다. 그리고 커서 앞에 문자를 추가시킵니다. + 앞에 't'를 추가시켰습니다. 이게 add 연산입니다. 아니면, 커서 앞에 있는 문자를 제거할 수도 있어요. 예를 들어서, 여기에서는 ( 앞에 있는 y라는 문자를 제거했습니다. 이런 간단한 편집 프로그램은 어떻게 구성하면 좋을까요? 단, 삽입, 삭제, 커서 이동 쿼리가 최대 60만개 들어옵니다. 배열은 장점이 무엇인가요? cache friendly 하다는 겁니다. 단점이 무엇..
자료알고/자료구조 2019. 8. 4. 00:57
java 참조 타입 vs 기본 타입 : 어떤 값을 저장하는가?

자바에는 두 가지 타입이 있습니다. 기본 타입은 byte, char, short, int, long, float, double, boolean이 있어요. 참조 타입은 객체를 가리키는 변수인데요. 이들이 어떻게 다른지 예제 프로그램과 그림으로 설명해 보도록 하겠습니다. 문제의 예제 프로그램입니다. 7번째 줄까지 수행이 되면, 메모리에 다음과 같이 올라갑니다. n과 m은 기본형으로 선언된, 변수들입니다. 즉, 실제 값을 저장하고 있습니다. 8번째 줄에 2차원 배열인 arr을 선언했는데요. 이는 기본형이 아닙니다. 즉 참조형이라는 이야기인데요. 이것은 실값을 저장하지 않습니다. 참조값을 저장해 놓습니다. 그러면 arr은 실값을 저장해 놓았나요? 아닙니다. 객체를 참조하는 어떠한 값을 저장해 놓습니다. 이것이 ..
코딩/Java 2019. 8. 3. 21:07