자료구조, 알고리즘

비선형 자료구조 총정리

보호되어 있는 글입니다.

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

| 요약 종류 구분 내용 언제 쓰는 게 좋을까 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 식으로 원형으로 연결된 상태 - 연결리스트는 각 노드가 연결된 상태로, 삽입과 삭제가 용이하다. - 다만, 연결리스트는 조회에는 취..

[선형자료구조] 배열과 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 ..

[백준 17609] 회문 (팰린드롬)

팰린드롬이란, 앞 뒤가 똑같은 전화번호 문자열을 말한다고 합니다. 단순히 "abba" 문자열이 팰린드롬인가를 확인한다면, [1] 문자열을 거꾸로 뒤집어서 확인하거나 [2] 양끝에 left, right로 커서를 두고 left < right 일때까지 양 끝을 비교해도 되는데요. 물론 우리의 알고리즘은 그렇게로만 끝나지 않기 때문에 더 향상된 버전의 팰린드롬을 만날 수 있었습니다. 제 수준에서 풀만한 것들을 먼저 뽑아보았어요.. 아래 중에서 하나씩 풀어보려 합니다. | 백준 팰린드롬 문제 모음 브론즈 1259 팰린드롬수 바로가기 실버 1213 팰린드롬 만들기 1254 팰린드롬 만들기 17609 회문 바로가기 바로가기 바로가기 골드 1053 팰린드롬 공장 바로가기 🛎 17609 회문 | 문제 회문(回文) 또는 ..

[백준 10434] 행복한 소수 - 소수 구하기 + 행복한 수

행복한 수에 대한 연습문제를 풀다가, 백준에 관련된 문제가 있나 싶어 찾아보았습니다. 행복한 수만 구하는 문제는 아니고, 행복한 소수를 구하는 문제가 있었어요. 그래서 한 번 개념 정리를 먼저 하고 문제를 풀어보고 정리를 하려 합니다. | 행복한 수란? 십진수의 수가 있을 때, 예를 들어 14가 있다고 할 때, 각 자릿수를 제곱한 합은 1^2 + 4^2 = 18 입니다. 다시 29의 각 자릿수를 제곱한 합을 구하면 1^2 + 8^2 = 65 이 과정을 계속하다보면, 64,37,58,89,145,42,20,4,16,37,58,89,145,42.... 이 나오게 되는데요. - 어떤 수는 14처럼 '1이 아닌 중복되는 수'를 지점으로 무한히 동일한 수열이 반복되는 반면, - 어떤 수는 제곱합의 끝이 1이 되면..