병아리의 코딩 일기

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 안녕하세요! 곧 A형 시험이 있어서 주말 내내 알고리즘을 풀고 있네요,, ㅎㅎㅎ 새로운 문제를 풀기보다는 풀어봤던 문제들을 복습하고 있어요. 힘드네요,,ㅋㅋㅋ 오늘은 SW역량테스트 모의 A형 숫자 만들기 문제입니다. 문제 풀이 프로세스 이 문제의 핵심은 가지치기입니다. 연산자를 숫자 사이사이에 배치하는 것은 순열을 이용하면 됩니다. N개의 연산자를 일렬로 나열하는 것과 같죠. 1부터 N까지의 숫자를..

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..

본 글은 Do IT 알고리즘 코딩 테스트 자바 편을 정리한 글입니다! 구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘입니다. 코딩 테스트에서 사용 빈도가 높으니 꼭 알아두시기 바랍니다. 구간 합의 핵심 이론 구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 합니다. 배열 A가 있을 때 합 배열 S는 다음과 같이 정의합니다. 합 배열 S 정의 S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] // A[0]부터 A[i]까지의 합 합 배열은 기존의 배열을 전처리한 배열이라 생각하면 됩니다. 이렇게 합 배열을 미리 구해놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소합니다. A[i]부터 A[..