병아리의 코딩 일기

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 오늘은 SWEA의 2112번 문제 보호 필름입니다. 삼성SW역량테스트 모의 A형 문제입니다. 조합 코드를 이용한 부분집합을 구현한 강사님의 코드가 제일 깔끔한 것 같아 참고하여 풀어봤습니다. 해설은 주석에 자세히 설명하였습니다. 풀이는 아래와 같습니다! 정답 코드 package SSAFY_A형특강; import java.io.BufferedReader; import java.io.IOExceptio..

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제 해결 프로세스 및 꿀팁 대각선도 이동이 가능하므로 길이가 8인 델타 배열을 만듭니다. (팔방탐색) 원래 DFS는 visited 배열을 만들어 검사해줍니다. 하지만 이런 문제같은 경우에는 1을 지날 때 0으로 바꾸어주면 됩니다. map의 좌표 중 1인 곳만 탐색하기 때문에, 0으로 바꾸어준 곳은 더이상 다른 곳에서 탐색하지 않기 때문입니다. 한 가지 꿀팁을 드리자면!! map의 좌표를 w..

https://www.acmicpc.net/problem/24480 24480번: 알고리즘 수업 - 깊이 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 문제 해결 프로세스 이 문제는 이전 깊이 우선 탐색 1 문제와 완전히 동일하지만, 정점을 내림차순으로 방문합니다. Collections.reverseOrder() 을 이용하여 리스트만 내림차순으로 정렬해주면 해결되지만, DFS 알고리즘에 익숙해지기 위해 다시 한 번 풀어보는 것을 추천해드립니다! 정답 코드 package DF..

DFS 의 기본 문제이지만, 함정이 숨어있습니다. 보다시피 정점의 수와 간선의 수가 크다보니 인접행렬을 만들게 되면 메모리 및 시간 초과가 나게 됩니다. 따라서 인접 리스트로 만들어주어야 하고, 문제에서 인접 정점은 오름차순으로 방문한다고 했으니 리스트에 값을 넣은 후 Collections.sort 를 이용하여 오름차순으로 정렬해주어야 한다. R부터 시작해야 한다는 것도 잊지 말자. 정답 풀이 package DFS완전정복; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import j..

https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 문제 🐻‍❄️ 정답 코드 (이해가 안되시는 부분이 있다면, 아래의 상세 설명을 참고해주세요) package SW역량테스트_A형준비; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTo..