1. 리스트 순서를 가진 데이터의 집합을 가리키는 추상자료형. 값의 중복을 허용한다. 순차 리스트 : 배열을 기반으로 구현. : Random access 가능. : 삽입/삭제 연산에 불리. 연결 리스트 : 메모리의 동적할당을 기반으로 구현. : 삽입/삭제에 유리. : 탐색에 불리. 2. 연결 리스트 자료의 논리적인 순서와 물리적인 순서가 일치하지 않을 수 있다. 개별적인 노드를 연결하여 하나의 자료구조를 형성. class Node { T data'; Node link; } node 데이터 필드 링크 필드 : 연결된 노드의 참조값을 저장. head 첫번째 노드에 대한 참조값을 가지고 있음. tail 마지막 노드에 대한 참조값을 가지고 있음. 가. 단순 연결 리스트 다음 노드에 대한 참조값만 가지고 있음. ..

1. Heap 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조. 무언가를 차곡차곡 쌓아 올린 더미 부모의 값은 항상 자식(들)의 값보다… 크거나 같은 최대 힙(Max heap) 작거나 같은 최소 힙(Min heap) 데이터의 삽입과 삭제는 모두 O(log⁡N)이 소요. (완전 이진 트리일 때) 가. 데이터 삽입 가장 끝의 자리에 노드를 삽입한다. 그 노드와 부모 노드를 서로 비교한다. 규칙에 맞으면 그대로 두고, 그렇지 않으면 부모와 교환한다. 규칙에 맞을 때까지 반복한다. 나. 데이터 삭제 최댓값 혹은 최솟값이 저장된 루트 노드만 제거할 수 있다. 루트 노드를 제거한다. 루트 자리에 가장 마지막 노드를 삽입한다. 올라간 노드와 그의 자식..

1. Stack import java.util.Stack; Stack stack = new Stack(); push() : 삽입 pop() : 삭제 peek() : 조회 isEmpty() : 비었? size() : 크기 Stack underflow와 overflow를 조심하자. 2. Queue import java.util.Queue; Queue queue = new ArrayDeque(); // //또는 Queue queue = new LinkedList(); Java의 java.util.Queue는 interface다. 구현체로는 대표적으로 ArrayDeque 또는 LinkedList를 사용한다. 대부분의 상황에선 LinkedList보다는 ArrayDeque를 사용하자. ArrayDeque 양쪽 끝에..

종류 설명 기호 시간 복잡도 순열 N개의 원소 중 R개의 원소로 순서를 가진 부분집합을 만드는 경우의 수 nPr O(N!) 조합 N개의 원소 중 R개의 원소로 부분집합을 만드는 경우의 수 nCr O(n! /( r! x (n-r)!)) 부분집합 N개의 원소로 부분집합을 만드는 모든 경우의 수 nHr O(2^N) 집합에 포함된 원소들을 선택하는 것. 멱집합 (Power set) 주어진 집합의 모든 부분 집합들로 구성된 집합 원소들의 그룹에서 최적의 부분 집합을 찾는 문제가 많다. [알고리즘] 5215. 햄버거 다이어트 0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 민기가 좋아하는 햄버거를 먹으면서도 다..

0. 문제 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 1. 문제 이해 최악의 경우 : 가정집(2 * 50), 치킨집(13 Combination 7 = 13! /(6! * 7!) = 1716) → 171,600 연산 171,600 연산은 아주 여유롭다. (1억 번 연산을 1초라고 가정) 완전탐색으로 푼다. 2. 제출 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; imp..

0. 문제 1244번: 스위치 켜고 끄기 첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩 www.acmicpc.net 1. 문제 이해 2. 제출 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static char[] switches; public static int swi, stu; public static void main(String..

종류 설명 기호 시간복잡도 순열 N개의 원소 중 R개의 원소로 순서를 가진 부분집합을 만드는 경우의 수 nPr O(N!) 조합 N개의 원소 중 R개의 원소로 부분집합을 만드는 경우의 수 nCr O(n! / (r! x (n-r)!)) 부분집합 N개의 원소로 부분집합을 만드는 모든 경우의 수 nHr O(2^N) 1. 순열 가. 반복문 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Permutation { static int N, R=3; static int[] m..

1. Lamda 표현식 public class SamTest { SamTest(){ Sam s = new Sam(); InterImpl impl = new InterImpl(); s.m1(impl); } public static void main(String[] args) { new SamTest(); } } public class Sam { void m1 (Inter inter) { int res = inter.calc(1, 2); System.out.println(res); } } public class InterImpl implements Inter { @Override public int calc(int a, int b) { return a+b; } } public interface Inter {..