본문 바로가기

분류 전체보기

 (386)
[알고리즘] 세그먼트 트리(Segment Tree) 1. 세그먼트 트리 세그먼트 트리란 특정 구간의 합(최솟값, 최댓값, 곱 등)을 구할 때 사용하는 자료구조이다. 문제 상황은 다음과 같다. (백준 설명) 배열 A가 있고, 여기서 다음과 같은 두 연산을 수행해야하는 문제를 생각해봅시다. 1) 구간 l, r (l ≤ r)이 주어졌을 때, A[l] + A[l+1] + ... + A[r-1] + A[r]을 구해서 출력하기 2) i번째 수를 v로 바꾸기. A[i] = v 수행해야하는 연산은 최대 M번입니다. 세그먼트 트리나 다른 방법을 사용하지 않고 문제를 푼다면, 1번 연산을 수행하는데 O(N), 2번 연산을 수행하는데 O(1)이 걸리게 됩니다. 총 시간 복잡도는 O(NM) + O(M) = O(NM)이 나오게 됩니다. N과 M이 매우 큰 경우, 너무 오랜 시간..
[boj] 백준 1194 달이 차오른다, 가자 (c++) - 비트마스킹, BFS [문제] https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net [풀이] 보통의 BFS, DFS 문제에서 추가로 고려해줘야 할 부분은 크게 다음 2가지이다. 1) 똑같은 위치라도 key가 없는 상태에서 방문한 것과 key가 있는 상태에서 방문했을 때가 다르다. 이를 구분해주기 위해 visited[][][key]와 같이 3차원으로 선언하여 현재 소지한 키의 상태를 저장할 수 있도록 한다. 2. 6개의 열쇠 소지 여부에 대한..
[boj] 백준 1766 문제집 (c++) - 위상정렬 [문제] https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net [풀이] 위상정렬 문제이다. 다만, 가능하면 쉬운 문제부터 풀어야 한다는 3번째 조건을 만족시키기 위해(문제 번호가 작을수록 쉬운 문제) 우선순위 큐를 사용한다. 오름차순으로 출력되어야 하므로 -1을 곱해서 우선순위 큐에 넣어준다. [코드] #include #include #include #include #include using namespace::std;..
[boj] 백준 2357 최솟값과 최댓값 (c++) - 세그먼트 트리 [문제] https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net [풀이] 세그먼트 트리(segment tree)를 사용해서 푸는 standard 문제이다. 세그먼트 트리는 특정 구간에 대한 연산을 효율적으로 하기 위해 사용되는데, 보통은 배열의 부분합(구간합)을 저장해놓고 쓴다. 이 문제에서는 최솟값과 최댓값을 구하기 위해 구간의 최솟값과 최댓값을 저장하도록 하였다. (세그먼트 트리도 차후에 알고리즘에 정리해야겠다..
[boj] 백준 2098 외판원 순회 (c++) - TSP(비트마스킹, dp, dfs) [문제] https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net [풀이] TSP(Traveling Salesperson Problem)이라는 외판원 순회 알고리즘이 따로 존재할 정도로 유명한 문제라는데...처음 봤다. 비트마스킹도 익숙치 않아서 여러 블로그 깨작거리면서 갱신히 풀었다. 알고리즘 카테고리에 한 번 정리해야 할 것 같다. TSP는 어떠한 도시에서 출발하여 다른 모든 도시들을 거쳐 출발 했던 도시로 다시..
[CNN] Real-time Facial Emotion Recognition using CNN (웹캠을 이용한 실시간 표정 감지 - with opencv, tensorflow.js) (동글(동화 그루) 프로젝트에서 웹캠을 이용해 실시간으로 emotion detection을 하는 기능을 만들기 위한 과정을 정리해봤다.) 1. Colab에서 Facial Emotion Recognition 학습시키기 먼저 CNN으로 표정 데이터셋을 학습시키도록 하자! 학습에 사용한 데이터는 FER2013 데이터셋으로 angry, disgust, fear, happy, sad, surprise, neutral 7가지의 감정으로 라벨링되어있다. 모델 학습은 다음과 같은 순서로 진행되었다. 0) 필요한 라이브러리 가져오기 1) 이미지 전처리(preprocessing) 2) SMOTE 기법을 적용하여 Over-sampling 3) image augmentation 4) 모델 정의 5) 모델 훈련 6) 모델 평가..
[spring-core-3] 싱글톤 컨테이너 인프런 [스프링 핵심 원리 - 기본편]을 정리한 내용입니다. 싱글톤 컨테이너 문제 정의: 기존의 스프링이 없는 순수한 DI 컨테이너인 AppConfig는 요청을 할 때마다 객체를 새로 생성해도 반환해줬다. 이 경우 트래픽이 클 수록 많은 객체가 생성되고 소멸되며 메모리 낭비가 심한 문제가 있고, 따라서 해결하기 위해 싱글톤 패턴을 사용한다. 싱글톤 패턴 클래스의 인스턴스가 딱 1개만 생성되는 것을 보장하는 디자인 패턴. //1. static 영역에 객체를 딱 1개만 생성해둔다. private static final SingletonService instance = new SingletonService(); //2. public으로 열어서 객체 인스턴스가 필요하면 이 static 메소드를 통해서만 조회하도..
[spring-core-2] 스프링 컨테이너와 스프링 빈 인프런 [스프링 핵심 원리 - 기본편]을 정리한 내용입니다. 스프링 컨테이너 ApplicationContext ac = new AnnotationConfigApplicationContext(AppConfig.class) - ApplicationContext를 스프링 컨테이너라 한다. - ApplicationContext는 인터페이스이고, AnnotationConfigApplicationContext는 구현체이다. 즉, 역할과 구현으로 나누어 다형성을 적용한 것이다. - 역할과 구현으로 나누었기 때문에 스프링 컨테이너는 xml 기반으로 만들 수도 있고, 애노테이션 기반으로 자바 설정 클래스를 만들 수도 있다. 다양한 설정 형식 지원 - 자바코드, XML - 애노테이션 기반 자바 코드 설정 사용 Applic..

티스토리툴바