개발자로 살아남기

이진 탐색 트리 (Binary Search Tree, BST) 이진 탐색 트리 (Binary Search Tree, BST) 이진 트리의 일종 데이터를 트리에 저장하는 규칙에 따라야 함 노드에 저장된 키 값은 유일해야 함 왼쪽 자식 노드 키 > 부모 노드 키 > 오른쪽 노드 키 삽입할 데이터가 부모 노드보다 작으면 왼쪽, 크면 오른쪽에 삽입 왼쪽과 오른쪽의 서브 트리도 이진 탐색 트리 이진 탐색 트리 구현 방법 삽입 부모 노드와 삽입할 데이터를 비교해서 삽입할 데이터가 더 크면 오른쪽에 추가하고, 더 작으면 왼쪽에 추가한다. 단, 비교할 대상이 없을때까지 내려가야 한다. 탐색 삽입과 마찬가지로 찾고자하는 데이터가 부모 노드보다 작으면 왼쪽, 크다면 오른쪽으로 탐색한다. 단, 탐색 도중 데이터를 찾았거나 ..

버블 정렬 (Bubble Sort) 버블 정렬 (Bubble Sort) 가장 단순한 정렬 알고리즘 인접한 요소와 정렬 기준(오름차순, 내림차순)대로 교환 안정 정렬 (stable sort) : 정렬 후에도 같은 값들 끼리의 순서가 보장됨을 의미 제자리 정렬 (in-place sort) : 데이터에 필요한 공간을 제외하고 추가적인 공간이 필요없음을 의미 정렬한 데이터의 개수가 적을때는 나쁘지 않은 속도를 보임 버블 정렬 방법 (오름차순 기준) 첫 번째 사이클이 끝나면 맨 마지막 값이 정렬되고, 두 번째 사이클이 끝나면 뒤에서 두 번째의 값이 정렬된다. 이같은 과정을 계속 반복하면 최종적으로 정렬이 된다. 버블 정렬의 성능 시간복잡도 최악의 경우 : O(n^2) 최선의 경우 : O(n) 최악의 경우 : 모든..

단순 연결 리스트 단순 연결 리스트 크기가 변경 불가능한 배열의 단점을 극복 (배열은 정적인 메모리 구성) 크기가 정해져있지 않음 (동적인 메모리 구성) 데이터들을 Node로 관리 (Node : data, 다음 노드의 주소값으로 이루어져 있음) 리스트는 데이터의 저장 순서를 유지해야하는 자료구조가 아님 Node 리스트의 구성 필요한 Node들 head : 리스트의 머리를 가리킴 tail : 리스트의 꼬리를 가리킴 cur : 데이터의 조회에 사용됨 head에 데이터 추가 시 장점 : tail 노드가 불필요 단점 : 저장 순서가 유지되지 않음 tail에 데이터 추가 시 장점 : 저장 순서가 유지됨 단점 : tail 노드가 필요 데이터 추가 tail 또는 head쪽에 데이터 추가 후 tail 또는 head가 ..

순차 리스트 순차 리스트 데이터가 메모리에 연속적으로 저장됨 (ex. 배열 등) 장점 1) 인덱스로 데이터에 접근할 수 있으므로 속도가 빠름 단점 1) 배열의 길이가 사전에 정의되어야 함 2) 중간 데이터 삭제 시 해당 인덱스 이후의 값들은 한 칸씩 이동이 발생 설명 삽입 - 보통 배열의 마지막에 데이터가 삽입되며, 삽입 시 배열의 크기도 고려해야 함 - 배열의 중간에 데이터를 삽입하기 위해서는 배열의 길이가 충분한지 확인해야 하며, 삽입된 위치 뒤에 존재하는 모든 데이터들이 한 칸씩 뒤로 이동해야 하므로 중간에 데이터 삽입 시 비효율적 - 시간 복잡도 : O(n) 삭제 - 배열의 중간에 위치한 데이터를 삭제할 경우 해당 위치의 뒤 데이터들은 한 칸씩 앞으로 이동해야 하므로 배열의 크기가 크고 삭제가 빈..

알고리즘 문제를 풀다가 반복문을 이용해 문자열을 합치는 부분이 있었다. 간단한 문제여서 String으로 문자열을 합쳤었는데 다른 사람들의 풀이를 보니 StringBuilder로 문제를 풀었다. 해당 문제를 String과 StringBuilder로 풀어봤는데 속도 차이가 많이 나서 어떤 차이 때문에 그런지 확인해보려고 한다. String String은 불변(immutable)한 객체이며, 한 번 생성되면 내용을 변경할 수 없으며 길이가 정해져 있다. 이러한 특성 때문에 멀티스레드 환경에서 사용하기 적절하다. public class TEST { public static void main(String[] args){ String str = "ABC"; System.out.println("ABC : " + st..

정규표현식이란? 특정 문자열을 처리할 때 사용하는 방법 중 하나 특정 문자열에서 패턴을 검색하거나 치환할 때 사용되며 기존에는 코드로 직접 작성해야 했으나, 이 정규표현식을 이용하면 간단하게 문자열을 처리할 수 있음 ex) 이메일 주소 및 핸드폰 번호 검증 등 입력이 불가능한 문자들이 들어있는지 사전에 확인하여 보안상으로도 유용함 ex) SQL에서 주석으로 표현되는 ' -- 와 같은 문자 확인 Pattern, Matcher 클래스 Pattern 클래스 - 검색 또는 치환할 패턴을 정의(Compile)하는 클래스 Matcher 클래스 - 패턴을 해석해서 문자열이 일치하는지 확인하는 클래스 예제 이메일 주소 검증 - 이메일 주소는 대부분 test@test.com 형태로, 아이디 부분은 영문 대/소문자, @는..