끄적끄적 끄적끄적

문제는 간단해보였는데 생각보다 너무 오래걸렸다... 1) 도착점 C가 2개인 점 2) 같은 방향으로 2번 연속 이동할 수 없다는 점 3) 방문했던 점도 다시 방문할 수 있다는 점 이 세 조건을 만족시키면서 BFS를 수행하면 된다. 사실 1, 3번 때문에 많이 헤맸다... C가 2개이기 때문에 두 점이 명확히 구분되도록 하나는 C, 다른 하나는 D로 바꿔주었다. 또한 S도 2번 이상 방문될 수 있기 때문에 S의 좌표는 따로 저장해놓은 다음 .으로 바꿔주었다. visited 배열은 5차원 배열로 구체화시켜서 같은 상태로 중복 방문을 할 수 없도록 했다. visited[MAX][MAX][dir][C][D] 예를 들어 visited[3][4][2][0][1] = 1이면, (3, 4) 지점을 왼쪽에서 진입한 상태..

삼성 A형 문제 중 하나인데 삼성은 브루트 포스를 좋아하나보다... 수식이 주어지면 수식에 적절하게 괄호를 넣어 최대 결과값을 구하는 문제이다. 중첩 괄호는 허용되지 않고, 괄호 안에는 연산자가 1개만 들어있어야 한다. 수식을 string으로 입력받은 후 숫자는 숫자끼리, 연산자는 연산자끼리 따로 배열에 저장했다. 그 다음 dfs를 사용해 "현재 연산자"를 기준으로 괄호를 추가하는 경우와 그렇지 않은 경우로 나누어서 연산을 수행했다. 예를 들어, 3 + 8 * 7 - 9 에서 현재 연산자가 +인 경우, 1. 현재 연산자를 기준으로 괄호 추가 (3 + 8)을 계산한 후 다음 연산자인 * 대해 dfs(*, 11) 수행 2. 다음 연산자를 기준으로 괄호 추가 (8 * 7)을 계산한 후 현재 피연산자(3)를 계..

파이프를 이동할 수 있는 경우의 수를 구하는 문제이다. 파이프 크기는 2X1이고, 오른쪽으로만 이동할 수 있으며, 가로, 세로, 대각선 방향으로만 이동할 수 있다. 2칸을 차지하긴 하지만 결국 끝점이 목적지에만 있으면 되기 때문에 끝점만 보면 된다. 보자마자 bfs dfs가 생각나서 dfs를 시도했다. 한번에 45도밖에 회전을 못하기 때문에 곧바로 "가로->세로, 세로->가로"로 이동할 수 없음을 주의하자. (반드시 대각선 선 상태를 거쳐야 함. 이거땜에 삽질....) dfs를 돌 때 현재 파이프 상태가 가로인지, 세로 또는 대각선인지 매번 저장해주고, 각 파이프 상태에 따라 이동이 가능한지를 벽의 유무를 통해 확인한다. 1. 가로/세로 상태일 때는 다음 정점(house[nx][ny])에 벽이 있는지 확..

제목 어그로에 이끌려서 풀게 된 문제... 전형적인 BFS 문제인데 문제 조건을 잘못 이해해서 좀 헤맸다ㅠ 힘이랑 장애물 위치, 높이 정보가 주어지면 힘이 0이 될 때까지 목적지에 도달할 수 있는지 여부를 출력하는 문제이다. 한번 이동할 때마다 힘이 1씩 감소하고, 현재 위치보다 이동할 위치의 높이가 높으면 남아있는 힘이 (이동할 위치의 높이 - 현재 위치의 높이)보다 크거나 같아야만 이동할 수 있다. 난 이 조건을 잘못 이해해서 높이 차만큼 힘도 같이 감소되도록 코드를 작성해서 틀렸다. 해당 조건은 그냥 제약사항일 뿐 힘의 감소에는 영향을 미치지 않는다는 것을 주의하자. 아무튼 조건에 맞게 힘을 감소시켜주고 bfs를 돌면서, 목적지에 도착하면 true, bfs를 끝까지 돌았음에도 목적지에 도달하지 못하..

컴퓨터들의 의존성을 보고 해킹된 컴퓨터 수와 걸리는 시간을 출력하는 문제이다. 보자마자 그래프 문제여서 다익스트라를 쓰려고 했는데 너무 오랜만에 다익스트라를 써서 기억이 안났다.. 그래서 다익스트라 코드는 아래 블로그를 참조했다. (alswnsdl.tistory.com/13) 다익스트라 알고리즘(Dijkstra's algorithm) C++ 코드 다익스트라 알고리즘의 개념은 이전 게시물 http://alswnsdl.tistory.com/12 을 참고 하시면 됩니다. 이번에는 다익스트라 알고리즘의 소스코드에 대해 적어보겠습니다. 다익스트라의 소스코드는 두가 alswnsdl.tistory.com 이 문제에서 주의할 점은, 의존성이 a, b, s 순서대로 주어지므로 그래프 방향은 a -> b가 아닌 b -> ..

n일동안 상담 일정을 적절히 잡아 최대 이익을 구하는 문제이다. 처음 문제를 보자마자 생각난 알고리즘은 DP였지만... 효율적인 공식이 생각나지 않아 결국 DFS로 방향을 틀었다. 일하는 날짜(start), 현재까지의 이익(cur_profit)을 인자로 받고, start부터 n일까지 dfs를 돌면서 일할 수 있는 모든 경우를 탐색하면 된다. 딱히 어려운 점은 없었지만, 처음에 start가 n보다 크면 dfs를 종료하도록 코드를 짰다가 마지막 날(n일)에 일하게 되는 경우가 제외되어 최대 이익이 제대로 계산되지 않았다. 그래서 start > n + 1로 수정해주었고 결국 맞았다. if (visited[start] || start > n + 1) return; // 14501_퇴사.cpp #define _C..

입력으로 날 수와 각 날의 주가가 주어졌을 때 최대 이익을 구하는 문제이다. 처음 이 문제를 봤을 때 제일 먼저 생각난 방법은 DP였다. 하지만 DP로 하기에는 주어진 숫자가 너무 크기도 했고... 단순히 감소하는 시점에 팔아버리는 것으로 구현하면 뒤에 더 고점이 나왔을 때 반례가 존재하기 때문에 이 방식은 포기했다. 내림차순으로 sorting한 후에 이익을 계산해볼까도 했지만, 이 경우 sorting시 순서도 같이 기억해야했기 때문에 포기.. 결국 내가 선택한 방법은 뒤에서부터 반복문을 돌아서, 이전까지의 최대 주가보다 현재 주가가 더 크면 최대 주가를 갱신하고, 반대로 현재 주가가 더 작으면 차익만큼을 플러스하는 식으로 구현했다. 예를 들어 주가가 cost[8] = 4 1 2 4 5 6 2 2 이렇게..

테트로미노가 놓인 칸 수의 최대값을 구하는 문제이다. 처음에 DFS를 쓸까 하다가... 복잡할 것 같아서 그냥 Brute Force를 썼다. 아래 5가지 모양에 대한 모든 경우의 수를 지정해줘야 한다. 먼저 제일 쉬운 긴 직사각형 모양과 정사각형 모양의 좌표를 지정해준다. // 직사각형 {{0, 0}, {0, 1}, {0, 2}, {0, 3}}, {{0, 0}, {1, 0}, {2, 0}, {3, 0}} // 정사각형 {{0, 0}, {1, 0}, {0, 1}, {1, 1}} 그 다음 ㄹ형 모양과 ㅗ형 모양의 좌표를 지정해준다. 문제에서 회전뿐만 아니라 대칭까지도 허용한다고 했으므로, 각 모양의 경우의 수는 총 4가지이다. // ㄹ형 {{0, 0}, {1, 0}, {1, 1}, {2, 1}}, {{0, ..