전체 글

[선형자료구조] 해시테이블

| 요약 종류 구분 내용 언제 쓰는 게 좋을까 HashTable 특징 - 해싱 함수를 통해 키 -> 해시로 변환한다 - key + value - 특정 키와 값을 연결할 때(알파벳-단어, 사전, 전화번호부) - 중복을 제거해야할 때(전체 명단 중 투표 여부 확인) 장점 - 해시 충돌이 없을 때 검색, 삽입, 삭제가 빠르다 (시간복잡도 : 평균 O(1), 최악 O(n)) - 보안성이 높다 (Key와 Hash간의 연관성X) - 데이터 캐싱에 자주 사용된다. - 중복 제거에 유리하다. 단점 - 해시 충돌 : key1과 key2가 해시함수를 거쳐 동일한 해시값(공간)을 가지는 상태 - 공간 복잡도가 커진다 - 순서가 있는 경우에는 맞지 않는다 - 해시 함수 의존도가 높다 - 해시 테이블은 키와 값을 대응시켜 저장..

[선형자료구조] 스택, 큐, 데크

| 스택 종류 구분 내용 언제 쓰는 게 좋을까 Stack 특징 - 후입선출(LIFO) - top / bottom - push, pop, peek - 데이터가 입력된 순서의 역순으로 처리되어야 할 때 Ex. - 함수 콜스택,역추적,인터럽트 처리 - 재귀, DFS - 괄호 검사, 후위 연산, 문자열 역순출력, 실행취소 장점 - top을 통한 접근, 삽입, 삭제가 빠르다. (시간복잡도 O(1)) 단점 - top 이외의 데이터에 접근 불가(탐색x) - 스택은 마치 옷을 겹겹히 쌓듯 데이터를 쌓아 올렸다가 맨 위에서부터 꺼내는 구조이다. - 스택에 대한 알고리즘 문제를 보면, "괄호 검사", "후위 연산", "문자열의 역순 출력", "실행 취소"와 같이 [ 넣었다가 위에서부터 빼는 행위 ]를 통해 문자열의 특정 ..

[선형자료구조] 연결리스트

| 요약 종류 구분 내용 언제 쓰는 게 좋을까 LinkedList 특징 - 각 노드가 연결된 상태 - 각 노드의 메모리 주소는 항상 연속적이지 않다. - head / tail (양방향 이상) - 자료의 삽입과 삭제가 많은 경우 장점 - 데이터의 삽입 및 삭제가 잦을 때 유리 * 삽입, 삭제 시 새로운 배열 생성 없이 링크만 연결한다. 단점 - 특정 인덱스를 조회하는 데 시간이 O(n)만큼 소요된다. * 처음~끝까지 인덱스를 돌기 때문에 Array보다 느리다. 양방향 - 각 노드가 prev / next 두 가지의 연결점을 가진다. 원형 - head -> tail -> head 식으로 원형으로 연결된 상태 - 연결리스트는 각 노드가 연결된 상태로, 삽입과 삭제가 용이하다. - 다만, 연결리스트는 조회에는 취..

객체지향 언어의 특징 2_상속 (재사용 + 확장)

| 상속 (재사용 + 확장) - 부모 - 자손의 상속 관점 보다는, 재사용과 확장으로 접근하는 것이 좋다 - 상속은, 상위 클래스의 특성을 하위 클래스에서 재사용하고, 거기에 덧붙여 확장할 수 있는 것을 말한다. - 관계 : 상위 - 하위 / 슈퍼 - 서브 * 상위로 갈수록 추상화, 일반화되며 * 하위로 갈수록 구체화, 특수화된다. - 상속을 표현하는 문장 구분 - 설명 포함 has a 클래스 내에서 인스턴스를 형성하여 사용 상속 is a kind of 클래스를 extends (확장하다) 구현 is able to 인터페이스를 implements (구현하다) - 오버라이딩 : 상속 관계에 있는 상위 클래스로부터 물려 받은 메소드를 재정의한 것 | 상속의 장단점 장점 - 모듈화*를 통한 재사용 - 유지보수가..

객체지향 언어의 특징 1_추상화 (모델링)

| 추상화 (모델링) - 현실 세계의 객체에서 필요한 부분만 뽑아 클래스로 만드는 작업을 말한다. 추상화란 구체적인 것을 분해하여 관심 영역에 있는 특성만 가지고 재조립하는 것(= 모델링) [출처] 스프링 입문을 위한 객체 지향의 원리와 이해 | 추상화가 모델링인 이유 관심 영역(앱의 경계)에 따라 클래스 모델링이 달라진다. - 현실 세계에서 물리적으로는 동일한 실체에 대해서도 관심 영역(여기서는 애플리케이션에 적용할 영역)이 어디냐에 따라서, 클래스 모델링이 달라진다. Ex. 사람(객체)을 동물로 본다면 "다리 갯수", "자손 생식 방식" 등을 보겠지만, 고객으로 본다면 "연령대", "지출금액" 등을 볼 것이다. | 추상화의 예시 [1] 상속을 통한 추상화와 구체화 - 상속 관계에서 상위 클래스로 올라..

객체지향 프로그래밍이란?

| 객체지향 프로그래밍 / 절차지향 프로그래밍 절차 지향 프로그래밍(PP) 객체 지향 프로그래밍(OOP) 특징 일련의 동작(모듈, 함수)를 순차적으로 실행 객체(속성 + 기능) 간의 상호작용을 이용 포커스 명령어의 순서와 흐름 데이터의 속성(필드)과 기능(메서드) 장점 컴퓨터의 처리구조와 비슷해 속도가 빠르다 재사용성(상속), 유지보수 용이, 자연스러운 모델링* 단점 규모가 커질 수록, 추가 개발 및 유지보수 어려움 느린 개발 속도와 실행 속도. 높은 난이도 * 객체지향 프로그래밍은 하나의 방법론이지, 그것이 언어나 제품을 의미하는 것은 아니다. * OOP나 PP 외에 CBD(Component-based development), SOA(Service-orient development)등 프로그래밍 방법론..

[선형자료구조] 배열과 ArrayList

| 요약 종류 구분 내용 언제 쓰는 게 좋을까 Array 특징 - 정해진 크기만큼 공간 할당 - 데이터가 연속적으로 하나씩 저장되어 있다. - 데이터와 인덱스가 1 : 1로 매칭 - 많은 양의 데이터를 다룰때 - 특정 위치 자료를 빠르게 선택할때 장점 - 인덱스를 통해 빠르게 데이터에 접근할 수 있다. 단점 - 길이를 미리 설정해야 한다. ArrayList 특징 - 가변 길이 배열 - 삽입 & 삭제 시, 배열을 새로 생성하고 복사한다. 장점 - 크기가 고정되어 있지 않다 (유동적) 단점 - 처음 또는 중간에 데이터를 삽입하거나 삭제할 때마다 배열을 새로 생성&복사하거나, 데이터를 모두 앞으로 미뤄야 한다. | ArrayList은 어떻게 가변적으로 데이터를 관리하나 - ArrayList는 java.util..

자릿수 - 자릿수와 경우의 수

| 자릿수와 경우의 수 (1) X진수의 K자릿수에 대한 모든 경우의 수 어떤 연속된 10진수 수 3개에 대한 배열이 있다고 가정할 때, 각 자리에 올 수 있는 수의 범위는 0 ~ 9이다. 0 0 0 0 0 1 0 0 2 0 0 3 0 0 4 0 0 5 0 0 6 0 0 7 0 0 8 0 0 9 ..... (생략) 10진수의 세 자릿수에 대한 모든 경우의 수는 아래와 같다 --> 10 x 10 x 10 = 1000 (곧, 000 ~ 999) 결국 x 진수의 k자릿수에 대한 모든 경우의 수는 --> x * x * x.... = x^k (자릿수 하나당 0 ~ x-1) (2) x진수의 각 자릿수 하나당 0 ~ x-1 범위를 가지며, x - 1를 넘어서면 올림이 이루어진다. - 10진수일 때 1 1 8 1 1 9..

소수판별법 - 에라토스테네스의 체

| 합성수와 소수 합성수 나누어떨어지는 수가 하나라도 존재하는 수 ex. 100 = 1 x 100, 2 x 50, 4 x 25, 5 x 20, 10 x 10... 소수 오직 1과 자기 자신만으로 나누어떨어지는 수 ex. 3 = 1 x 3 소수에 관한 알고리즘 문제는 보통 아래의 세가지가 있다고 하는데요. 1. 자연수 N이 소수인지 판별하거나, 2. 1~N까지 중 소수의 갯수를 구하거나 3. 1 ~ N 까지의 소수를 나열하는 이 중에서 먼저 1.자연수 N이 소수인지 판별하는 법을 이야기해 보려고 합니다. | N을 2부터 N - 1 까지 모두 나누기 [1] 소수는 1과 자기 자신을 제외한 다른 수로는 나누어떨어져서는 안됩니다. 그것을 판별하기 위한 코드는 아래와 같은데요. 2부터 N - 1가 N의 약수인지 ..

[백준 11660] 구간 합 구하기 5

| 시작하기 전에 지난번에는 일차원 배열에 있는 데이터에 대한 구간합을 구하는 법을 다루었다면, 이번에는 이차원 배열에 있는 데이터에 대한 구간합을 구하는 법을 다루어보았다. 🔖 일차원 구간합에 대한 포스팅은 아래에 [백준 11659] 구간합 🛎 11659 구간합 | 문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. | 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N why-dev.tistory.com 🛎 11660 구간 합 구하기 5 | 문제 N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다. 예를 들어, N ..