전체 글
-
백준 14889 스타트와 링크Algorithm/구현(Brute force, Back tracking, etc.) 2021. 11. 15. 18:24
https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net - 난이도가 어렵진 않았지만, 디테일에 신경써야 하는 문제였다. - 역시나 브루트포스 백트래킹 문제이다. 1번부터 최대 20번 선수까지 주어질 때, 각 선수가 A팀에 선택이 되던지, B팀에 선택이 되던지 두 가지의 경우의 수이고, 재귀의 깊이는 20을 넘지 못한다.(한 팀에 과반수의 인원이 들어가는 경우 바로 종결되기 때문.) 따라서, 2^20 이하의 연산량이 되므로 재귀적으로 구현이 가능하다. - 각 팀의 구성원은 ..
-
백준 14888 연산자 끼워넣기Algorithm/구현(Brute force, Back tracking, etc.) 2021. 11. 15. 17:31
- N개의 수열과 N-1개의 연산자가 주어질 때, 가능한 모든 연산 결과의 최소값과 최대값을 구하는 문제이다. - 브루트 포스 문제이고, N의 범위가 2 이상 11 이하인 것으로 보아, 재귀 백트래킹으로 풀 수 있는 문제임을 알 수 있다. (약 4^11 = 2^22) - 백트래킹을 평소 열심히 연습해왔다면 쉽게 풀 수 있는 문제이다. 종결 조건은 cnt 매개변수가 n과 같아질 때, 즉 모든 피연산자를 사용 했을 때 최대 / 최소값을 최신화하면 된다. #include #include using namespace std; int n; int executed[11]; int num_plus, num_minus, num_multiply, num_divide; int min_answer = 1000000000; ..
-
백준 14503 로봇 청소기Algorithm/구현(Brute force, Back tracking, etc.) 2021. 11. 15. 16:28
https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net - N x M 크기의 장소가 주어진다. 테스트 케이스 마음이라 시간복잡도는 구할 수 없다고 생각.. - 벽인지 바닥인지 여부를 나타내는 place array, 그리고 청소가 된 지 여부를 체크하는 cleaned array를 두었다. - 방향은 x, y 각각 배열을 두어서, 북 : 0, 동 : 1, 남 : 2, 서 : 3 각 값을 index로 사용하도록 하였다. 즉, 현재 x,y에 해당 인덱스의 ..
-
백준 1260 DFS와 BFSAlgorithm/그래프 2021. 11. 13. 12:18
https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net - 그래프 알고리즘을 처음 입문할 때 좋은 문제이다. - DFS의 경우, 재귀적으로 구현하는 경우 O(V^2)의 시간복잡도가 나온다. BFS의 경우, 인접 행렬을 사용할 것이므로 O(V^2)의 시간복잡도가 나온다. - 주의해야 할 점은, 무방향 그래프이므로 처음 인접 행렬을 구성할 때 양방향으로 등록을 해 주어야 한다는 것, 또 하나의 노드에서 여러 개의 간선..
-
백준 2839 설탕 배달Algorithm/DP 2021. 11. 13. 04:54
https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net - 2가지의 풀이법이 있다. Greedy, DP - Greedy 풀이법을 보면, 주어진 N에 3을 빼주면서, 뺄 때마다 해당 수가 5의 배수인지를 확인한다. 5의 배수가 되는 순간 남은 모든 무게를 5kg 봉지로 해결하면 되므로 그것이 해답이다. #include using namespace std; int N; int main() { cin >> N; int ans = 0; while (N >= 0) { i..
-
백준 14502 연구소Algorithm/그래프 2021. 11. 12. 20:14
https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net - N과 M이 최대 2^3이므로, 많은 for문을 중첩시킬 수 있다. (NM = n || ny >= m) continue; if (virus[nx][ny] == 0) { virus[nx][ny] = 2; visited[nx][ny] = true; q.push({ nx,ny }); } } } // 안전구역 검사 후, answer 최신화 int cnt = 0; for (int i = 0; i < n; i++) {..
-
백준 14501 퇴사Algorithm/구현(Brute force, Back tracking, etc.) 2021. 11. 11. 12:32
https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net - 재귀의 깊이를 보면, 백트래킹으로 풀 수 있는 각이 나온다. 특정 일에 상담을 하는 경우, 하지 않는 경우 2가지의 경우의 수가 있고, N이 15이하이므로 최대 2^15 의 경우의 수가 가능하다. 즉, 시간초과를 걱정 할 필요가 없다. - 첫 호출은 1일차, profit은 0로 한다. 여기서 1일차에 상담을 하기로 결정했다면 1일차의 profit을 현재 profit에 더하고, 상담에 걸리는 시간을 추가해서 호출을 한다. - 백트래킹의 종결조건으로는 1. day가 n+1보다 많은 경우, 즉 퇴사일을 넘기는 경우는 상담을 못 하는 것..
-
인턴 4주차에 작성했던 중간 일기Etc/Diary 2021. 11. 11. 12:00
살면서 아르바이트는 여러 번 해봤지만, 인턴은 처음인지라.. 해 보면서 느꼈던 점들을 정리 해 본다. 1. 인턴을 하면서 느낀 건, 공식문서를 읽고 디테일함에 신경 쓰는 것이 중요하다는 것. (특히 성능 향상을 위해서) 2. 또한, 일 처리를 굉장히 꼼꼼하게 해야 한다는 것(node_modules 디렉토리를 계속 push하거나, merge 실행 이후 conflict난 부분을 처리하지 못하고 PR에 올리는 실수를 해서 지적당함.) 3. 급하게 진행하면 기초가 약해서 결국엔 전체적인 진전이 더욱 느리게 된다. 시간을 많이 투자해서, 차근차근 공부를 해 나가자. + 복습이 굉장히 중요하다. 소중한 PR 리뷰들 여러 번 읽기 4. 힘들게 번 돈이라 흥청망청 쓰기가 싫다. (하지만 열심히 아낀 돈은 결국 2학기 ..