꼼개의 개발자취

문제 : 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 알고리즘을..

문제 : https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어 www.acmicpc.net 문제설명 이분 그래프 문제이다. 이분그래프 문제는 BFS로 구현하는 것이 정석이다. 알고리즘 1. 삽입 삭제가 빈번하면 Li..

서론 최장 수열은 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분수열을 찾는 문제이다. 일반적으로 길이를 저장하는 테이블을 만들어 해결한다. 이럴경우 이중반복문을 사용하기에 시간복잡도는 O(N^2)이 된다. 또 다른 방법은 Binary search를 이용하여 O(NlogN)의 시간복잡도를 갖는 방법도 있다. 구현 코드 memo[0] = 1; for (int i = 1; i arr[j] && memo[i]

문제 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRF8s6ezEDFAUo SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제설명 자료구조를 잘 활용하여 풀어야하는 시뮬레이션인다. N의 크기가 100이기 때문에 값이 0인 자리에서 출발하여 모든 경우의 수를 살펴봐도 O(N^2)이다. 아마 평균적으로는 장애물들이 있기 때문에 훨씬 더 빠를 것이다. 알고리즘 1. 0이 있는곳 즉 아무 장애물이 없는 구역을 queue에 넣는다. 2. 하나씩 poll 하며 4방향으로 조건에 맞게 탐색을 진행한다. 3. 웜홀 같은 경..

문제 :https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq&categoryId=AV5PoOKKAPIDFAUq&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제설명 기본적인 DFS문제지만 공사 할 수 있는 것을 잘 유의하며 접근해야한다. 알고리즘 1. DFS로 가장 높은 봉우리부터 4방향 탐색을 시작한다. 2. 만약 다음 갈 수 있는 봉우리 - 현재 높이 가 공사할 수 있는 높이보다 작아야 공사가 가능하다. 3. 2번의 경우 공사 한 것을 체크 한뒤 DFS를 진행..

서론 Floyd Warshall 알고리즘은 최단 경로를 구하는 방법중 하나이다. 동적계획법으로 접근하는데 시간 복잡도는 O(N^3)이다. 최단경로 구하는 알고리즘인 dijkstra와 비교하자면 간선 수가 많으면 Floyd 가 빠를 수 있다. 시작 정점이 정해져 있으면 dijkstra가 당연히 빠르다. 음의 가중치가 존재한다면 dijkstra는 사용할 수 없지면 Floyd는 사용가능하다. 구현 코드 for i in vertex // 경유 for j in vertex //시작점 if i == j continue for k in vertex //도착점 if i == j or j==k continue arr[j][k] = min(arr[j][i] + arr[i][k] , arr[j][k]) 문제에 적용 문제 :..

문제 : https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 www.acmicpc.net 문제설명 단순 로직, 메모이제이션, 완전탐색 등 푸는 방법은 여러가지이다. 단순 로직은 빠르지만 문제가 달라지면 또 다른 로직..