코딩하기 좋은날

https://www.acmicpc.net/problem/4195 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 이 문제는 유니온 파인드 구조를 사용해서 해결을 하여야 하는 문제입니다. 다만 조금 까다로운게 string을 처리해야 하는 문제입니다. 따라서 저는 map을 이용하였고 map parent; 을 선언하여 key값은 사람의 이름을 저장하였고 value값은 pair로 저장하였는데 pair의 first값은 key값의 부모의 이름을 저장하였고 pair의 second값은 key값이 속해있는 그래프의 친구 명수를 저장하였습니다. 저는 이문제를 아예 다 string으로 처리해서 코드가 좀 지저분하게 작성 되었습니다. 다른분들을 보니 union-find 연산시에는 각 들어오는 친구에게 번호를 부여하여 ..

https://www.acmicpc.net/problem/4485 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 이문제는 이전글인 1261번 알고스팟과 유사한 문제입니다.(거의 동일합니다) 시작점에서 N-1,N-1까지 가면서 잃는 금액이 가장 최소가 될때 금액을 구하는 문제입니다. 따라서 다익스트라 알고리즘을 통해 최단경로를 구해야 하고 그래프가 N*N행렬 형태로 주어지고 각 노드에서는 상하좌우로 이동할수 있으므로 각 노드는 상하좌우의 노드와 연결되어 있다고 생각 하고 풀면 됩니다. 다음은 코드입니다. #include #include #include using namespace std; #define INF 987654321 int arr[130][130]; priority_queue pq; in..

https://www.acmicpc.net/problem/1261 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 이 문제는 최단경로를 구하는 문제입니다. 출발점에서 N,M까지 가는데 부숴야 하는 벽의 최소 개수를 구해야 하므로 출발지에서 N,M까지의 최단경로를 구하면 해결 할 수 있습니다. 따라서 다익스트라 알고리즘을 통하여 해결하면 됩니다. 노드와 간선으로 정보가 주어지는 것이 아니라 N*M의 판에 대한 정보가 주어지므로 i,j에 위치했을 때는 상 하 좌 우로 이동이 가능하므로 상하좌우 노드와 현재의 노드가 연결 되어 있다고 생각하고 문제를 해결하면 됩니다. 다음은 코드입니다. #include #include #include #include using namespace std; #define I..

Python의 Pyqt5라는 GUI 라이브러리를 이용하여 단어장 프로그램을 만들어 보았습니다. GUI 프로그래밍을 하고 싶어서 무작정 찾아보며 만들어 보았습니다. 기본적으로 이 프로그램은 항상 창에서 상단에 위치하도록 설정되어 있어서 창을 이동하거나 해도 항상 자신의 위치에 떠있습니다. 따라서 계속해서 단어를 볼 수가 있습니다. 단어 같은 경우는 파일 입출력을 이용하였기 때문에 압축을 푸시면 word.txt 라는 텍스트 문서가 있습니다. 그 문서에 아래와 같이 한줄 간격으로 원하는 단어 / 뜻을 적으면 단어가 추가 됩니다. 그리고 우측 하단을 보시면 트레이 아이콘이 있습니다. 트레이 아이콘을 우클릭시 아래와 같은 모습이 나오며 뜻 테스트/ 단어 테스트를 눌러 원하는 테스트를 볼 수 있습니다. 테스트는 저..

https://www.acmicpc.net/problem/1541 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 이 문제는 수식을 입력받았을때 괄호를 적절히 쳐서 최소의 값을 만드는 값을 출력하는 문제입니다. 부호는 +와-밖에 나오지 않으므로 -가 한번이라도 나오면 그 뒤부분은 모두 -로 처리할 수 있음을 알 수 있습니다. 예를들어 2+3-4+5-6+2 라면 -4가 나온순간 4 와 5를 묶고 6과 2를 묶으면 모두 -로 처리 할 수 있습니다. 따라서 그리디하게 처음 - 가 나올때까지의 숫자들과 그 이후 숫자들을 나누어서 서로 합해주면 답을 구할 수 있습니다. 다음은 코드입니다. #include #include using namespace std; int main(void) { ios_base::s..

https://www.acmicpc.net/problem/6549 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 이 문제는 주어진 히스토그램에서 넓이가 가장 큰 직사각형을 구하는 문제입니다. n이 10만 까지있으므로 당연히 모든 넓이를 다 해보는 방법으로는 해결을 할 수 없습니다. 따라서 저는 이 문제를 스택을 이용하여 해결을 하였습니다. 스택을 이용하여 높이가 스택의 top보다 높으면 계속 진행하고 그렇지 않으면 현재 집어넣을 높이보다 높이가 낮아질 때까지 pop하면서 그사이에 존재하는 직사각형의 넓이를 계산해주면서 끝까지 진행해주면 답을 찾을 수 있습니다. 넓이를 계산할 때 현재 높이에 해당하는 부분은 s.top 부분이고 밑변에 해당하는 부분은 top의 원소를 빼준뒤 그다음 top원소가 존재하..

https://www.acmicpc.net/problem/1916 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 이 문제는 원래 다익스트라로 풀어야 하지만 연습겸 벨만포드로 풀어보았습니다. 벨만포드 알고리즘 같은경우 음의 가중치가 있을때 다익스트라를 사용할 수 없으므로 그때 사용을 합니다. 이때 시간복잡도는 O(|V||E|) 만큼 소요되므로 사실 이문제의 입력 최대치를 넣으면 1억이 됩니다. 그래서 시간초과가 나지 않을까 했는데 찾아보니 요즘 컴퓨터는 1억번 반복은 1초안에 해결을 할 수 있으므로 시간초과가 나지 않고 문제가 풀립니다! 간략하게 알고리즘을 설명하면 V-1번의 반복동안 각 정점에서 연결된 정점으로 가는 비용을 완화(더적은 비용이 있으면 그비용으로 교체)시키면서 진행합니다. 벨만포드 ..

https://www.acmicpc.net/problem/11404 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 이 문제는 최단경로 알고리즘중 하나인 플로이드 와샬 알고리즘을 통해서 해결하는 문제입니다. 모든정점과 다른정점들간의 최단경로를 구할때는 O(V^3)이 걸리는 플로이드 와샬 알고리즘이 가장 빠르기 때문에 이를 이용하면 되고 방법은 DP를 이용하여 dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]) 라는 점화식을 통하여 k정점을 경유하여 갈때와 기존의 저장된 값과 비교하여 더작은 값을 넣어주면 마지막에는 최단경로가 모두 저장되게 됩니다. #include #include using namespace std; #define INF 987654321 int V,m; ..