코딩테스트 (66) 썸네일형 리스트형 [D4-JAVA] SWEA 1238 - Contact SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com ✅ 문제 요약 시작노드에서부터 탐색을 시작하여 가장 깊은 노드를 찾고 만약 깊이가 같다면 노드의 번호가 더 큰 것을 출력하라 🤔 문제 접근 어렵지 않은 문제였으나 문제를 제대로 읽지 않아서 중간에 살짝 헤맸던 문제다. 항상 문제와 주어지는 조건을 잘 읽은 뒤 문제를 풀도록 해야겠다. (매번 이런 생각을 하지만 풀이법이 떠오르면 바로 코드부터 치고자 해서 잘 지켜지지 않는다..) 지금까지 풀어오던 그래프 문제와 다르게 정점 연결 정보를 특이하게 준다. 하지만 어려울거 없다. 정점 연결 정보는 항상 시작과 끝, 2가지가 한 쌍으로 주어지므로 각 테스트 케이스 별로 주.. [D4-JAVA] SWEA 1210 - ladder SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com ✅ 문제 요약 흔히 우리가 평소에 하는 사다리 게임이라고 생각하면 된다. 100 x 100인 2차원 배열에서 y(행) = 99 이며 그 값이 2인 도착점으로 갈 수 있는 y(행) = 0 이며 그 값이 1인 시작점을 찾는 문제다. 🤔문제 접근 처음 문제를 풀 때 배열의 값을 입력받으며 만약 y=99이고 그 값이 2인 경우 x.y좌표를 저장해놓고 도착지에서 역순으로 시작점을 찾도록 코드를 짰다. 도착지에서 왼쪽(x-1), 오른쪽(x+1)의 값이 1이라면 더이상 1이 나오지 않을 때까지 왼쪽, 오른쪽으로 전진했으며 아닐 경우 y-1을 해주어 위로 전진하도록 했다. 되게.. [Silver4-JAVA] 백준 10610 - 30 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 🤔 문제 접근 처음에는 양수 N을 문자열로 받은 뒤 백트래킹을 통해 숫자들의 위치를 바꿔가며 30의 배수를 찾고자 했다. 하지만 숫자들을 몇번 바꾸어줘야할지에 대한 상한선을 설정하는 것이 힘들었고 숫자의 길이가 길어지면 길어질 수록 시간 복잡도가 증가하는 문제가 있었다. 해당 문제를 풀기 위해서는 수학적 지식이 조금 필요한 것 같다. 먼저 30의 배수가 되기 위해서는 주어진 양수 N에 반드시 0이 1개 이상 존재해야한다. 또한 30의 배수인 30, 60, 90, 1.. [D2-JAVA] SWEA - 백만장자 프로젝트 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com ✅ 문제 요약 물건을 팔았을 때의 최대 이익 구하기 🤔 문제 접근 처음 문제를 봤을 때는 각 매매가를 우선순위 큐에 내림차순으로 저장하고 매매가의 앞에서부터 진행하여 만약 최대값(큐.poll() 한 값) 에 도달하면 (최대값 전의 매매가격 수 * 최대값) - (최대값 이전의 매매가격 누적합) 을 통해 문제를 풀고자 했다. 매매가 배열에서 인덱스가 최대값에 도달했다면 다시금 큐에서 poll하여 위 과정을 반복하도록 했지만 푸는 것에 실패했다. 더욱 간단한 방법이 있었으니, 매매가 배열의 뒤에서부터 시작하여 만약 현재 매매가가 max매매가보다 작다면 sum에 더해주고.. [Gold4-JAVA] 백준 1647 - 도시 분할 계획 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net ✅ 문제 요약 정점(집)과 간선(길)로 연결된 마을을 둘로 분리할 것인데 각 마을에서의 집들의 거리를 최소로 하고 싶다. 🛠️ 사용한 알고리즘 최소 스패닝 트리 - 크루스칼 알고리즘 🤔 문제 접근 처음 문제를 보고 어떻게 마을을 둘로 나눌 것인가 고민했다. 집 N개의 A마을, 집 M개의 B마을로 나누어 각각의 마을의 집들 사이의 최소 거리를 구해 완전 탐색으로.. [Gold4-JAVA] 백준 11657 - 타임머신 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 🤔문제 풀이 문제에서 음의 가중치가 존재하는 것, 그리고 1번 도시에서 어떤도시로 가는 과정에서 시간을 무한히 오래전으로 되돌릴 수 있다 는 것에서 음의 사이클이 존재할 수도 있다는 정보를 얻어 한 정점에서 다른 정점까지 최단 거리를 구하고 음의 사이클 존재 여부를 확인할 수 있는 벨만 포드 알고리즘을 적용해 풀어야겠다고 생각했다. 🚨C.. [Gold5-JAVA] 백준 21278 - 호석이 두 마리 치킨 https://www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net 🤔 초기 문제 접근 초기에 이 문제를 완전탐색으로 풀고자 했다. 전체 건물들 중에서 두개의 건물을 치킨집으로 선택한 뒤 다른 모든 건물들에서 깊이 우선 탐색을 진행하여 치킨 건물로의 최소 거리를 구하고자 했다. 하지만 전체 19개의 테스트 케이스 중 5개 밖에 맞히지 못했다. 또한 위와같은 풀이법으로 접근하고자 했다면 다른 건물들이 아닌 치킨 건물에서 다른 건물로의 .. [Silver2-JAVA] 백준 1780 - 종이의 개수 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 🤔 문제 풀이 쉽지 않았던 분할 정복 문제였다. 처음 문제를 풀었을 때 계속된 재귀호출을 통해 종이들을 분할하여 풀어나가는 방법임은 짐작했으나 종이들을 나누는 과정을 생각해내는 것이 무척 어려웠다. 첫 종이의 전체 요소들이 전부 같은지 검사하고 만약 다르다면 row/3 col/3 하여 9칸으로 나누고 나뉜 종이들을 다시 검사하고... 이런 과정의 반복이었다. 종이들을 분할하기 위해 필요.. 이전 1 2 3 4 5 6 ··· 9 다음
