본문 바로가기

전체 글

 (121)
[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칸으로 나누고 나뉜 종이들을 다시 검사하고... 이런 과정의 반복이었다. 종이들을 분할하기 위해 필요..
[Gold4-JAVA] 백준 14499 - 주사위 굴리기 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 🤔 문제 풀이 쉽지 않았던 시뮬레이션/구현 문제였다. 주사위를 굴렸을 때 map과 닿는 각 면의 숫자를 어떻게 채워줄지 막막했었다. 주사위가 다음과 같이 있다고 하고, 윗면을 보이는 주사위가 3이라고 한다면 다음과 같은 방식으로 움직이게 된다. 동쪽이동 서쪽이동 북쪽이동 남쪽이동 2 -> 3 4 -> 3 5 -> 3 1 -> 3 6..
[Gold4-JAVA] 백준 15918 - 랭퍼든 수열쟁이야!! https://www.acmicpc.net/problem/15918 15918번: 랭퍼든 수열쟁이야!! 세 자연수 n, x, y가 주어진다. (2 ≤ n ≤ 12, 1 ≤ x < y ≤ 2n, 1 ≤ y-x-1 ≤ n) www.acmicpc.net 🤔 문제 풀이 수열에 대한 규칙을 알려줬지만 처음에 수열을 어떻게 채워나갈지 막막했다. 하지만 문제에서 주어지는 입력 값 중 수열의 X와 Y위치의 숫자가 같다는 정보를 캐치했고 X와 Y의 숫자가 같으려면 X와 Y 사이의 간격이 X or Y와 같아야 함을 깨달았다. ex) x = 4, y = 10 이라고 주어지면 x와 y 사이엔 5칸의 빈칸이 존재하고 이는 수열 규칙에 의해 x와 y가 5임을 알 수 있는 부분이다. 이는 수열을 담은 배열 seq[x] = seq[..
반응형

티스토리툴바