분류 전체보기 검색 결과

해당 글 215건

[BaekJoon] 백준 1240. 노드사이의 거리

https://www.acmicpc.net/problem/1240 [1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net](https://www.acmicpc.net/problem/1240) 문제 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. 입력 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리(10,000 이하의 정수)를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 M개의 노드 쌍이 한 줄에 한 쌍씩 입력된다. 출력 M..
알고리즘/백준 2022. 9. 27. 14:01

2020 KAKAO BLIND RECRUITMENT - 자물쇠와 열쇠

https://programmers.co.kr/ [프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr](https://programmers.co.kr/)문제 설명 고고학자인 "튜브"는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다. 잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M..
알고리즘 2022. 9. 23. 14:48

2021 KAKAO BLIND RECRUITMENT - 합승 택시 요금

문제는 프로그래머스 에서 확인 할 수 있습니다. 풀이 : 한 정점이 주어 졌을 때 최단거리를 구하는 문제 다익스트라 알고리즘을 사용하여 해결할 수 있다. 시작정점 S와 도착지점 A, B 가 있을 때 시작지점을 S 라고했을 때 다익스트라 결과값, 시작지점을 A 라고했을 때 다익스트라 결과값, 시작지점을 B 라고 했을 때 에서의 다익스트라 결과값 3가지를 사용해서 어느 정점을 거쳐갔을 때 최소가 되는지 확인하면 답이 나온다. import java.util.Arrays; class Solution { static int INF = 98765432; public int solution(int n, int s, int a, int b, int[][] fares) { int[][] w = new int[n+1][n..
알고리즘 2022. 9. 22. 09:47

2022 KAKAO BLIND RECRUITMENT - k진수에서 소수 개수 구하기

문제는 프로그래머스 에서 찾을 수 있습니다. https://programmers.co.kr/ 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 : K 진수를 구하고 0이 나올 때 까지 문자열로 끊어서 체크하면 된다. 다만 소수를 구하는 과정에서 에라토스테네스의 채를 생각하고 풀면 된다. int 형으로 할 경우 런타임 에러가 발생하는걸 보니 long으로 대체해서 풀었다. import java.util.*; class Solution { public int solution(int n, int k) { int answer = 0; String knum = "..
알고리즘 2022. 9. 20. 10:00

[BaekJoon] 백준 12868번. 돌 그룹

https://www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려 www.acmicpc.net 풀이 : A, B, C 3개의 돌이 주어 졌을 때 2개의 조합을 선택하여 연산을 수행했을 때 모두 같은 값이 될 수 있도록 확인한다. 예를 들어 A, B 를 선택했고, A < B 일 경우 A = A + A, B = B - A 으로 새로 값을 정할 수 있다. 여기서 접근 방법은 A, B, C 을 모두 더한 값이 달라지지 않는다는 것이다. 합이 달라지지 않기에 2가지 조합만 생각해도 나머지 1개..
알고리즘/백준 2022. 9. 16. 16:48

[BaekJoon] 백준 2482번 색상환

https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 : N개의 색상환을 입력받았을 때 K 개를 선택할 수 있는 경우의 수를 구하는 문제 dp[i][j] = i 개의 색상환에서 j 개를 선택할 경우의 수 여기서 j 를 선택하는 경우와 선택하지 않는 경우로 나눌 수 있다. j 번째를 선택하는 경우 = dp[i-2][j-1] j 번째를 선택하지 않는 경우 = dp[i-1][j] dp[i][j] = dp[i-2][j-1] + dp[i-1][j] 단 마지막에서 N 개의 색상..
알고리즘/백준 2022. 9. 14. 17:20

[BaekJoon] 17404번: RGB거리 2

https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 원형을 이루는 집들 간에 RGB 의 색으로 집을 색칠 할 때의 최소 비용을 구하는 문제 고려할 점은 원형을 이루고 있고 서로 인접한 집들은 같은 색을 가지면 안된다는 점이다. 다이나믹 프로그래밍으로 풀 수 있고 점화식을 dp[i][0] = i - 1 번째 집까지 색칠한 최소값 + i 를 Red 로 칠했을 때의 값 dp[i][1] = 위와 동일 + i 를 Green 으로..
알고리즘/백준 2022. 9. 13. 16:30

[BaekJoon] 백준 11049번 행렬 곱셈 순서(Java)

https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net DP 문제 주어진 행렬은 서로 인접한 행렬끼리만 곱할 수 있고 다이나믹 프로그래밍으로 풀 수 있다. dp[i][j] 를 i 번째 행렬부터 j 번째 행렬까지의 연산 횟수 중 최소의 값을 저장하고 있다고 할 때, dp[i][j] = d[i][k] + d[k][j] + i, k, j 간의 곱셈 연산 수 로 점화식을 표현할 수 있다. 초기화 작업 >> 우선 초기화 작업으로 행과 열이 같을 때..
알고리즘/백준 2022. 9. 13. 12:09