https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net BFS를 이용해 퍼즐을 풀 수 있습니다. 0의 위치를 기준으로 BFS를 돌리면 됩니다. 하지만 메모리가 아주 작기 때문에 배열이 아닌 string을 활용해 map의 키로 활용하여 해당 string이 조회되었는지 확인합니다. 코드는 다음과 같습니다. #include #include #include #include #include #include using namespace std; int dx[4] = { 0,0,-1,1 }; int dy[4] = { 1,-1,0,0 }; /..
https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 그래프가 주어져 있을 때 최소 스패닝 트리 (MST) 를 만드는 문제입니다. 전체 간선을 오름차순으로 정렬 후, 크루스칼 알고리즘을 통해 최소 스패닝 트리를 만들면 됩니다. 크루스칼 알고리즘을 이용해 MST를 만들면 모든 마을을 이을 수 있는 최소 경로를 찾을 수 있게 되고 이 때 마지막 가중치를 가지는 간선 (연결 가능한 간선 중 가중치 최대) 인 것을 빼면..
https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 정말 주어진대로 구현만 되는 문제였습니다. 좀 더 간단하게 풀 수 있을 거 같지만, 잠이 와서 그냥 하드코딩으로 했습니다..... 토네이도가 이동할 때 이동하는 방향에 따라 모래가 분리되는 비율이 달라지는 것만 주의하면 크게 어려울 것이 없습니다. 주어진 비율대로 모래를 구하고, 소수점은 그냥 버리면 됩니다. 날려간 모래는 해당 위치에 더해줍니다. 그리고 알파 위치..
https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 해당 문자열이 회문인지 아닌지, 그리고 한 글자를 뺐을 때 회문인지 판단하는 문제입니다. 단순히 한글자 씩 빼서 회문인지 검사하면, string의 최대 길이가 100,000 이하 이므로 최악의 경우 100,000 * 50,000 번의 검사를 해야합니다. (한 번에 2개 문자 검사 가정) 그러므로 투 포인터를 응용하여 해당 문자열이 회문인 경우 계속 진행하고, 서로 다른 문자가 나온 경우, check count를 1개 올려줍니다..
https://www.acmicpc.net/problem/10266 10266번: 시계 사진들 상근이는 보통의 시계와는 다른 독특한 시계 사진 두장이 있습니다. 시계는 n개의 동일한 길이와 목적을 가진 시계 바늘들을 가지고 있습니다. 애석하게도 시계의 숫자들은 희미해져 각 시계 바 www.acmicpc.net 시계의 침만 주어진 두 시계가 시간이 일치할 확률을 구하는 문제입니다. 주의할 점은 침이 일정한 규칙을 가지고 있지 않기 때문에, 1 2 3 4 와 4 2 1 3 은 possible을 가집니다. KMP알고리즘을 이용하여 간단히 구할 수 있습니다. (KMP라는 것을 생각하기 좀 어려웠다... 처음에는 각으로 계산하려했다) 우선, 입력값은 0