🌏 주제 : 10 - 해시법 (자바편) 🌏 해시법 해시법은 데이터를 저장할 위치(인덱스)를 간단한 연산으로 구하여 검색,추가,삭제를 효율적으로 수행 🌏 충돌(Collision) 만약 333이라는 값이 인덱스 14에 저장되어있는데 이후에 130이라는 값(나머지 14)을 저장한다고 가정 -> 이렇게 저장할 버킷이 중복되는 현상을 충돌이라고 한다. -> 해시 함수는 가능하면 해시값이 치우치지 않도록 고르게 분포된 값을 만들어야 한다. 충돌 대처법 2가지 1. 체인법 : 해시값이 같은 요소를 연결 리스트로 관리 2. 오픈 주소법 : 빈 버킷을 찾을때 까지 해시 반복 🌏 오픈 주소법 충돌이 발생했을 때 재해시를 수행하여 비어있는 버킷을 찾는 방법 -> 닫힌 해시법이라고도 함 18 삽입 하고자 할때 18 % 13 ..
🌴 문제 문제 상근이의 동생 상수는 수학을 정말 못한다. 상수는 숫자를 읽는데 문제가 있다. 이렇게 수학을 못하는 상수를 위해서 상근이는 수의 크기를 비교하는 문제를 내주었다. 상근이는 세 자리 수 두 개를 칠판에 써주었다. 그 다음에 크기가 큰 수를 말해보라고 했다. 상수는 수를 다른 사람과 다르게 거꾸로 읽는다. 예를 들어, 734와 893을 칠판에 적었다면, 상수는 이 수를 437과 398로 읽는다. 따라서, 상수는 두 수중 큰 수인 437을 큰 수라고 말할 것이다. 두 수가 주어졌을 때, 상수의 대답을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 칠판에 적은 두 수 A와 B가 주어진다. 두 수는 같지 않은 세 자리 수이며, 0이 포함되어 있지 않다. 출력 첫째 줄에 상수의 대답을 출력..
🌱 오늘의 주제 : 쓰레드의 우선순위 & 데몬 쓰레드 🌱 쓰레드의 우선순위 쓰레드는 우선순위라는 속성을 가지고 있는데, 이 우선순위의 값에 따라 쓰레드가 얻는 실행시간이 달라진다. 예를 들어, 파일전송기능이 있는 메신저의 경우, 파일 다운로드를 처리하는 쓰레드보다 채팅 내용을 전송하는 쓰레드의 우선순위가 더 높아야 사용자가 채팅하는데 불편함이 없을 것 이다. 우선순위 범위는 1~ 10이며, 숫자가 높을수록 우선순위가 높다. 쓰레드의 우선순위는 쓰레드를 생성한 쓰레드로부터 상속받는다. 예를 들어, main메서드를 수행하는 쓰레드는 우선순위가 5이므로, main메서드 내에서 생성하는 쓰레드의 우선순위는 자동적으로 5가 된다. 쓰레드를 실행하기 전에만 우선순위를 변경할 수 있다. void setPriority..
🌱 오늘의 주제 : 이클립스 프로젝트 배포시 오류 - The project description file (.project) for 'academy' is missing. This file contains important information about the project. The project will not function properly until this file is restored. 🌱 이클립스 프로젝트 배포시 오류 파일>워크스페이스 변경을 하여 변경하고자 하는 곳으로 변경 저자의 변경 위치 : desktop -> Algorithm *참고 https://suyou.tistory.com/53
🌴 문제 문제 영어 대소문자와 공백으로 이루어진 문자열이 주어진다. 이 문자열에는 몇 개의 단어가 있을까? 이를 구하는 프로그램을 작성하시오. 단, 한 단어가 여러 번 등장하면 등장한 횟수만큼 모두 세어야 한다. 입력 첫 줄에 영어 대소문자와 공백으로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 공백 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 문자열은 공백으로 시작하거나 끝날 수 있다. 출력 첫째 줄에 단어의 개수를 출력한다. 예제 입력 1 복사 The Curious Case of Benjamin Button 예제 출력 1 복사 6 예제 입력 2 복사 The first character is a blank 예제 출력 2 복사 6 예제 입력 ..
🌱 오늘의 주제 : 싱글쓰레드와 멀티쓰레드 🌱 싱글쓰레드와 멀티쓰레드 하나의 쓰레드로 두 작업을 처리하는 경우는 한 작업을 마친 후에 다른 작업을 시작한다. 두개의 쓰레드를 작업 하는 경우에는 짧은 시간동안 2개의 쓰레드가 번갈아 가면서 작업을 수행해서 동시에 두 작업이 처리되는 것과 같이 느낀다. 하나의 쓰레드로 두개의 작업을 수행한 시간과 두개의 쓰레드로 두 개의 작업을 수행한 시간은 거의 같다. 오히려 두 개의 쓰레드로 작업한 시간이 싱글쓰레드로 작업한 시간보다 더 걸린다. 이유는 쓰레드간의 작업 전환에 시간이 걸리기 때문이다. 싱글 코어에서 단순히 CPU만을 사용하는 계산작업이라면 오히려 멀티쓰레드보다 싱글쓰레드로 프로그래밍하는 것이 더 효율적이다. 🌱 싱글쓰레드와 멀티쓰레드 예제 싱글 코어인 ..
🌏 주제 : 09 - 이진검색트리 (자바편) 🌏 이진검색트리 (자바편) 이진탐색트리(Binary Search Tree)는 이진 트리 기반의 탐색을 위한 자료구조이다. 전화번호부에서 전화번호를 찾거나, 사전에서 단어를 찾는 탐색 작업을 효율적으로 하기 위한 자료구조이다. 탐색작업을 하기에 앞서, 이진탐색트리의 정의에 대해 알아보면 다음과 같다. 1. 모든 노드의 키는 유일하다. 2. 왼쪽 서브트리의 키들은 루트의 키보다 작다. 3. 오른쪽 서브트리의 키들은 루트의 키보다 크다. 4. 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다. 🌏 이진탐색트리의 삭제연산 1. 삭제하려는 노드가 단말노드인경우 2. 삭제하려는 노드가 두개의 서브트리중 하나만 가지고 있는 경우 3. 삭제하려는 노드가 두개의 서브트리를 모두 가..
🌏 주제 : 08 - 원형 이중 연결 리스트 만들기 (자바편) 🌏 원형 연결 리스트 원형 연결 리스트 : 연결 리스트의 맨 끝 노드를 첫 번째 노드와 연결시켜 원형으로 만든 리스트이다. 맨 끝 링크는 맨 앞 노드를 가리킨다. 포인터는 맨 끝 노드를 가리킨다. 맨 끝과 맨 앞을 바로 찾을 수 있다. 🌏 원형 이중 연결 리스트 이중 연결 리스트란 연결 리스트의 각 노드에 링크를 2개 만들어 하나는 뒷 노드를 하나는 앞 노드를 가리키는 연결 리스트이다. 기존의 단순 연결 리스트는 노드 포인터를 알고 있을 때 노드의 다음 노드는 찾아갈 수 있지만, 노드 앞의 노드는 찾아갈 수 없다. 앞의 노드를 찾으려면 리스트의 처음부터 거슬러 올라가야 한다. 따라서 단순 연결 리스트의 각 노드에 두 개의 노드 포인터를 두어 ..
🌏 주제 : 07 - 보이어 . 무어법 (자바편) 🌏 보이어 . 무어법 (자바편) 보이어-무어 알고리즘 KMP 알고리즘의 개선판이라고 할 수 있습니다. 시간복잡도는 최악의 경우 O(N)이지만 평균 O(N/M)의 시간복잡도를 가진다고 합니다. O(N+M)인 KMP 알고리즘보다 향상된 성능을 기대할 수 있습니다. 보이어-무어 알고리즘의 작동은 KMP 알고리즘과 유사하게 불필요한 비교는 건너뛰고 유의미한 비교만 진행하겠다는 것입니다. KMP 알고리즘의 경우에는 접두사와 접미사가 같은 최대길이를 저장하는 배열을 만들어 앞에서부터 검사를 진행하였다면, 보이어-무어 알고리즘은 문자열을 검색할때 주로 뒤에서 부터 확인합니다. 보이어-무어 알고리즘은 두가지 이동 방법이 존재하지만 주로 사용하는 bad match tab..
🌴 문제 문제 문자열 S를 입력받은 후에, 각 문자를 R번 반복해 새 문자열 P를 만든 후 출력하는 프로그램을 작성하시오. 즉, 첫 번째 문자를 R번 반복하고, 두 번째 문자를 R번 반복하는 식으로 P를 만들면 된다. S에는 QR Code "alphanumeric" 문자만 들어있다. QR Code "alphanumeric" 문자는 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ\$%*+-./: 이다. 입력 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스는 반복 횟수 R(1 ≤ R ≤ 8), 문자열 S가 공백으로 구분되어 주어진다. S의 길이는 적어도 1이며, 20글자를 넘지 않는다. 출력 각 테스트 케이스에 대해 P를 출력한다. 예제 입력 1..
