0m1n's Develog

문제 출처 : https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드 워셜 플로이드 워셜 알고리즘을 사용하는 문제이다! 다익스트라와 플로이드-워셜의 차이는 아래와 같다. 다익스트라 : 하나의 정점에서 다른 모든 정점의 최단거리 플로이드 : 모든 노드간 최단거리 플로이드 알고리즘의 프로세스는 아래와 같다. 인접 배열을 구한다. 1번노드를 중간 노드(거쳐가는 노드)로 설정해, 거쳐가는 경우의 비용이 더 작으면 배열을 갱신한다. n번노드까지 반복한..

문제 출처 : https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 풀이 남극의 언어가 anta로 시작되고 tica로 끝난다 -> a c i n t는 필수로 가르쳐야 한다. 즉 K가 5 미만이라면 0을 출력하면 된다. a c i n t는 디폴트로 학습시킨다. 입력 단어에서 anta, tica를 빼고 저장해 시간을 줄일 수 있다. string str = ""; for(int i = 0; i > str; v.push_..

문제 출처 :https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 풀이 bfs로 생각할 수 있으나 다익스트라 개념을 도입해 풀어야하는 문제이다. 벽을 부수는 최소 수를 저장하는 dist 배열을 선언해 조건에 달아주면 된다. 코드 #include #include #include #include using namespace std; int M, N; int arr[101][101]; vector dist(101, vector(101..

문제 출처 : https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 풀이 이 문제는 불과 지훈이의 이동경로를 비교를 해야한다. 따라서 먼저 불의 시간 별 이동경로를 저장하는 배열을 만들어 계산한 뒤, 지훈이가 이동 가능한지 비교한다. 불 이동 경로 초기 입력 시 fire 배열은 INF로 초기화하고, 처음 불이 있던 자리만 0으로 저장한다. bfs로 기존 배열 값보다 값이 작으면 갱신하고 큐에 푸시해준다. int fire[1000][10..

스프링 세팅 시 민감한 정보들이 많다. (rds db 주소 등) jasypt로 간편하게 암호화 할 수 있다!! 1. build.gradle 설정 아래 부분을 추가해준다. testImplementation 'org.springframework.boot:spring-boot-starter-test' implementation group: 'com.github.ulisesbocchio', name: 'jasypt-spring-boot-starter', version: '3.0.4' 2. Jasypt config 설정 필자는 JasyptConfig로 네이밍해 설정하였다. 여기서 중요한 부분은 encryptKey 은 노출하면 안된다! package com.mews.mews_backend.global.config;..

문제 출처 :https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net 풀이 불쌍한 준석이,,, 우선 완전탐색으로 생각했으나 유니온 파인드로 해결해야하는 문제임을 깨달았다. 유니온 파인드는 아래 패턴을 기억해야 할 것 같다. 1. 같은 집합으로 묶어주는 함수(unionParent) root를 찾아주는 함수(getParent)로 가져온 후 서로의 부모를 지정해준다. void unionPar..

문제 출처 : https://www.acmicpc.net/problem/2195 2195번: 문자열 복사 첫째 줄에 S, 둘째 줄에 P가 주어진다. S와 P는 영어 대소문자와 숫자로만 되어 있다. S의 길이는 1,000을 넘지 않으며, P의 길이는 1,000을 넘지 않는다. copy함수만을 이용하여 S에서 P를 만들어낼 수 www.acmicpc.net 풀이 최소한의 copy를 사용해 s를 p로 만들 때, 사용 횟수를 출력하는 문제이다. p를 반복문을 돌며 s에서 같은 부분을 찾은 후, 만약 같다면 그 뒤에도 같은지 계속 검사한다. 가장 길게 검사한 부분을 저장해 idx에 더해준다. 코드 #include using namespace std; string s, p; int main(void) { ios::s..

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/150368 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 카카오톡의 이모티콘 목표 조건 이모티콘 플러스 서비스 가입자를 최대한 늘리는 것. 이모티콘 판매액을 최대한 늘리는 것. 을 최대한으로 달성했을때 이모티콘 플러스 서비스 가입자수, 이모티콘 매출액을 구하는 문제이다. 처음 문제를 보고 완전탐색 말고 다른 방법을 고민했는데, 우선 완전탐색으로 정답 확인을 받았다. 이 문제의 큰 힌트는 아래부분이다. 이모티콘마다 할인율은 다를 수 ..

문제 출처 : https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 풀이 문제가 길고 영어 번역본이라 거부감이 들 수 있겠으나.. 결론은 연결되어 있는 그래프를 탐색하는 대표적인 그래프 탐색 문제이다. 이런 그래프 문제는 보통 아래와 같은 방법으로 처리한다. vector를 배열로 선언한다. a b가 연결되어 있을 경우 서로 푸시한다. v[a].push_back(값), v[b].push_back(값)..

문제 출처 : https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 풀이 두 집합 a와 b가 같은 집합에 포함되어 있는지 확인하는 문제이다. 처음에 bfs로 완전탐색으로 구현하였으나, 시간초과가 발생하였다. 따라서 유니온 파인드를 통해 해결해야 한다. 처음 모든 수의 부모를 나타내는 배열 parent를 선언한다. 이 parent 배열은 항상 부모중 가장 작은 값을 가진 노드로 갱신해준다. getParent 부..