전체 글

버블 정렬, 선택 정렬, 삽입 정렬

버블 정렬 배열의 첫 원소부터 순차적으로 진행하며, 현재 원소가 그 다음 원소의 값보다 크면 두 원소를 바꾸는 작업을 반복한다. 정렬하고자 하는 배열 안에서 교환하는 방식으로 다른 메모리 공간이 필요하지 않고 (제자리 정렬), 중복된 값을 입력 순서와 동일하게 정렬한다. (안정 정렬) 시간 복잡도는 최악, 최선, 평균 모두 O(n^2)으로 비효율적이며, 정렬되지 않은 원소가 정렬됐을 때의 자리로 가기 위해서 스왑 연산이 많이 일어난다. 알고리즘 def bubble_sort(arr): for i in range(len(arr) - 1, 0, -1): for j in range(i): if arr[j] > arr[j - 1]: arr[i], arr[i + 1] = arr[i + 1], arr[i] 조금 더 ..

22943 수

문제 https://www.acmicpc.net/problem/22943 22943번: 수 0부터 9까지 $K$가지의 숫자를 한 번씩만 사용하여 만들 수 있는 수 중 아래 조건을 모두 만족하는 수들의 개수를 구해보자. 단, 수의 맨 앞에는 0이 올 수 없다. 즉, 0143는 불가능하다. 서로 다른 www.acmicpc.net 접근 문제에서 어떤 k와 m이 주어지든지 간에 소수, 소수의 합으로 만들 수 있는 수, 소수의 곱으로 만들 수 있는 수는 정해져 있으므로 에라토스테네스의 체를 이용하여 소수를 구한다. 구해진 소수들을 이용해서 덧셈과 곱셈으로 만들 수 있는 수들을 미리 구해놓고 백트래킹으로 해당 수가 조건을 만족하는지 확인했다. 풀이 def solve(num): global ans if len(num..

4803 트리

문제 https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 접근 주어진 연결정보에 따라 노드를 분리하고 각 노드 집합에 대해 사이클이 발생하는지 확인하면 트리인지 아닌지 판별할 수 있으므로 유니온 파인드를 이용했다. 만약 사이클이 생긴다면 한 노드에서 다른 노드로 갈 수 있는 경로가 2개 이상이 되므로, 노드 집합의 원소의 개수가 k라고 한다면 노드 집합의 간선의 개수가 k-1보다 크다는 뜻 또한 노드를 연결정보에 따라 분리했으므로..

객체지향 설계와 스프링

SOLID - 좋은 객체지향 설계의 5가지 원칙 SRP (단일 책임 원칙) 한 클래스는 하나의 책임만 가져야 한다. 변경이 있을 때 파급 효과가 적으면 단일 책임 원칙을 잘 따른 것 OCP (개방-폐쇄 원칙) 소프트웨어 요소는 확장에는 열려 있으나 변경에는 닫혀있어야 한다. 만약 클라이언트가 구현 클래스를 직접 선택하는 경우, 구현 객체를 변경하면 클라이언트 코드를 변경해야 한다. (OCP 위반) 따라서 객체를 생성하고 연관관계를 맺어주는 별도의 조립, 설정자가 필요하다. LSP (리스코프 치환 원칙) 프로그램의 객체는 프로그램의 정확성을 깨뜨리지 않으면서 하위 타입의 인스턴스로 바꿀 수 있어야 한다. 다형성에서 하위 클래스는 인터페이스 규약을 다 지켜야한다는 것을 의미 ISP (인터페이스 분리 원칙) ..

19641 중첩 집합 모델

문제 https://www.acmicpc.net/problem/19641 19641번: 중첩 집합 모델 S번 노드가 루트 노드일 때, 번호가 가장 낮은 노드부터 오름차순으로 방문해서 중첩 집합을 구성했을 때, 각 노드의 번호 left 필드와 right 필드를 출력한다. 총 N개의 줄에 걸쳐 i번째 줄에 i번 www.acmicpc.net 접근 각 노드에 대해 방문하는 순서가 필요해서 dfs를 이용했다. dfs의 매개변수로 순서를 넘길 경우 같은 레벨에 있는 노드들을 처리하기가 힘들어서 공유변수 order를 이용해서 처리했다. 주의할 점은 노드를 오름차순으로 방문하므로, 연결정보를 입력받은 후 정렬해줘야 한다. 풀이 각 노드를 방문하면 order를 1 증가시키고 left 값을 기록한다. 해당 노드와 연결된 ..

트라이

트라이 (Trie) 각 노드에 문자를 저장하는 트리 기반의 자료구로, 트리를 아래쪽으로 순회하면 단어 하나가 나온다. 트라이는 길이가 K인 문자열이 주어졌을 때 O(K) 시간에 해당 문자열이 유효한 접두사인지 확인할 수 있다. 먄악 트리에서 연관된 접두사를 반복적으로 검색해야 하는 경우, 트리의 현재 노드를 참조값으로 넘긴다면 매번 검색할 때마다 루트에서 시작할 필요없이 자식 여부만 확인하면 된다. 구현 # Node 클래스 # key: 해당 노드의 문자, child: 자식 노드 # data: 문자열이 끝나는 위치를 알려주는 역할 (해당 노드에서 끝나는 문자열이 없으면 None) class Node: def __init__(self, key, data=None): self.key = key self.dat..

힙과 우선순위 큐

힙 (Heap) 힙은 힙의 특성을 만족하는 완전 이진 트리로, 최소 힙 기준으로 각 노드의 원소는 항상 자식 노드의 원소보다 작거나 같아야 한다. 최소 힙의 부모 노드는 항상 자식 노드보다 크거나 같지만, 부모-자식 간의 관계만 정의되어 있을 뿐 좌우 관계에 대한 정의는 하지 않기 때문에 힙은 정렬된 구조는 아니다. 인덱스 완전 이진 트리 형태인 이진 힙은 배열에 빈틈없이 배치가 가능하며, 대개 트리의 배열 표현의 경우 계산의 편의성을 위해 0번째 인덱스는 비워두고 1번째 인덱스부터 사용한다. i번째 노드에 대해 부모 노드의 인덱스는 i // 2, 왼쪽 자식 노드의 인덱스는 2 * i, 오른쪽 자식 노드의 인덱스는 2 * i + 1로 계산된다. 원소 삽입 (Python) 최소 힙에 원소를 삽입할 때는 언..

22871 징검다리 건너기 (large)

문제 https://www.acmicpc.net/problem/22871 22871번: 징검다리 건너기 (large) $N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다. 항상 오른쪽으 www.acmicpc.net 접근 22869 징검다리 건너기 (small) 문제랑 조건은 똑같고, N번째 돌까지 갈 수 있는 모든 경로 중 K의 최솟값을 찾는 문제이므로 파라메트릭 서치 즉, 이분탐색과 DP로 풀이했다. 풀이 DP 과정은 22869번과 동일하고 lt는 0으로 rt는 10 ** 9으로 초기화한 후 이분탐색으로 적절한 K값중 가장 작은 값을 구했다..

22869 징검다리 건너기 (small)

문제 https://www.acmicpc.net/problem/22869 22869번: 징검다리 건너기 (small) $N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다. 항상 오른쪽으 www.acmicpc.net 접근 1번째 돌에서 N번째 돌까지의 돌들에 대해, 돌을 한번 건너갈 때마다 쓸 수 있는 힘이 K를 넘지 않는 경로가 존재하기만 하면 되는 문제 따라서 i번째 돌까지 이동하는 데 필요한 힘의 최댓값의 최솟값을 저장할 배열을 만들고 DP로 풀이했다. 풀이 d[i]를 i번째 돌까지 이동하는 데 필요한 힘의 최댓값의 최솟값으로 정의했을 때..