본문 바로가기

전체 글

(7)
[쓸데는 없지만, 만들고 싶어하는 PS러 ㅋㅋㅋ] 솔직히 이러고 싶지는 않은데.. ㅋㅋㅋ 갑자기 모니카가 되버렸엌ㅋㅋㅋㅋ (나 좀 살려줘 ㅋㅋㅋㅋ) 미치겠닼ㅋㅋㅋ
[BOJ16946] 벽 부수고 이동하기 4 문제는 기존 문제 변형한 것이지만, 이 문제의 알고리즘은 BFS, DFS이다. BFS는 Breadth기준으로 해서 찾는 것을 말한다. 방향의 기준으로해서 모든 경우를 찾아야 한다. 즉, 문제에서는 0은 패스하고, 1인 경우는 벽을 부수고, 이동할 수 있는 칸의 개수를 10으로 나누면 된다는 것이다. 코드는 많이 기므로, 참고용으로만 쓰길 바란다. #include #include #include #include #include using namespace std; int N, M; int map[1000][1000]; int visited[1000][1000]; int group[1000][1000]; int groupSize[1000000]; int groupNum = 1; int dir[4][2] = ..
[BOJ16724] 피리 부는 사나이 문제가 무슨 말인지를 몰라서 푸는 데 시간이 걸리는 문제이다. 힌트는 주어져 있지만... 약간, DFS와 Disjoint Set이 필요한 이유를 찾아보기는 힘들지만, 전에 이야기하듯이, find와 merge를 이용하면 쉬운 문제이다. 즉, find에서는 부모 배열에서 같은 값이 있으면 그 값을 리턴하면 되지만, 없으면 자식이 있을 때까지 찾는 것이다. 즉, 만약 자식을 찾으면 merge에서 x와 y가 같으면 끝이지만, 아니라면 SAFE ZONE이 될 수 없다는 의미인 거 같다. x = (i * m + j)로 주로 맡는다. 그럼 y는? y는 상하좌우 역할을 맡게 하면 된다. 여러 경우로 나눈 거 보면 얼핏 DFS와 유사해보인다. DFS는 Depth기준으로 하여 경우를 찾는 것을 말한다. 긴 if문을 단순하..
[BOJ4386] 별자리 만들기 또 최소 비용. 최소 비용은 MST이라고 생각이 나야 한다. 어떻게 구현하기 전 필요한 것은 star의 좌표 구조체와 간선 구조체가 필요하다. 비용은 최소 비용이므로, bool cmpCost(edge a, edge b) { return a.cost < b.cost; } cost는 두 좌표 사이의 거리가 비용이므로, 좌표와 비용을 간선 구조체에 저장한다. 그리고, 정렬은 비용 기준으로 해야 한다. 그래야 칼퇴 가능 소스는 참고용으로 /* 하늘에 n개의 별들을 이어서 별자리를 만들려고 한다. - 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다. - 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다. 별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마 두 별 ..
[BOJ2887] 행성 터널 어떻게 진행해야 할까? 이 문제는 정렬이 있는 것으로 보아 각 점에 대해서 정렬해야 해답이 볼 수 있는 건 당연하다. 알고리즘 분류에서는 정렬 뿐만 아닌 MST(최소 스패닝 트리)가 있다. MST는 최소의 비용을 산출하기 위한 알고리즘이며, 이 문제는 최소 비용을 구하는 프로그램이 주된 목적이므로, 정렬을 먼저 한 다음, MST를 활용한다면 아무런 문제 없이 풀 수 있다. 물론, MST는 처음 들어 보신 분이라면 난감할 수 있다고 생각한다. 최소 스패닝 트리는 무엇일까? 어떤 정점과 다른 정점 사이의 비용을 가지고, find와 merge를 이용하여 최소 비용을 찾아내는 방식이다. 이 설명이 맞는지 모르겠지만, geeksforgeeks에서 검색해보면 더 자세한 설명이 나와 있을 것이다. 정렬 기준은 x, ..
[BOJ 11257] IT 시험 이 문제는 간단한 조건이 문제에 적혀 있으므로, 그것을 찾아내고, 코드를 작성하면 된다. 전략 분야 35점의 30%, 경영 분야 25점의 30%, 기술 분야 40점의 30% 즉, 35*0.3의 값 이상이 되어야 한다는 것. 총점은 55점 이상 전략+경영+기술의 값이 55이상이라는 것 import sys N = int(sys.stdin.readline()) for i in range(N): number, S, G, T = map(int, sys.stdin.readline().split()) total = S + G + T # S의 값이 35점의 30%이상이면서, G의 값이 25점의 30%이상이면서, T의 값이 40점의 30%이상이면서, 총점이 55점 이상이면 PASS if S >= 35 * 0.3 and ..
[BOJ2473] 세 용액 전체 용액의 수: N 용액의 특성값의 범위는 광범위한 상태이다. 이를 일일이 확인하면 TLE가 되므로, 이분 탐색이 낫다. 이분 탐색은 왼쪽과 오른쪽을 서서히 중앙으로 모이게 만드는 전략이다. 하지만, 이분 탐색은 두 용액이면 유용하겠지만, 세 용액은 오히려 더 힘든 상태이다. 그래서 사용하는 것이 투 포인터이다. 투 포인터에 관한 설명은 geeksforgeeks에 잘 되어 있다. https://www.geeksforgeeks.org/two-pointers-technique/ Two Pointers Technique - GeeksforGeeks A Computer Science portal for geeks. It contains well written, well thought and well expla..