1. JAVA 오늘은 모든 시간을 spring 과제에 쏟았다 대중교통이라는 부모 클래스를 생성하고, 이를 상속받는 버스와 택시 클래스는 만드는 과제였는데, 필드를 오버라이딩 하는 것과 관련해서 뭔가 잘 풀리지 않는 느낌이었다 과제의 요구사항은 충분히 맞출 수 있을 것 같은데, 바람직하게 코드를 구성해서 완성해가고 있는 것인지에 대한 의문이 든다 나의 판단으로는 객체 생성할 때 사용자가 필드에 해당하는 값들을 지정해서 넣는 형태가 아니고 상당 수의 필드값의 디폴트 값이 자식 클래스끼리 차이가 있다보니, 일단 자식 클래스에서 그냥 새롭게 필드를 정의해서 덮어쓰는 식으로 진행했다 그 과정에서 배운 것: 자식 클래스에서 덮어쓴 필드의 getter setter 메소드는 오버라이딩 해야 원하는 결과가 나온다 부모 ..
leetcode
1. JAVA 우려하던 대로 파이썬에 너무 익숙해져 있어서 코테 문제 푸는데는 너무 별로인 것 같다 자료형이 너무 세분화 되어있고, 당연히 그에 따른 메소드도 많은데, 기능은 훨씬 적은듯 싶다 그래도 자바에 더 익숙해지는 것에는 도움이 되지 않을까 싶고, 코테는 따로 파이썬으로 공부하려 한다 타의 반으로 달리기반에 들어오신 분들이 두 분 계셔서 좀 얼탔는데, 앞으로 방법을 잘 생각해봐야겠다 내 풀이 코드 설명하는 것을 좀 더 듣는 입장에서 이해가 잘 가도록 하고 싶다 2. IntelliJ 깃헙과 연동하는 방법 다시 한번 복습 share project on github -> 프로젝트 폴더 우클릭 후 깃 선택한 후 commit directory 프로젝트 시작 세팅 복습: JDK 연결 -> src 안에 클래스..
다이나믹 프로그래밍: 문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해뒀다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘 최적 부분 구조: 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성 대부분의 재귀 알고리즘은 최적 부분 구조 문제를 풀 수 있음 중복된 하위 문제들의 결과를 저장해뒀다가 풀이해나감 알고리즘 풀이 가능한 문제들의 특징 풀이 가능한 문제 및 알고리즘 다이나믹 프로그래밍 - 최적 부분 구조 - 중복된 하위 문제들 - 0-1 배낭 문제 - 피보나치 수열 - 다익스트라 알고리즘 그리디 알고리즘 - 최적 부분 구조 - 탐욕 선택 속성 - 분할 가능 배낭 문제 - 다익스트라 알고리즘 분할 정복 - 최적 부분 구조 - 병합 정렬 - 퀵 정렬 다익스트라 알고리즘 - 최적 ..
분할 정복: 다중 분기 재귀를 기반으로 하는 알고리즘 디자인 패러다임 직접 해결할 수 있을 정도로 간단한 문제가 될 때 까지 문제를 재귀적으로 쪼개나간 다음(분할), 그 하위 문제의 결과(정복)들을 조합하여 원래 문제의 결과로 만듦(조합) 재귀를 활용하는 대표적인 알고리즘, 최적 부분 구조 169. Majority Element - 브루트 포스 -> 하나하나 count() 메소드로 세다가 과반수인 요소 나오면 리턴 - 다이내믹 프로그래밍 -> 리스트 순회하며 처음 출현한 요소는 count()메소드로 세고, 나왔던 요소는 과반수인지 확인 - 분할 정복 -> 재귀적으로 쪼갠 후 과반수 후보 하나만 상위로 계속 리턴 ※ 비교 연산자로 true | false 반환하여 1 | 0으로 활용 - 리스트를 정렬하면 정..
그리디 알고리즘: 글로벌 최적을 찾기 위해 각 단계에서 로컬 최적의 선택을 하는 휴리스틱 문제 해결 알고리즘 대부분 뛰어난 결과를 도출하지 못하지만, 드물게 최적해 보장 최적해를 찾을 수 있으면 그것을 목표로 삼고, 그것이 어렵다면 주어진 시간 내에 최적에 가까운 해를 찾음 탐욕 선택 속성 + 최적 부분 구조 에 해당하는 문제에 좋다 탐욕 선택 속성: 앞의 선택이 이후 선택에 영향을 주지 않는 것 최적 부분 구조: 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우 예) 다익스트라, 허프만 코딩, ID3 DP vs Greedy DP: 하위 문제에 대한 최적 솔루션을 찾고, 이 결과들을 결합한 정보로 전역 최적 솔루션 선택 Greedy: 각 단계마다 로컬 최적해를 찾는 문제로 접근..
슬라이딩 윈도우: 고정 사이즈의 윈도우가 이동하며 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘 정렬 여부와 관계없이 사용 좌 또는 우 한 방향으로만 이동 교과서에 정의된 내용이 아니며, 투 포인터와 혼용하여 쓰기도 하고, 원래 네트워크에서 사용되던 알고리즘 이름 정렬 여부 윈도우 사이즈 이동 투 포인터 대부분 O 가변 좌우 포인터 양방향 슬라이딩 윈도우 X 고정 좌 또는 우 단방향 239. Sliding Window Maximum - 브루트 포스 - 큐로 최적화 -> 윈도우 이동하여 최댓값 계산 시, 이전 윈도우의 최댓값이 빠질 때만 새로 계산 ※ 고정된 윈도우 크기로 탐색하면서 필요한 계산 수행 (가능하면 계산 최소화하여 구현) 76. Minimum Window Substring - 브루..
부울 연산자: NOT, AND, OR (기본), XOR (보조) 기본 연산자를 조합해 보조 연산 가능 XOR: TT, FF 일때는 F 반환, TF, FT 일때는 T 반환 # XOR x = y = True (x and not y) or (not x and y) >>> False 비트 연산자 ~ : (2의 보수) - 1, 십진수로는 -x-1, 부울 변수 True에 적용하면 -1-1 = -2 True & False # Bitwise AND >>> False True | False # Bitwise OR >>> True True ^ True # Bitwise XOR >>> False ~ True # Bitwise NOT >>> -2 # 십진수와 마찬가지로 연산 bin(0b0110 + 0b0010) >>> '0b..
이진 검색: 정렬된 배열에서 타겟을 찾는 검색 알고리즘 값을 찾아내는 시간 복잡도가 O(logn) 704. Binary Search - 재귀로 이진 검색 * 파이썬은 재귀 호출 횟수 제한이 1000번으로 정해져있으므로 유의 (sys 모듈로 변경가능하지만 대부분 지원하지 않음) - 반복으로 이진 검색 - 이진 검색 모듈 bisect - index() * 최악의 경우 O(n)으로, 앞에서부터 탐색하므로 뒤에 위치할수록 느려진다 bisect.bisect(iterable, value)는 bisect.bisect_right(iterable, value)와 같으며 value 값이 iterable에 정렬되어 삽입된다면 위치할 인덱스 값 리턴 -> value 값과 동일한 값이 이미 iterable에 있다면 그 값 우측..
정렬 알고리즘: 목록의 요소를 특정 순서대로 넣는 알고리즘, 대게 숫자식 순서와 사전식 순서로 정렬 버블 정렬(O(n^2)): 배열의 요소를 끝까지 순차적으로 탐색하며 연달아 있는 2개의 요소의 순서가 맞지 않으면 스왑 병합 정렬(O(nlogn)): 배열을 더 이상 분할이 안될때까지 반씩 나누고, 요소들을 정렬하면서 이어붙힌다 대부분의 경우 퀵 정렬보다 느리지만 일정한 속도와 안정 정렬인 점 때문에 많이 쓰인다 퀵 정렬(O(nlogn)): 분할 정복 알고리즘에 피벗 개념을 추가해 피벗보다 작으면 왼쪽, 크면 오른쪽에 배치되게 분할 이미 정렬된 배열이 입력되는 등의 비효율적인 상황에서는 O(n^2) 가장 간단한 분할 알고리즘인 로무토 파티션은 피벗이 가장 오른쪽 요소 안정 정렬: 입력된 순서가 다른 기준으..
트라이: 검색 트리의 일종으로 일반적으로 키가 문자열인, 동적 배열 또는 연관 배열을 저장하는 데 사용되는 정렬된 트리 자료구조 특히 자연어 처리 분야에서 문자열 탐색을 위한 자료구조로 널리 쓰인다 검색을 뜻하는 'retrieval'에서 따옴 다진 트리의 형태 각 문자열 길이만큼만 탐색하면 원하는 결과 찾을 수 있다 208. Implement Trie (Prefix Tree) - TrieNode 클래스 생성해 딕셔너리로 노드 값 정보, 불리안으로 해당 노드에서 단어 완성 여부 정보를 각 노드에 담는다 -> 삽입이나 검색하려는 문자열 갯수만큼 반복하여 각 노드의 딕셔너리 확인하며 필요한 작업 수행 336. Palindrome Pairs - 부르트 포스 -> 시간 초과 O(n^2) - 트라이 구현 -> 입력..
