n . n

https://www.acmicpc.net/problem/16118 16118번: 달빛 여우 첫 줄에 나무 그루터기의 개수와 오솔길의 개수를 의미하는 정수 N, M(2 ≤ N ≤ 4,000, 1 ≤ M ≤ 100,000)이 주어진다. 두 번째 줄부터 M개의 줄에 걸쳐 각 줄에 세 개의 정수 a, b, d(1 ≤ a, b ≤ N, a ≠ b www.acmicpc.net 하.. 시간초과를 한시간동안이나 붙잡고 있다니 !!! 누가이기나 해보자는 마음가짐으로.. 그래도 결국엔 내가 이겻다 일단 로직은 생각보다 간단? 하다 문제에서 늑대는 2배 빨리 가거나, 2배 느리게 갈 수 있는데 해당 vertex(그루터기)까지 가는데 걸린 최소 시간을 직전에 2배 스퍼트해서 도착했을 경우와, 2배 느리게 달려서 도착했을 경..

https://school.programmers.co.kr/learn/courses/30/lessons/67259 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 제일 처음에는 다익스트라 알고리즘을 사용하는 걸 떠올렸는데.. 결론을 말하자면 다익스트라 알고리즘이 맞지만 [모든 방향을 고려한] 다익스트라 알고리즘이라고 할 수 있을 것 같다 (2023.02.17 맞나..? 다시 생각해보니까 다익스트라는 greedy한 알고리즘인데 dp라고 하는 게 맞지 않나..) 맨 처음 생각한 방식 시작점 [0, 0]에서부터 이동 가능한 좌표를 우선순위 큐에 삽입시키면서 최소..

https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 전형적인 dp의 점화식을 세우는 문제이다. 방법 1) 최대 정수를 N, 뽑는 정수의 개수를 K라고 하면, 간략한 점화식을 다음과 같이 생각할 수 있다. 위의 점화식을 예를 들어 생각해 보면, 최대 정수가 7이고 뽑는 개수가 3일때, dpCount[3][7] = dpCount[2][7] + dpCount[2][6] + dpCount[2][5] + dpCount[2][4] + ... + dpCount[2][0] 순서대로 ak가 0일때, ak가 1일때, 2일때, 3일때, ... 7일때 라고 생각하면 된다. 처음에는 덧붙여지는 a..

https://school.programmers.co.kr/learn/courses/30/lessons/43236 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이분 탐색 문제! 거리 범위가 10^9인 것에서부터 이분 탐색을 적용해야겠다는 느낌이 들었다 바위 n개를 제거했을 때, 각 징검다리(출발점, 도착점 포함)의 간격 거리의 최소값들 중 최대값을 구해야 한다. (최소값들 중 최대값이라는 말이 아직도 헷갈리는데 이런 값을 구하는 문제는 보통 이분 탐색 문제인 느낌 .. ?????👹) [1, distance] 범위에 대해 이분 탐색을 적용해야 한다는 건 ..

https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 복잡한 시뮬레이션 문제.. 시간 제한이 0.3초여서 긴장했는데 완전탐색으로 풀어도 시간 초과가 나지는 않을 것 같아서 완전탐색으로 풀이했다. 헷갈렸던 부분은 1. 모든 트리가 양분을 섭취한 후에야(봄), 섭취하지 못한 트리에 대해서 양분화가 진행된다. -> 이 두 과정을 동시에 처리하면 올바른 답이 나오지 않음 2. 나무가 죽을 때 나무의 나이/2 만큼의 양분(소수점은 절사)이 해..

https://www.acmicpc.net/problem/2515 2515번: 전시장 첫째 줄에는 그림의 개수 N (1 ≤ N ≤ 300,000)과 판매가능 그림을 정의하는 1이상의 정수 S가 빈칸을 사이에 두고 주어진다. 다음 이어지는 N개의 줄 각각에는 한 그림의 높이와 가격을 나타내는 정 www.acmicpc.net dp를 적용하여 풀이할 수 있다. 문제에서 제시한 테스트케이스 1번을 통하여 생각해 보면 6 4 //그림 입력 15 80 8 230 10 100 17 200 20 75 26 80 위에서 입력된 그림들을 높이 asc, 비용 desc 기준으로 정렬하면 다음과 같다. //sorted 8 230 10 100 15 80 17 200 20 75 26 80 높이가 제일 낮은 그림 (8,230)을 고..

https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 트리 구조이므로 사이클 없는 직선 거리 = 노드 사이의 거리 가 된다. 처음에는 플로이드-와샬 알고리즘을 적용하는 방식도 생각했지만, 이 알고리즘의 시간복잡도는 O(N^3)이고, N=1,000이므로 시간 초과가 발생함 따라서 각 노드에 대한 연결 리스트를 만들어 준 후, 다음의 bfs를 통하여 노드 사이의 거리를 구함 private static int bfs(int n, int start, int end) { int cost = 0; bool..

https://www.acmicpc.net/problem/9997 9997번: 폰트 첫째 줄에 단어의 개수 N (1 ≤ N ≤ 25)가 주어진다. 다음 N개 줄에는 사전에 포함되어있는 단어가 주어진다. 단어의 길이는 100을 넘지 않으며, 중복되는 단어는 주어지지 않는다. www.acmicpc.net 테스트 문장에는 알파벳 소문자 26개가 모두 포함되어 있어야 한다. -> 문장(또는 단어) 어떤 알파벳이 포함되어 있는지 여부를 판단하자!! => 비트마스킹 도입 집합 원소의 개수가 적을 때, 비트마스크를 통한 집합의 원소 삭제, 추가, 집합끼리의 계산 등의 연산을 효율적으로 수행할 수 있음 알파벳 소문자 26개만을 원소로 가지므로, 이에 적합 - 비트마스크 연산 https://loosie.tistory.c..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class Main { static int..

https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 먼저 지어져야 하는 건물 -> 순서 존재. => 위상 정렬!! 원래 연결 리스트 값을 만들 때 out -> in 형태로 만드는데, 여기에서 주어진 값은 in -> out 형태여서 헷갈렸다.. 참고 https://steady-coding.tistory.com/86 [BOJ] 백준 1516번 : 게임 개발 (JAVA) 문제 숌 회사에서 이번에 새로운 전략 시뮬레이션 게임 세준 크래프트를 개..