꼼개의 개발자취

문제 : https://www.acmicpc.net/problem/5557 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제설명 탐색문제일까 싶었지만 N이 100이면 최악의 경우가 2의 99승까지 가기 때문에 무조건 DP로 풀어야 한다고 생각했다. 근데 DP의 가장 큰 문제는 점화식을 찾기 어렵다는 것이다. 30분 정도 고민해 봤지만 역시 생각해내기 어려워 다른 사람 풀이를 참고하였다. 알고리즘 핵심 변수는 dp[N][21] 인데 'N번 째 일 때 값이 0이상 20이하 이다.'를 나타낸 것이다. 이해하기가 쉽지 않은데 이 그림을 보면 이해하기 쉬울 것이다. 아래와 같은 예제가 주어졌을 때 5 9 3 3 3 ..

문제 : SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제설명 1. 조합문제이다. 21개의 조합 중(anta tica 제외) 제한시간이 1초는 중복제거를 한다면 충분히 가능한 시간이다. 알고리즘 1. 남극언어의 특징인 접두사와 접미사는 무조건 읽어야만한다.(anta tica) 2. 21개의 알파벳과 K - 5 만큼 조합한다. 3. 조합된 원소를 이용해 읽을 수 있는 단어를 체크한다. 주의사항 1. 남극언어 필수 알파벳 5개보다 가르칠 수 있는 개수가 적으면 읽을 수 있는 단어는 0이다. 2. DFS 함수 구현 시 idx 변수를 통해 했던 조합은 중복 제거를 해야한다. 안그러면 시간초과 발생 구현 bool a..

문제 : 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/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://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를 진행..

문제 :https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4yC3pqCegDFAUx&categoryId=AV4yC3pqCegDFAUx&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 알고리즘 1. 재귀함수를 사용한다. 종료 조건은 주어진 값을 버튼으로 누를 수 있으면 숫자의 길이 + 1(=버튼) 종료된다. 가치치기는 min보다 커지면 return한다. 2. 누르지 못한다면 input값의 약수를 찾는다. 약수는 버튼으로 누를 수 있어야 한다. 약수를 찾았다면 몫과 약수의 길이 + 1(x버튼)..

문제 :https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWsBQpPqMNMDFARG&categoryId=AWsBQpPqMNMDFARG&categoryType=CODE&&& SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 알고리즘 1. time step 마다 악마를 증식시키고 주인공이 움직인다. 2. 악마 큐와 주인공 큐를 따로 만들어서 BFS를 사용하여 조건에 따라 증식 & 이동한다. 3. time step 마다 움직여야 하기 때문에 큐에 cnt를 만들어 time변수와 cnt를 비교하여 다르면 while문을 빠져나오게 했..

문제 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu&categoryId=AV5V4A46AdIDFAWu&categoryType=CODE&&& SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 알고리즘 1. DFS를 통해 벌통에서 벌꿀을 채취 할 수 있는 가장 큰 경우를 배열에 저장한다. 2. 배열에 저장된 값을 통해 두 명의 일꾼이 선택 할 수 있는 가장 큰 조합을 찾는다. 주의사항 1. 채취 할 벌통을 선택하는 과정에서 선택한 경우와 선택하지 않는 경우를 나눠줘야한다. 예를 들어 채취 할 ..