전체 글

1. 해시 테이블이란? 데이터를 저장하는 자료구조 중 하나로, 키와 값을 연관시켜 저장하는 구조를 갖고있다. 해시 함수를 사용하여 키를 해시 값으로 변환하고, 이를 통해 데이터를 저장하고 검색할 수 있다. 2. 해시 테이블의 구조 해시 테이블은 배열로 구현되어있으며, 각 배열 요소는 버킷이라고 불리는 키와 값 쌍으로 저장된다. 3. 해시 테이블의 장점 1. 키가 해시 값으로 되어있기 때문에 검색속도가 O(1)로 굉장히 빠르다. 2. 키의 유형은 정수, 문자열, 객체 등 모든 유형이 가능하다. 3. 개방 주소법과 체이닝을 통해 해시 값이충돌되는 문제를 자동으로 해결해준다. 4. 중복된 키가 존재하지 않기 때문에 적절한 해시 함수의 사용은 메모리를 효율적으로 만들어준다.

백준 13144 https://www.acmicpc.net/problem/13144 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net 풀이 전 나의 생각 길이가 N인 수열이 주어질 때, 1개 이상의 연속된 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구해야 한다. 조건 - (1 ≤ N ≤ 100,000) - 수열에 나타나는 수는 모두 1 이상 100,000 이하 과정 수열 N이 10만의 범위로 주어지기 때문에 단순히 2중 for문을 이용한 풀이를 진행한다면 10만 * 10만의 계산 횟수로 시간 제한을 ..

1. 가비지 컬렉터란? 런타임 환경에서 동적으로 할당된 메모리의 누수를 방지하고 사용되지 않는 메모리를 찾아 회수하며 관리해주는 기능이다. 대표적으로 JAVA와 C#에 존재하며 자동으로 메모리를 관리해주지만 C++과 같은 언어는 직접 사용자가 메모리를 관리해줘야 한다. 2. 가비지 컬렉터의 동작 과정 1. 프로그램의 모든 메모리를 검사하여 객체의 사용여부를 루트 세트의 시작점을 사용하여 표시한다. (루트 세트 - 전역 변수, 지역 변수, 정적 변수 등, 직접적으로 참조되는 객체들) 2. 객체의 사용여부가 표시되지 않은 객체를 메모리에서 제거한다. 제거한 메모리는 프로그램이 다시 사용이 가능하다.(메모리 누수 방지) 3. 사용되지 않는 객체의 메모리 공간을 메모리의 끝쪽으로 이동시켜 단편화 한다. (효율적..

백준 2003 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 풀이 전 나의 생각 N개의 수로 된 수열이 주어진다. 이 수열의 i번째 수부터 j번째 수까지의 합이 M이 되는 경우의 수를 구해야 한다. 조건 - N(1 ≤ N ≤ 10,000) - M(1 ≤ M ≤ 300,000,000) - A[x]는 30,000을 넘지 않는 자연수 과정 N, M, A[x]는 int의 범위를 벗어나지 않기 때문에 데이터 타..

1. 제네릭 컬렉션이란? 제네릭 기반의 데이터 구조를 말한다. 다양한 데이터의 저장 및 관리가 가능하고 타입 안정성과 성능을 보장한다. 2. 제네릭 컬렉션의 종류 - List 동적으로 크기 조절이 되는 배열을 구현한 리스트 - Dictionary 키-값 쌍을 저장하는 컬렉션 - HashSet 중복을 허용하지 않는 집합 - Queue FIFO(First In First Out)의 원칙을 따르는 큐 - Stack LIFO(Last In First Out)의 원칙을 따르는 스택 -LinkedList 이중 연결 리스트를 구현한 리스트 -SortedDictionary 키에 대해 정렬된 순서를 가지는 컬렉션, 키 값에 따라 자동 정렬 -SortedSet 정렬된 순서를 유지하는 집합, 키 값에 따라 자동 정렬

백준 1644 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 풀이 전 나의 생각 자연수 N이 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구해야 한다. 조건 - (1 ≤ N ≤ 4,000,000) 과정 N은 1이상 400만 이하의 값의 범위를 가지기 때문에 데이터 타입을 int로 설정한다. 소수들을 더해줄 누적합의 공간은 400만을 크게 벗어나지 않을 것이기 때문에 데이터 타입을 int로 설정한다. -> 목표로하는 소수의 합은 N이기 때문 소수를 구할 때 최적화 된 방법없이 2중 for문을 사용하면 400만 * 400만의 계산 횟..

1. 실수 표현 방식 컴퓨터는 0과 1로 이루어졌다는 이야기를 많이 들어봤을 것이다. 실제로 컴퓨터는 0과 1로 이루어진 비트로 연산을 수행하고 저장할 수 있기 때문에 실수도 이진수로 표현해야만 한다. 하지만 정수에 비해 실수를 이진수로 표현하려면 굉장히 복잡하기 때문에 이를 해결하기 위하여 고정 소수점과 부동 소수점 방식을 사용하고 있다. 2. 고정 소수점 구조를 보면 정수부와 소수부의 비트가 적기 때문에 연산속도가 굉장히 빠르고 메모리 사용량이 적다. 하지만 그만큼 표현할 수 있는 수의 범위가 굉장히 좁고 정밀하지 않다. 이를 해결하기 위해 정수부의 비트를 늘려버리면 큰 수는 표현할 수 있지만 소수부의 비트가 줄어들어 정밀한 표현이 불가능하고 소수부의 비트를 늘려버리면 정밀한 표현이 가능하지만 큰 수..

백준 1806 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 전 나의 생각 N 길이의 수열이 주어질 때 연속된 수들의 부분합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구해내야 한다. 조건 - N (10 ≤ N < 100,000) - S (0 < S ≤ 100,000,000) - 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수 과정 목표 값 S는 1억 이하의 수기 때문에 데이터 타입을 int로..