꼼개의 개발자취

문제 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제설명 다양한 푸는 방법이 존재한다. 조합을 이용하여 풀면 쉽게 풀 수 있다. 알고리즘 1. DFS를 이용하는데 종료조건은 투약횟수보다 cnt가 커지거나 세로길이를 넘어갈 때 이다. 2. 조건을 만족하면 최솟값을 구하고 return 한다. 3. 투여했을 때 안했을 때를 나눠서 조합으로 탐색한다. 구현 static int D; //두께 static int W; //가로크기 static in..

문제 : https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작�� www.acmicpc.net 문제설명 문제를 처음 보면 단순한 DFS/BFS 문제로 느껴진다. 그러나 단순 탐색으로 찾는다면 많은 반례들이 있다. 예를 들어 십자가 모양으로 있는 TK를 통과하진 못한다. 사실 5x5 배열에 제한시간이 2초라는 것은 단순 탐색으로는 풀 수 없다는 걸 뜻한다. 그러므로 5x5 = 25개의 학생중에 7명을 뽑는다고 생각해야한다. 알고리즘 1. 25명의 학생중 7명을 뽑는다. 2. 뽑은 학..

문제 : https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이�� www.acmicpc.net 문제설명 단순해 보이지만 생각하기 어려운 문제이다. 대부분 위상정렬을 이용해 해결한다. 알고리즘 1. 시작 정점과 도착정점을 이어주고, 다른 정점으로부터 도착되는 개수를 count배열에 할당한다. 2. count가 0인 정점부터 queue에 집어넣는다. 2. BFS를 실행하며 count가 0이 되는 정점을 출력한다. 주의사항 1. BFS 실행전에 cou..

문제 : https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 문제설명 BFS 와 객체 비교, PQ와 queue를 사용한다. 복잡한 문제여서 잘 읽어보며 꼼꼼히 코딩해야한다. 알고리즘 1. 우선순위를 compareTo를 이용하여 설정한다. 현재 위치를 queue에 넣고 BFS 실행 2. 먹이를 먹으면 PQ에 넣는다. 이떄 먹이를 먹을 때 까지의 최소시간 min을 이용해서 최소시간에 먹이를 먹은 애들만 PQ에 넣는다. -> queue 비워짐..

문제 : https://www.acmicpc.net/problem/6987 6987번: 월드컵 www.acmicpc.net 문제설명 6팀의 모든 경우의 수를 탐색하는 문제이다. 재귀와 백트래킹을 이용하여 해결한다. 알고리즘 1. 재귀를 이용하는데 종료조건은 무사히 15경기까지 오는 것이다. 2. 각 팀의 승리 , 패배 , 무승부 횟수가 음수가 되면 return 한다. 3. 1팀은 2,3,4,5,6 팀과 경기 2팀은 3,4,5,6 경기 3팀은 4,5,6 ~~ 이런식으로 진행된다. -> team, index 변수 사용 주의사항 1. 승 패 무승부 합쳐 30개가 안되는 TK가 존재한다. 2. 백 트래킹 조건은 종료조건 보다 위에 배치한다. 구현 public class Main_월드컵 { static int w..

문제 : https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 문제설명 1. BFS, DFS, Prim, Kruskal 등 다양한 알고리즘이 사용된다. 2. 문제를 잘 분석하고 하나하나 디버깅하며 해결한다. 알고리즘 1. BFS와 DFS를 사용하여 labeling 후 labeling 한 구역을 하나의 정점이라 생각한다. 2. 정점 사이의 거리를 PQ에 넣어준다. 3. PQ와 Union-Find를 이용하여 Kruskal 알고리즘을..