[BOJ] 백준 14938 서강그라운드 (JAVA)
Algorithm/- Baekjoon2023. 12. 25. 01:27[BOJ] 백준 14938 서강그라운드 (JAVA)

📑 문제🌱  아이디어N 번 반복 다익스트라알고리즘과 플로이드 워셜 알고리즘 두 방법으로 풀 수 있다일단 나는 다익스트라 알고리즘을 사용해서 풀기로 했다 (그냥 빠를 것 같아서...) 사실 플로이드 워셜을 사용해도 시간초과는 걱정안 해도 된다 ㅎㅎ위 문제에서 "탐색 범위"를 입력으로 주는데, 예를 들어 탐색 범위가 5 일 때 현재 노드로부터 다른 노드까지의 거리가5보다 작거나 같아야 한다. 즉 현재 노드에서 모든 노드의 최단거리를 구하고, 탐색범위 이하의 노드들의 아이템을 도출한다! 🌱 코드 및 풀이그래프가 가지는 모든 정점을 기준으로 각각 시작노드로 설정 후 모든 정점을 기준으로 최단거리를 탐색하고탐색범위에 비례한 아이템을 챙길 수 있는 최대 숫자를 출력한다. 즉 현재 노드에 아이템이 몇 개가 있는..

[BOJ] 백준 18111 마인크래프트 (JAVA)
Algorithm/- Baekjoon2023. 12. 21. 03:26[BOJ] 백준 18111 마인크래프트 (JAVA)

📑 문제🌱 아이디어이 문제는 한 블록당 숫자를 기준으로 푸는 것이 아닌 평탄화 기준이 될 땅 높이를 기준으로 탐색한다! 처음엔 문제에서 말한 조건 1,2번을 DFS로 풀어서 한 블록을 기준으로 평탄화 작업을 하려고 했는데...안된다는 것을 빨리 깨달았다... 이 문제는 "땅의 높이는 256블럭 보다 작거나 같은 자연수 또는 0 이다"  라는 말을 이용해서 풀어야 한다 예를 들어 결국 평탄화 작업을 통해 나오는 땅의 높이는 0 ~ 256까지의 경우가 있다.즉 우리는 0~256까지 경우의 평탄화 기준 땅높이를 토대로 조건 1,2번과 인벤토리를 통해 평탄화할 수 있는지판단하고 평탄화 가능 하다면 최소 시간을 구해야 한다! 주석을 통해 코드마다 설명을 남겨놨으니 천천히 보면 이해하는데 어렵지 않을 것이다.?..

[BOJ] 백준 1309 동물원 (JAVA)
Algorithm/- Baekjoon2023. 12. 18. 12:00[BOJ] 백준 1309 동물원 (JAVA)

📑  문제🌱 아이디어사자는 마주 보게 배치하면 안 되며, 한 마리도 존재하지 않는 경우도 하나의 경우의 수로 센다 동적계획법(DP)을 사용하면 시간도 아끼면서 풀 수 있다!사실 본인도 점화식 세우는 법을 잘 모른다... 하지만 감이 안 잡히면 N의 수만큼 경우의 수의 수열을 만들어 보자!일단 문제처럼  N*2 배열을 만들어보자! (문제 조건에 성립하는 경우의 수)N = 0 -> 1 N = 1 ->  3N = 2 -> 7N = 3 -> 17N = 4 -> 41 이렇게 증가되는 수열이 만들어진다 이것을 점화식으로 세운다면점화식 = fn = f(n-1)*2 + f(n-2) 이렇게 세울 수 있다. 즉 전값*2 + 전전값 이 현재값이다 이용해서 구현해 보자!🌱  코드 및 풀이점화식을 세우고 DP 통해 구현한..

[BOJ] 백준 1010 다리놓기 (JAVA)
Algorithm/- Baekjoon2023. 12. 17. 03:30[BOJ] 백준 1010 다리놓기 (JAVA)

📑 문제🌱 아이디어본문에서 "다리는 서로 겹칠 수 없다." 라는 조건이 하나 붙는데 이번 문제의 키 포인트이다."다리는 서로 겹칠 수 없다." 라는 말은 곧 순서를 고려하지 않는다 는 말과 같다.두 그림은 같은 사이트에 다리를 잇는 경우의 수이다. 순서를 고려한다면 두 경우는 서로 다른 경우가 되어야 한다.A, B, C != A, C, B 이 경우는 순서를 고려하기 때문에 요소가 같아도 순서가 달라 서로 다른 경우이다. 하지만 문제 조건 중 "다리는 서로 겹칠 수 없다." 를 성립하려면 위 두 그림은 같은 경우의 수가 되어야 한다!중복을 제거해야 하기 때문이다. 즉 A, B, C == A, C, B 이 성립되어야 중복이 제거가 되며 하나의 경우로 본다. 이 문제는 M개에서 N개를 뽑고 중복을 제거해야..

[BOJ] 백준 11724 연결 요소의 개수 (JAVA)
Algorithm/- Baekjoon2023. 12. 14. 22:12[BOJ] 백준 11724 연결 요소의 개수 (JAVA)

📑 문제 본문에서 "방향 없는 그래프가 주어졌을 때" 라는 말은 곧 양방향이다!즉 A -> B , B -> A 가 성립해야 한다. "연결 요소"에 대해 설명하기 위해 테스트 케이스를 두 가지를 가져와 봤다.1. 본문 예제 입력 1 위 사진은 본문에서 입력된 정점과 간선들의 그래프이다.왼쪽 집합 (1,2,5) 와 오른쪽 집합 (3,4,6)은 연결할 수 있는 간선이 없다 즉 "연결 요소의 개수는" 2 가 되는 것이다! 2. TestCase : 4 0이 경우는 노드는 4개이고 간선은 0이다 그렇다면 연결 요소의 개수는 몇일까?답은 4 이다. 간선이 없는 노드는 하나의 연결요소이다. 이점만 생각하고 구현한다면 쉽게 풀 수 있을 것이다. 🌱 코드 및 풀이ArrayList를 이용하여 인접리스트를 만들고 양방향임..

반응형
image