본문 바로가기
728x90
반응형

전체 글67

11장. 해시 테이블(5) - 예제(중복 문자 없는 가장 긴 부분 문자열) 중복 문자가 없는 가장 긴 부분 문자열의 길이를 리턴한다.입력: "abcabcbb"출력: 3입력: "pwwkew"출력: 3  풀이1. 슬라이딩 윈도우와 투 포인터로 사이즈 조절이 문제는 "슬라이딩 윈도우"와 "두 포인터" 기법을 사용하여 해결할 수 있다.슬라이딩 윈도우는 문자열의 특정 구간을 반복적으로 이동하면서 중복 없이 가장 긴 구간을 찾는 방법이다. 1. 슬라이딩 윈도우와 두 포인터의 역할윈도우: 문자열에서 중복 없는 구간을 나타낸다.두 포인터 (start와 index): start는 현재 윈도우의 시작 위치, index는 현재 문자의 위치를 나타낸다.이 방법은 두 포인터를 이용해 윈도우의 크기를 조절하며 중복이 생길 때마다 시작 위치를 업데이트하는 방식으로 작동한다. 예시를 통해 이해하기입력: ".. 2024. 11. 9.
11장. 해시 테이블(4) - 예제(보석과 돌) 문제. 보석과 돌J는 보석이며, S는 갖고 있는 돌이다. S에는 보석이 몇 개나 있을까? 이때, 대소문자는 구분한다. 입력: J ="aA", S = "aAAbbbb"출력: 3   풀이1. 해시 테이블을 이용한 풀이이 문제는 S의 각 문자 빈도를 해시 테이블로 계산한 후, J의 각 문자에 해당하는 빈도 수를 더하는 방식으로 해결할 수 있다. S = "aAAbbbb"freqs = {}for char in S: if char not in freqs: freqs[char] = 1 else: freqs[char] +=1 freqs # {'a': 1, 'A': 2, 'b': 4}  S의 각 문자가 몇 번씩 등장하는지 세기 위해 해시 테이블을 생성한다.S의 문자를 순.. 2024. 11. 8.
[Day5/30] 초보자를 위한 SQL 200제 1. 숫자를 버리고 출력하기 (TRUNC)876.567 숫자를 출력하는데 소수점 두 번째 자리인 6과 그 이후의 숫자들을 모두 버리고 출력SELECT '876.567' as 숫자, TRUNC(876.567,1), TRUNC(876.567,-1) FROM dual;  TRUNC(N,1): 소수점 두 번째 자리부터 버림TRUNC(N,-1): 소수점 이전 일의 자리부터 바로 버리고 출력  2. 나눈 나머지 값 출력하기 (MOD)숫자 10을 3으로 나눈 나머지 값이 어떻게 되는지 출력SELECT MOD(10,3) FROM dual;​ 사원 번호와 사원 번호가 홀수이면 1, 짝수이면 0을 출력 SELECT empno, MOD(empno,2) FROM emp;  사원 번호가 짝수인 사원들의 사원 번호와 이름을.. 2024. 11. 7.
11장. 해시 테이블 (3) - 충돌 처리 방식 (개별 체이닝 파이썬 구현) 다음의 기능을 제공하는 해시맵을 디자인하라.- put(key, value): 키, 값을 해시맵에 삽입한다. 만약 이미 존재하는 키라면 업데이트한다. - get(key, value): 키에 해당하는 값을 조회한다. 만약 키가 존재하지 않는다면 -1을 리턴한다.- remove(key, value): 키에 해당하는 키, 값을 해시맵에서 삭제한다.  풀이1. 개별 체이닝 방식을 이용한 해시 테이블 구현  우리가 구현할 MyHashMap 클래스의 전체 메소드는 아래와 같다.초기화 __init__()삽입 put()조회 get()삭제 remove()class MyHashMap: def __init__(self): def put(self, key:int, value: int) -> None: .. 2024. 11. 4.
11장. 해시 테이블 (2) - 충돌 처리 방식 (개별 체이닝, 오픈 어드레싱) 파이썬 딕셔너리는 해시 테이블을 기반으로 한 자료형으로, 충돌 해결을 위해 오픈 어드레싱 방식을 사용합니다. 이를 통해 메모리 할당 오버헤드를 줄이고, 성능 저하를 막기 위해 로드 팩터를 낮게 설정하여 최적화를 이루고 있습니다.  충돌 (Collision)해시 함수가 아무리 좋아도 충돌(Collision)은 피할 수 없습니다.예를 들어, 그림 1에서 윤아와 서현의 해시 값이 모두 2로 같아 충돌이 발생했습니다.이렇게 충돌이 발생했을 때는 어떤 방법으로 이를 처리할 수 있을까요?우선 개별 체이닝(Separate Chaining) 방식을 살펴보겠습니다.  1. 개별 체이닝 (Separate Chaining)우선, 입력 데이터는 아래의 표와 같이 구성되었습니다.해시는 키를 해싱한 결과 값이며, 윤아와 서현의 .. 2024. 11. 1.
[Day4/30] 초보자를 위한 SQL 200제 이 카테고리는 정보문화사의 "초보자를 위한 SQL 200제" 30일 코스를 학습 하면서 실습한 내용입니다.   1. 대소문자 변환 함수 배우기 (UPPER, LOWER, INITCAP)사원 테이블의 이름을 출력하는데, 첫 번째 컬럼은 이름을 대문자로, 두 번째 컬럼은 소문자로 출력하고, 세 번째 컬럼은 이름의 첫 번째 철자는 대문자로 하고 나머지는 소문자로 출력 SELECT UPPER(ename), LOWER(ename), INITCAP(ename) FROM emp UPPER: 대문자로 출력LOWER: 소문자로 출력INITCAP: 첫 번째 철자만 대문자로 출력, 나머지는 소문자로 출력UPPER, LOWER 함수는 테이블 내 특정 문자 데이터를 검색하고자 할 때 데이터가 대문자인지 소문자로 저장되어 .. 2024. 10. 29.
11장. 해시 테이블 (1) - 해시 함수의 이해 해시 테이블 또는 해시 맵은 키를 값에 매핑할 수 있는 구조인, 연관 배열 추상 자료형을 구현하는 자료구조이다. 가장 큰 특징은 대부분의 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1)이라는 점이다.    해시 함수와 해싱의 이해해시 함수는 임의의 크기를 가진 데이터를 고정된 크기 값으로 변환하는 함수입니다.예를 들어, 아래와 같이 다양한 길이의 문자열을 고정된 크기의 해시 값으로 매핑할 수 있습니다:ABC      ->   A112321F -> B1FSR4    -> C3이처럼 입력값을 특정한 값으로 변환하는 역할을 하는 함수를 해시 함수라 합니다.이러한 해시 함수의 결과를 사용해 해시 테이블을 인덱싱하고 데이터를 빠르게 저장하고 검색하는 기법을 해싱이라고 합니다.해싱은 특히 최적의 검색 성능이 .. 2024. 10. 29.
[Day3/30] 초보자를 위한 SQL 200제 이 카테고리는 정보문화사의 "초보자를 위한 SQL 200제" 30일 코스를 학습 하면서 실습한 내용입니다.   1. 비교 연산자 배우기 3 - LIKE이름의 첫 글자가 S로 시작하는 사원들의 이름과 월급 출력SELECT ename, sal FROM emp WHERE ename LIKE 'S%';%는 와일드 카드 - 와일드 카드는 이 자리에 어떠한 철자가 와도 상관없고 철자의 개수가 몇 개가 되든 관계없다는 뜻이다.즉, WHERE ename LIKE ‘S%’는 첫 번째 철자가 S이고, 두 번째 철자가 %인 데이터를 검색하겠다는 뜻%가 특수문자 퍼센트가 아니라 와일드 카드로 사용되려면 이퀄 연산자(=)가 아닌 LIKE 연산자를 사용해야 함      이름의 두 번째 철자가 M인 사원의 이름을 출력S.. 2024. 10. 25.
728x90
반응형

티스토리툴바