목록2024/09 (49)
미소를뿌리는감자의 코딩
1. 문제https://www.acmicpc.net/problem/14888 2. 접근 방법어떻게 연산자들의 경우의 수를 표현할 수 있을까 고민해 보았다.처음에 잘 생각이 나지 않았지만, 섣불리 접근하다간 오히려 시간을 많이 쓸 것 같아서 더 고민해 보았다. - 요런 태도가 코테에서는 중요한 것 같다. (메모메모~)예를 들어 + : 2개- : 1개* : 1개/ : 1개라면, +가 중복 되기에, 중복 case를 제외시켜 주어야 한다. 따라서, dfs를 이용해서dfs(현재 연산 경우의 리스트, 사용하고 남은 연산자 리스트) 로 문제 풀이를 시작한다.만약, 현재 연산자 경우의 리스트의 len이 연산자 개수라면, 해당 리스트를 total 에 append하고 return 한다. 그 외는 for i in range..
1. 문제https://www.acmicpc.net/problem/21606 2. 접근 방법이번 문제는 고생을 너무 많이 했다.........................................진짜처음에 접근 방법을 제대로 잡고 들어갔어야 했는데, 경우에 따라서 코드를 작성하다보니 너무 시간이 오래 걸렸다. 처음에는 각 vertex 별 검정 vertex 까지의 경우를 생각하면서 풀었다. 하지만, 5번 test case 에서 fail 하고 말았다.즉, 다른 접근 방법이 필요로 했다. 몇 시간을 고민하다가 다른 동료 분의 도움을 받아서 풀 수 있었다. (압도적 감사) 이런 다양한 case 들이 있었다. 이제 본격적으로 문제 접근을 해보도록 하자우선 for 문으로 각 vertex를 접근하였다. 검정 v..
1. 문제https://www.acmicpc.net/problem/1707 2. 접근 방법처음에 이분 그래프 (Bipartite Graph)를 잘 이해하지 못하여 헤맸었다.이에, 이분 그래프에 대한 설명을 찾아보게 되고 문제 풀이의 가닥을 잡게 되었다. 특정 노드에서 인접 노드로 접근하게 되면, color_num을 증가시켜서 넣어주는 방식으로 접근하였다.빨간색, 검정색으로 표현하고 싶었지만, 짝수와 홀수로 표현하는 것이 더 코드 작성이 편리할 것이라고 생각이 들었다. 만약 색이 칠해진 노드에 다시 접근하게 된다면, 저장된 color가 짝수인지 홀수인지 확인하였고, 새로이 저장하고자 하는 값과 일치하는 . 지확인하였다.일치하지 않는다면, 다른 색을 저장하려고 하게 되는 것이며, 이는 이분 그래프의 정의에 ..
1. 개요잊어버리기 쉬운 알고리즘인 Kruskal's Algorithm과 Prim's Algorithm에 대해서 공부해 보는 시간을 가졌다.두 알고리즘은 Minimum Spanning Tree를 해결하기 위한 대표적인 두 알고리즘이다. Kruskal's Algorithm은 edge가 제일 작은 값들 순으로 접근하여, 해당 edge를 잇는 정점 u, v의 parent node가 동일하지 않다면 합쳐주는 방법이다. - parent node가 동일한데, 해당 edge를 포함시키게 되면 cycle을 형성하게 될 것이기 때문이다. Prim's Algorithm은 edge가 아닌, node를 기준으로 접근하는 방법이다.일단, 특정 node를 선택하고, 해당 노드가 접근할 수 있는 노드까지의 weight 중 가장 ..