0m1n's Develog

문제 출처 : https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 풀이 알파벳을 숫자로 치환했을때, 주어진 단어의 합의 최댓값을 구하는 문제이다. 브루트포스 방식으로 모든 숫자를 대입(dfs)해 정답을 구하는 방식도 있으나, 그리디 알고리즘으로 정답을 구하는 방법이 빠르다. 그리디 알고리즘 + @? 그렇다면 어떤 방식으로 해결해야 할까? 단순히 큰 자리수에 큰 숫자를 대입한다고 생각하면 아래와 같은 상황에서는 처리할 방법이 애매해진다. ABC..

문제 출처 : https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 연속된 수의 부분합 중 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 문제이다. 단순하게 합을 구한다고 해서 정렬이나 priority_queue를 쓰면 안된다. 연속된 수의 부분합이기 때문이다. 그렇다고 브루트포스로 구현하면 시간초과가 발생한다. 어떻게 해야 할까? 바로 투포인터 알고리즘을 사용하면 된다. 투포인터 알고리즘 이름 그대로 배열을 이동하는 포..

협업 시 팀원이 세팅해 놓은 QueryDSL 관련 코드를 깃허브로 받아 실행할때 보통 일어난다. 이때 Gradle에서 compileQuerydsl을 실행시켜주면 해결된다!

문제 출처 : https://www.acmicpc.net/problem/1027 1027번: 고층 건물 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작) www.acmicpc.net 풀이 고층 빌딩 리스트가 주어지는데, 가장 많은 빌딩이 보이는 수를 출력하는 문제이다. 이때 A에서 B빌딩이 보이려면 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야 한다. 처음에 두 선분을 구하고 사이에 있는 빌딩의 높이가 그 선분을 건드리는지 확인해봐야하나 고민했지만, 결론은 기울기였다. 2중 for문을 돌며 모든 빌딩과 다른 빌딩을 확인해 해당..

Redis를 어디서 들어봤지만 대충 DB관련된 툴이라고 들어본 정도가 다인 경우가 많다. 오늘은 Redis와 관련해서 알아야 하는 Cache에 대해서 정리해보았다. Redis Remote dictionary Server의 약자로, 기존의 데이터를 빠르고 쉽게 데이터를 접근할 수 있는 시스템이다. Redis의 특징은 아래와 같다. Remote dictionary Server : 직역하면 외부 자료구조 서버? 느낌으로 와닿을 수 있다. Database, Cache, Message broker In-memory Database(Cache) 빠른 성능 평균 작업속도 < 1ms 초당 수백만 건 작업 가능 다양한 자료구조 제공 이렇게 Redis는 가장 유명한 software caching 솔루션인데, 여기서 Cac..

문제 출처 : https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 풀이 맥주 한 박스(20개)를 들고 50m마다 맥주를 한병씩 마시는데, 편의점에 방문하면 맥주를 채울 수 있다. 집에서 페스티벌 좌표까지 이동할 수 있는지 묻는 문제이다. 직관적으로 풀면 해결되는 문제였다. 먼저 맥주 20개를 가지고 있으니 최대 1000m까지 이동할 수 있다. bfs로 풀면 이제 고려해야 할 경우는 2가지이다. 1. 1000m 맨해튼 거리 내 편의점이 있으면 ..

문제 출처 : https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 풀이 일년마다 주위(상하좌우)에 물이 있는 개수만큼 빙산이 녹는 방식인데, 빙산이 두개이상으로 분리되는 시간을 구하는 문제이다! (빙산이 다 녹을 때까지 분리되지 않으면 0 출력) 먼저 2차원 배열을 입력받고 1. 4방향 탐색 후 물이 있는개수만큼 빼주기 2. 빙산이 분리되었는지 확인 3. 빙산이 다 녹았는지 확인 을 반복한다. 1. 4방향 탐색 후 물이 있는개수만큼 빼주기 처..

머신 러닝 주어진 데이터를 분석하여 규칙성, 패턴 등을 찾음 → 의미 있는 정보 추출 지도 학습 : 정답이 있는 데이터를 활용해 데이터를 학습시키는 것 회귀 : 연속된 수치 값을 예측 분류 : 이산적인 값을 결과로 출력 비지도 학습 : 종속변수(정답데이터)가 제공되지 않는 데이터에 대한 학습을 처리하는 기법 주로 군집화(클러스터링)에 사용 영상 데이터 픽셀을 머신 러닝 입력으로 사용 안하는 이유 픽셀 값은 매우 민감하게 변화하므로 k-폴드 교차 검증 훈련 데이터를 k개의 부분 집합으로 분할하여 학습과 검증을 반복하는 작업 OpenCV 머신 러닝 클래스는 주로 ml 모듈에 포함되어 있음 StatModel 추상 클래스를 상속 train() - 학습 predict() - 예측 분류 / 회귀에 사용 분류의 경우..

지역 특징 : 영상의 특징 중에서 에지, 직선 성분, 코너 처럼 영상 전체가 아닌 일부 영역에서 추출할 수 있는 특징 코너 검출 방법 해리스 코너 검출 방법 R이 0보다 충분히 큰 양수 : 코너 점, R이 0 가까운 실수 평탄, R < 0 : 에지 하나의 코너 위치에 사용자 지정 임계값보다 큰 픽셀이 여러개 발생할 수 있기 때문 → 비최대 억제 수행 FAST 코너 검출 방법 해리스는 연산 복잡해서 연산 속도가 느림 단순한 픽셀 값 비교를 통해 코너 검출 영상의 모든 픽셀에서 픽셀 둘러싸고 있는 16개의 주변 픽셀과 밝기 비교 16개 중 기준 좌표보다 충분히 밝거나 어두운 픽셀이 9개 이상 연속으로 존재 → 코너 코너 점 주변 픽셀도 코너로 검출하는 경우 많음 비최대 억제 작업 수행(코너 점수 가장 큰 코..

템플릿 매칭 영상에서 작은 크기의 부분 영상 위치를 찾아내고 싶을때 사용 작은 크기의 템플릿 영상을 입력 영상 전체 영역에 대해 이동하면서 가장 비슷한 위치를 수치적으로 찾음 유사도, 비유사도 계산 유사도 → 템플릿과 비슷한 부분에서 값 크게 나옴, 비유사도는 반대 matchTemplate() 사용 템플릿 영상과 입력 영상과의 비교 방식 제곱차 매칭 두 영상이 완벽하게 일치 → 0, 유사하지 않으면 0보다 큰 양수 상관관계 매칭 두 영상이 유사하면 큰 양수, else 작은 값 상관계수 매칭 두 영상을 미리 평균 밝기로 보정 후 상관관계 매칭 유사하지 않으면 0에 가까운 양수 or 음수 정규화된 상관계수 매칭 방법이 좋은 결과 제공 캐스케이드 분류기와 얼굴 검출 유사-하르 필터 집합으로부터 특정 집합 추출..