CS/Algorism (99) 썸네일형 리스트형 [백준] 1058. 친구 https://www.acmicpc.net/problem/10581. 플로이드워셜로 푸는 방법플로이드워셜은 N개의 노드에서 N개의 노드로 이동하는데 걸리는 최단 거리(비용)을 구할 수 있다. 즉, 각 노드에서 다른 N-1개의 노드로 몇 번의 이동으로 도달 가능한지 구한 후(=사람 a와 사람 b의 관계), 1번 또는 2번으로 이동이 가능하면 2-친구 관계이므로 카운트해주면 된다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { static BufferedReader br = new BufferedReader(new Inpu.. [프로그래머스] 등대 https://school.programmers.co.kr/learn/courses/30/lessons/133500?language=java 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr트리간선이 n-1개이고, 모든 등대가 서로 다른 등대로 이동 가능하다.즉, 사이클이 생길 수 없다. 따라서 트리로 바라볼 수 있고 dfs, bfs 같은 트리 순회 방법을 사용할 수 있다.그리디임의의 한 점을 루트 노드라고 생각하여, dfs를 진행한다고 가정하자. 가장 아래인 리프 노드는 불이 켜질 필요가 없다. 즉, dfs를 진행하며 가장 아래인 리프 노드까지 내려간 뒤, 리.. 다익스트라 알고리즘 - 우선순위 큐와 방문 처리에 대해 다익스트라 문제를 풀다가 공식처럼 우선순위 큐를 사용하고, 방문 처리를 하는 느낌이 들었다. "우선순위 큐를 꼭 사용해야 하는가?", "방문 처리를 꼭 해야 하는가?" 라는 궁금증이 들어서 이 글을 작성한다. https://www.acmicpc.net/problem/1753 이 문제를 예로 들자. 입력 값이 다음과 같고, 1번 노드에서 출발한다고 가정하자.5 611 2 21 3 32 3 42 4 53 4 14 5 2 간선을 리스트로 표현하면 다음과 같고, 1 ➡️ 2 ➡️ 3번 노드 순서로 방문했을 때의 모습은 다음과 같다. 이때 큐에는 (4, 7)과 (4, 4)가 담겨있다. (노드 4번까지 오는데 걸린 비용이 각각 7, 4)우선순위 큐를 사용하지 않을 경우(4, 7)을 먼저 poll한다. 그리고 cos.. [백준] 10713. 기차 여행 https://www.acmicpc.net/problem/10713 가격 비교 (min(a * k, c + b * k)) 각 철도를 이용하는 총 횟수를 알아내고, 그에 따라 해당 철도를 이용할 때 티켓을 구매하는 방법과 IC 카드를 구매하는 방법 중 가격이 더 작은 방법을 이용하면 된다.철도 이용 횟수 구하기 (누적합)각 철도를 이용하는 횟수를 구해야 하는데, 만약 도시 1번에서 3번으로 이동할 경우, 1번 철도와 2번 철도를 이용한다. 그런데 이런 식으로 카운트하면, 이동 횟수가 m번이고 매 이동마다 가장 먼 도시로 이동한다고 가정했을 때 O(m * n)의 시간 복잡도가 소요되어 시간초과가 날 수 있다.따라서 누적합을 이용해야 한다. 누적합 활용 방식은 다음과 같다.도시 1번에서 5번으로 이동한다고 .. [백준] 1941. 소문난 칠공주 https://www.acmicpc.net/problem/1941 처음에는 5 X 5 그래프의 각 노드를 시작으로 그래프 탐색을 해서 7명을 모으는 것을 생각했다. 그런데 같은 조합이 여러 번 나올 수 있다. (학생 1 -> 2 -> 3인 조합과 학생 3 -> 2 -> 1의 조합은 같기 때문) 그리고 이때 이미 나온 조합인지 일일이 검사하는 건 매우 비효율적이다. 따라서 25명의 학생 중 7명의 학생 조합을 찾고(백트래킹), 이 조합의 학생들이 모두 연속된 자리인지, 그리고 S 값이 더 많은지 확인(bfs)하면 된다. 그런데 7명의 학생 조합을 찾을 때 중복된 조합을 생성하면 안된다. (ex, 학생 1 + 2, 학생 2 + 1은 같음) 따라서 5 X 5 배열을 숫자 0 ~ 24로 취급한 후, dfs의 s.. [백준] 7570. 줄 세우기 https://www.acmicpc.net/problem/7570 처음에 떠올렸던 풀이는 시간 초과로 불가능했다. 따라서 다른 방법을 떠올려야 하는데, 구글링을 통해 dp로 O(N)의 시간으로 풀 수 있는 방법을 발견했다. (https://mygumi.tistory.com/276#recentEntries)우선 숫자를 제일 앞이나 뒤로 이동시키는 최솟값 = (n - 가장 긴 연속된 숫자의 오름차순 수열의 길이)이다.그리고 가장 긴 연속된 숫자의 오름차순 수열의 길이를 찾기 위해선 다음 점화식이 사용된다.dp[n] = dp[n - 1] + 1혼자 힘으로 떠올리기 힘들고 이렇게 적어도 와닿지 않지만, 예시를 통해 직접 적어가며 생각하면 이해는 된다..import java.io.BufferedReader;imp.. [백준] 2011. 암호코드 https://www.acmicpc.net/problem/2011 쉬운듯하지만 신경쓸게 있고, 구현 과정에서 실수하기 좋은(헷갈리는..) 부분이 많아서 푸는데 시간이 좀 걸렸다. 우선 dp로 풀 수 있는 문제이다. 25114가 주어졌을 때, 먼저 2를 만드는 경우부터 25, 251, ... , 25114를 만드는 경우까지 생각해보자.2 -> dp[1] = 1225 -> dp[2] = 22 + 525251 -> dp[3] = 2 2 + 5 + 125 + 12511 -> dp[4] = 42 + 5 + 1 + 125 + 1 + 12 + 5 + 1125 + 1125114 -> dp[5] = 62 + 5 + 1 + 1 + 425 + 1 + 1 + 42 + 5 + 11 + 425 + 11 + 42 + 5 + 1 +.. [2022 KAKAO TECH INTERNSHIP] 코딩 테스트 공부 https://school.programmers.co.kr/learn/courses/30/lessons/118668# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr[문제 정의]주어진 모든 문제를 풀 수 있는 알고력과 코딩력을 가진다는 말은, 주어진 problems 배열에서 가장 큰 값인 알고력과 코딩력을 가져야 한다는 말이다. 즉, (초기 알고력, 코딩력)에서 시작해서 (목표 알고력, 코딩력) 상태에 도달하는데 걸리는 최단 시간을 구하면 된다. [구현]그런데 현재의 알고력과 코딩력에서 알고력 및 코딩력을 늘릴 수 있는 방법은 다음과 같이 여러 방법이 있다.알.. 이전 1 2 3 4 ··· 13 다음
