[코드트리 조별과제] 정렬을 다루는 자료구조 in Java
·
CodeTree
PQ를 써야하는 순간은 보통 자신이 정한 정렬기준을 통해 지속적으로 정렬상태를 특정 시점마다 유지하고 싶을때 사용한다. 생각해보면 PQ만 정렬을 보장해주는 자료구조가 있는것은 아니다. Java에는 PQ, TreeMap, TreeSet 이 있다. 각각 어떨때 쓰는것이 좋을까? TreeSet의 경우에는 PQ와 거의 동일하다. 오히려 TreeSet은 최대(first) 최소(last)를 관리하기 더 편하며, 특정 값 바로 이상(floor), 초과(higher), 이하(ceiling) 그리고 미만(lower)인 값을 꺼내는데 유용하다. 하지만 TreeSet은 어디까지나 Set을 기반으로 한 OrderedSet이라는것을 잊으면 안된다. 즉, 정렬의 대상이되는 원소에 대한 중복을 허용치 않는다는점이다. 예를들어서 어..
[코드트리 조별과제] HashSet 활용
·
CodeTree
해시 셋은 보통 중복을 제거하여 고유의 값을 뽑아낼때 사용한다.  약간 돌려서 얘기하자면, 쓸데없는 값이 중복되어 연산되는걸 막아줄때 사용하기도 한다. 코드트리에 있는 "초대장과 번호표" 라는 문제가 있는데, 이는 백준의 "거짓말" 과 비슷하게 생겼다. 물론 백준의 "거짓말" 문제는 범위가 매우 작다( 코드트리 문제 기준으로 그룹이 50개고 각 그룹별 50명이다. ) 하지만 코드트리의 문제는 범위가 그룹은 최대 25만개에 인원또한 25만명으로 책정되어 있다. 이걸로 인해 시간복잡도 N^2의 완전탐색은 불가하다고 생각하겠지만 중요한 조건이 추가적으로 있다. 바로 " 모든 그룹 내 사람 수의 총합  이걸 해석해보면 그룹이 극단적으로 25만개 였다 하더라도, 그룹별 인원은 1명이 되는것이다. 즉, 그룹과 인원..
[코드트리 조별과제] HashMap 활용
·
CodeTree
코드트리에 HashMap을 활용하는 문제에서 임의의 두 수의 합을 구하는 문제가 있다. 수가 중복해서 나올 수 있는점을 고려해야 하기에 문제가 까다롭지만, HashMap을 사용하면 상수시간에 가까운 시간복잡도로 문제를 해결할 수 있다. HashMap을 굳이 안쓰고 문제를 접근할 수도 있다 (투포인터, 합이 0에 가까운 또다른 수 찾기 (이분탐색)) 하지만 숫자가 매우 큰경우에는 일반적인 배열의 인덱스로 활용하기 힘들기에 해싱 자료구조를 채택하는것이 좋다. 문제중에 두 수의 합과 세 수의 합이 있는데, 초안으로는 이분탐색과 투포인터로 해결할 실마리가 보였지만 반례에 막혔고 중복된 수에 대한 경우의수 예외를 적절하게 처리해주면 된다. 이를 위해 미리 수에 대한 카운팅 Map을 만들어주고 현재 소모할 숫자를 ..
예외처리와 Try With Resources
·
Java
응용프로그램에서 문제가 발생하면 보통 에러 혹은 예외를 던진다. 자바의 에러 구조는 다음과 같다. 가장 상위 인터페이스로 Throwable 이 있고여기서 Throwable을 상속받는 두가지로 예외는 Exception, 에러는 Error로 나뉜다. 그리고 Exception을 상속받는 클래스 중 RuntimeException은 런타임 도중 발생하는 예외를 잡는다. 예외는 던지거나 잡을 수 있다.던지고싶다면 메소드 선언부에서 throws 키워드로 던지고싶은 Exception을 나열하면된다.잡으려면 try-catch~finally가 있다. try ~ catch ~ finally에서 중요한 점은Exception이 catch 되더라도 finally는 발동한다.public int test(){ try{ ..
함수형 인터페이스
·
Java
Functional Interface https://download.java.net/java/early_access/panama/docs/api/java.base/java/util/function/package-summary.html Since 1.8 Functional Interface 는 람다 표현식과 메소드 레퍼런스에 대한 타겟 타입을 제공합니다. 각각의 Functional Interface는 Functional method라고 불리는 단일 추상 메소드를 가지고 있습니다. @Functional Interface 어노테이션: 해당 인터페이스가 함수형 인터페이스로 될 수 있는지 컴파일단계에서 검증하기 위한 어노테이션 함수형 인터페이스는 하나의 추상 메소드만 요구하지만, 여러 개의 디폴트 또는 정적 메소..
가비지 컬렉션 - 가비지 컬렉션의 개념와 작동 방식
·
Java
https://www.ibm.com/topics/garbage-collection-java 위의 글을 기반으로 작성한다. 가비지 컬렉션이란? 자동으로 메모리 할당 및 생성된 객체에 대한 메모리 할당해제를 관리하는 자바언어의 주 기능 중 하나 자바에서의 가비지 컬렉션은 개발자가 메모리 관리 측면에서 걱정없이 코드를 작성하는 것에 집중하도록 도와준다. 그러나 그들의 코드 퍼포먼스와 공통의 메모리 관련 문제들을 피하기 위해서는 자바 개발자라면 가비지 컬렉션의 작동방식은 알아야 한다. 메모리 부족 에러란? 메모리 부족 에러는 프로그램 또는 어플리케이션이 이용 가능한 메모리 양 보다 더 많은 양을 할당 하려고 시도할 때 발생하는 에러다. 이러한 에러는 JVM 또는 다른 플랫폼에서 어플리케이션을 작동시키는 동안 메..
OS - 다중모드 운용과 타이머
·
CS
운영체제와 사용자는 컴퓨터 시스템 내 하드웨어와 소프트웨어 자원을 공유하기 때문에 운영체제 혹은 사용자로부터의 잘못된 명령수행이 일어나지 않도록 보장해야 한다. 따라서 대부분의 컴퓨터 시스템에는 사용자 모드와 커널 모드로 최소한 두 개의 모드로 나누어진다. 이렇게 모드를 나누는 비트를 모드비트 라고 한다. 부팅과정을 예시로 설명하자면 아래와 같다. 처음 부팅시 부트스트랩에 의해 부트로더가 실행되기 위해서 커널모드에서 시작한다. 부트로더가 정상적으로 운영체제를 메모리위에 올려 실행되고 그 이후 사용자모드로 전환된다. 이 사용자가 응용프로그램들을 실행하게 되고, 그러다가 인터럽트 또는 트랩이 발생하게 되면 다시 커널모드로 전환하여 인터럽트를 처리하고 난 후 모드 비트를 바꾸어 사용자모드로 전환한다. 트랩(t..
OS - 멀티 프로그래밍과 멀티태스킹
·
CS
우리가 컴퓨터의 전원을 키면 젤 먼저 작동하는 것은 부트스트랩과 같은 초기 프로그램이다. 부트스트랩은 컴퓨터 내 하드웨어를 사용가능한 상태로 초기화 하고, 운영체제를 실행시키기 위해 부트로더를 실행시켜 메모리 위에 운영체제를 올린다. 이렇게 운영체제가 메모리위에서 작동하게 되면 비로소 사용자와 시스템에 서비스를 제공할 수 있게 된다. 여기서 몇몇 서비스들은 운영체제가 실행되는 동안에 함께 실행되기 위해 부팅 시 메모리에 load되는데, 이를 시스템 데몬이 이라고 한다. 여기서 데몬이란 백그라운드에서 실행되는 시스템 서비스를 말한다. 데몬은 사용자와의 상호작용을 하지 않는다. 멀티 프로그래밍 운영체제에서 가장 중요한 점은 CPU가 쉬지 않게 효율적으로 프로그램을 관리하는 것이다. 만약 CPU가 하나의 프로..