본문 바로가기
반응형

Problem Solving/프로그래머스14

프로그래머스 빛의 경로 사이클 - C++ 풀이 1. 기존의 노드를 도착한 빛의 방향에 따라 4개의 노드로 쪼갠다. 2. 그리드의 문자열 값에 따라 방향 간선을 추가한다. 3. DFS로 모든 노드를 방문하면서 사이클을 모두 찾아낸다. 1. 기존의 노드를 도착한 빛의 방향에 따라 4개의 노드로 쪼갠다. 노드에 빛이 도달할 때 4가지 경우가 있다. 북쪽에서 도달한 경우, 동쪽에서 도달한 경우, 남쪽에서 도달한경우, 서쪽에서 도달한 경우. 이 4가지 경우는 모두 다른 경우이기 때문에 기존 노드들을 모두 4개로 쪼개서 도달한 빛의 방향에 따라 다른 노드로 보자. 2. 그리드의 문자열 값에 따라 방향 간선을 추가한다. 이제 그리드의 문자열 값에 따라 방향 간선을 추가하여 그래프를 완성한다. L, R인 경우 방향을 전환해주고, 해당 방향으로 1만큼 떨어진 노드로.. 2023. 9. 16.
프로그래머스 에어컨 - C++ 풀이 1. dp(currTemp, t): 현재 시각이 t초이고, 현재 온도가 currTemp일 때 남은 시간동안 쾌적함을 유지하기 위한 최소비용 2. 1도 올리는 경우, 1도 내리는 경우, 희망온도를 현재온도로 유지하는 경우, 아예 끄는 경우 중 비용이 최소인 경우를 선택한다. 1. dp(currTemp, t): 현재 시각이 t초이고, 현재 온도가 currTemp일 때 남은 시간동안 쾌적함을 유지하기 위한 최소비용 dp(currTemp, t)를 위와 같이 정의하자. 2. 1도 올리는 경우, 1도 내리는 경우, 희망온도를 현재온도로 유지하는 경우, 아예 끄는 경우 중 비용이 최소인 경우를 선택한다. 어차피 온도는 1초마다 1씩만 내려가거나 올라갈 수 있다. 따라서 희망온도는 신경쓰지 않아도 된다. 현재 온도가 .. 2023. 9. 7.
프로그래머스 혼자서 하는 틱택토 - C++ 풀이 1. 올바르게 틱택토를 플레이할 때 나올 수 있는 모든 보드를 구한다. 2. 모든 보드 중에 주어진 보드가 있는지 확인한다. 1. 올바르게 틱택토를 플레이할 때 나올 수 있는 모든 보드를 구한다. 보드가 9칸 밖에 되지 않기 때문에 가능한 모든 보드 상태를 구해도 충분하다. 재귀를 이용하여 모든 케이스를 구해주자. 2. 모든 보드 중에 주어진 보드가 있는지 확인한다. 이제 모든 케이스와 주어진 보드 상태를 비교하여 주어진 보드와 같은 케이스가 존재하는지 확인해주면 된다. #include #include using namespace std; vector allCases; bool isEqual(char a, char b, char c) { return a == b && b == c; } bool isFin.. 2023. 9. 5.
프로그래머스 당구 연습 - C++ 풀이 1. 4개의 벽면을 맞추는 경우를 모두 탐색하고 최소거리를 구한다. 2. 만약 벽면에 맞기 전에 공을 먼저 맞는 경우 원쿠션이 되지 않으므로 제외한다. 1. 4개의 벽면을 맞추는 경우를 모두 탐색하고 최소거리를 구한다. 벽면이 총 4개 있으므로, 각 벽면을 맞추는 경우를 모두 탐색한 다음 최소거리를 구하면 된다. 벽면을 맞추고 공을 맞추기 위해 이동해야 하는 거리는 해당 벽면을 기준으로 목표공을 대칭이동 시킨 뒤 시작점과의 거리를 계산하면 된다. 2. 만약 벽면에 맞기 전에 공을 먼저 맞는 경우 원쿠션이 되지 않으므로 제외한다. 주의해야 하는 부분은 벽면을 맞추고 난 뒤에 목표공을 맞추는 것이 불가능할 수 있다는 점이다. 벽면으로 가는 경로에 목표공이 존재하는 경우에 해당한다. #include #incl.. 2023. 9. 5.
프로그래머스 리코쳇 로봇 - C++ 풀이 1. BFS를 사용하여 최단 거리를 구한다. 1. BFS를 사용하여 최단 거리를 구한다. 전형적인 BFS 문제이다. 각 칸을 노드로 생각하고, 일직선으로 쭉 이동했을 때 도달하는 칸을 인접 노드로 생각하고 BFS를 수행하면 된다. 중간에 G인 칸에 도달하면 바로 종료. 시작 지점에서 가능한 모든 노드를 방문했는데도 G 칸을 방문하지 못했다면 불가능한 경우이다. #include #include #include #include using namespace std; typedef pair pii; const int INF = 987654321; int N, M; int dr[] = {-1, 1, 0, 0}; int dc[] = {0, 0, -1, 1}; pii findStartPoint(vector& boar.. 2023. 9. 5.
반응형

티스토리툴바