'📒 코테연습장' 카테고리의 글 목록

[알고리즘] 크루스칼 알고리즘(Kruskal Algorithm)

2023.09.08

신장 트리 (Spanning Tree) 무방향 그래프의 최소 연결 부분 그래프를 말한다. 즉, N개의 정점을 가지는 그래프 중 모든 정점을 포함하면서 최소 간선의 수인 N-1개의 간선으로 연결된 부분 그래프를 뜻한다. 특정 그래프에서 최소 간선 수인 N-1개의 간선을 가지고 있는 그래프는 트리 형태를 이룰 수 밖에 없어 신장 "트리"라고 한다. 🔹정점 수: N 🔹간선 수: N-1 🔹즉, 그래프 내 모든 정점을 포함하는 트리 (사이클 존재 X) 위의 그림과 같이 하나의 그래프에서 신장 트리는 여러개가 존재할 수 있다. 이때 하나의 그래프에서 생성될 수 있는 신장 트리 중 가중치의 합이 가장 작은 트리를 최소 신장 트리라고 한다. MST를 구할 수 있는 알고리즘으로 크루스칼 알고리즘과 프림 알고리즘이 있다...

📒 코테연습장/📝 최단경로

[Beakjoon] 백준 28354_링크 컷 토마토 (Java)

2023.09.04

28354번: 링크 컷 토마토 첫째 줄에 토마토의 개수 $N$, $0$일에 연결되어 있는 토마토 쌍의 수 $M$, $0$일에 익은 토마토의 수 $K$, 연결 상태가 변하는 횟수 $Q$가 공백으로 구분되어 주어진다. $(1 \leq K \leq N \leq 200\,000;$ $0 \leq www.acmicpc.net 문제 풀이 내 첫 플래티넘 문제였다. 알고리즘은 제대로 구성해서 작성한 것 같은데, 계속 시간 초과가 나서 애먹었던 기억이 있다. 시간을 단축시키고자 BFS 방문 시 필요 없는 방문이 발생하지 않도록 조건도 체크했는데 시간 초과가 나서 며칠 동안 붙잡고 있었다. 결론적으로 탐색이 더 효율적인 자료구조로 변경하니 통과되었다. 처음엔 그래프를 ArrayList로 구현했었는데, 그래프 안에 특정 ..

📒 코테연습장/📝 DP

[Baekjoon] 백준 16500_문자열 판별 (Java)

2023.07.15

16500번: 문자열 판별 첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 www.acmicpc.net 문제 풀이 처음엔 단어목록(A)에 있는 단어들을 긴 단어부터 하나씩 문자열의 앞부분과 비교해서 일치하면 단어 길이만큼 삭제하고 다시 탐색하는 방식으로 접근했었는데, 단어목록에 software, soft 같이 단어 사이에 서브 스트링이 존재하는 경우 반례가 생기는 것 같다..(사실 정확한 문제점 발견 못함) 단어를 찾았다고 문자열에서 삭제한 후 다시 고려하지 않는 방식은 미처 고려하지 못하는 경우가 발생하는 것 같다. 따라서 DP 테이블을 이용..

📒 코테연습장/📝 DP

[Baekjoon] 백준 2193_이친수 (Java)

2023.07.09

2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제 풀이 "이친수"의 조건이 되려면 아래와 같다. 1. 이진수 중에 2. 1로 시작하는 수 3. 1이 두 번 연속 있으면 안 됨 이 조건에 맞는 경우를 각 자리 별로 찾아봤을 때 일정한 규칙을 찾을 수 있었다. 이전 자리 수에서 찾은 이친수를 그대로 가져와 이용할 수 있는데, 해당 수의 끝 자리가 1로 끝나면 연속으로 1이 올 수 없으니 0만 붙일 수 있다. 반대로 0으로 끝나는 수면 0과 1을 모두 붙일 수 있다. 따라서 자릿수가 4인 이친수를 구..

📒 코테연습장/📝 DP

[Baekjoon] 백준 9095_1,2,3 더하기 (Java)

2023.07.08

📝 오늘의 일기 DP는 참 어렵다. DP는 보통 점화식을 찾아내기만 하면 코드로 옮겨 구현하는 시간은 짧은 편인데, 그 점화식을 찾아내는 방법이 연습 말고는 없는 것 같다.. 그래서 다른 알고리즘 문제풀이는 따로 포스팅을 하지 않는 편인데, DP는 잘할 때까지 포스팅하면서 정리해야 할 것 같다. 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 풀이 처음엔 DP 테이블을 2차원을 구성해서, 1로만 해당 숫자를 구성하는 경우, 1과 2로 구성하는 경우, 1,2,3으로 구성하는 경우의 수를 따져 보았는데, 2차원 배열 안에선 아무리 봐도 규칙을 찾을 수 없었다. 1차원 배열로 DP 테이블을 다시 구성해서 보..

📒 코테연습장/📝 최단경로

[알고리즘] 벨만-포드 알고리즘 (Bellman-Ford Algorithm)

2023.07.05

벨만 포드 알고리즘 벨만-포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 한 정점을 기준으로 다른 모든 정점까지의 최단경로를 구하여 결과적으로 원하는 도착지까지의 최단경로를 도출해 내는 알고리즘이다. 하지만 다익스트라 알고리즘과 다르게 그래프에 음의 가중치가 있어도 최단 경로를 구할 수 있다. [알고리즘] 다익스트라(Dijkstra) 다익스트라 알고리즘 다익스트라 알고리즘은 다이나믹 프로그래밍(DP)과 그리디 알고리즘을 활용한 최단경로 탐색 알고리즘이다. 다익스트라 알고리즘은 하나의 특정 정점에서 다른 모든 정점 dana-study-log.tistory.com 다익스트라와 음의 가중치 다익스트라 알고리즘 과정 1. 시작정점 선택 2. 거리 배열 초기화 (시작정점은 0으로 다른 노드는 무한대로) 3. 지금..

📒 코테연습장/📝 최단경로

[알고리즘] 다익스트라(Dijkstra)

2023.05.08

다익스트라 알고리즘 다익스트라 알고리즘은 다이나믹 프로그래밍(DP)과 그리디 알고리즘을 활용한 최단경로 탐색 알고리즘이다. 다익스트라 알고리즘은 하나의 특정 정점에서 다른 모든 정점으로 가는 최단 경로를 알 수 있으며, 간선의 가중치가 양수일 때 사용가능하다. 다익스트라 알고리즘이 DP라고 할 수 있는 이유는 특정 최단 거리는 여러 개의 최단거리로 이루어져 있기 때문이며, 하나의 최단 거리를 구할 때 특정 정점까지의 최단거리 정보를 그대로 가져와 사용하기 때문이다. 또한 그리디 알고리즘이라고 말할 수 있는 이유는 특정 최단 거리에 최단 거리를 더해가며 최종적인 최단거리를 계산하는 방식이기 때문이다. (다익스트라 알고리즘을 공부한 뒤 다시 읽으면 쉽게 이해가능) 한 정점에서 다른 모든 정점까지의 최단거리를..

📒 코테연습장

[프로그래머스] 약수의 개수와 덧셈

2022.05.09

lv.1 월간 코드 챌린지 시즌2 https://programmers.co.kr/learn/courses/30/lessons/77884?language=java class Solution { public int solution(int left, int right) { int answer = 0; for(int num = left; num

📒 코테연습장

[프로그래머스] 숫자 문자열과 영단어

2022.05.09

lv.1 2021 카카오 채용연계형 인턴십 https://programmers.co.kr/learn/courses/30/lessons/81301 class Solution { public int solution(String s) { int answer = 0; String[] numStr = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"}; for(int i = 0; i

📒 코테연습장

[프로그래머스] 완주하지 못한 선수

2022.05.06

lv.1 해시 https://programmers.co.kr/learn/courses/30/lessons/42576 통과 풀이 import java.util.*; import java.util.Collections; class Solution { public String solution(String[] participant, String[] completion) { // 통과 풀이 Arrays.sort(completion); Arrays.sort(participant); for(int i = 0;i < participant.length-1;i++){ if(completion[i].equals(participant[i])) { continue; } else { return participant[i]; } ..

티스토리툴바