끄적끄적 끄적끄적

위 예시 그림처럼 숫자를 삼각형으로 순환하며 배열에 삽입하는 문제이다. 저 그림을 배열에 넣기 쉽게 바꾸면 아래처럼 된다. 1) n = 4 1 2 9 3 10 8 4 5 6 7 2) n = 5 1 2 12 3 13 11 4 14 15 10 5 6 7 8 9 switch문에서 아래(0), 오른쪽(1), 위(2) 이렇게 세 방향을 dir 변수로 설정해주고, 각 dir에 맞게 배열을 채워넣는다. 한 방향으로 수를 채워넣는 횟수는 n, n-1, n-2 ... 1씩 줄어들기 때문에 반복문은 각 방향에 대해 아래와 같이 설정한다. for(int i = 0; i < n; i++){ for(int j = i; j < n; j++){ ... } } arr[x][y]에서 i) 아래(0) 방향으로 갈 때 : x는 1씩 증가..

단순한 경우의 수 계산 문제인줄 알고 수학적으로 접근했다가 엄청 헤멨다. 처음에는 현재 관리자를 포함해 나올 수 있는 경우의 수를 다 센 다음에 열쇠를 건네받을 수 없는 경우만 따로 빼는 식으로 계산했는데, 이게 내가 생각한 것보다 따져야할 경우의 수가 너무 많아서 숫자가 자꾸 틀렸다. 결국 검색을 해봤는데 비트마스킹으로 일일이 경우의 수를 계산하는 문제였음... (참고한 코드는 여기 : willbfine.tistory.com/330) A, B, C, D가 i번째 날에 나오는 경우의 수는 총 2^4 - 1 = 15가지이고, 최대 날 수는 10000이므로 dp[10000][16] 크기의 배열을 생성해서 각 날마다의 경우의 수를 일일이 계산해주고, 총 경우의 수는 dp[10000][1]부터 dp[10000]..

문제는 간단해보였는데 생각보다 너무 오래걸렸다... 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를 끝까지 돌았음에도 목적지에 도달하지 못하..

string 형태의 전화번호 목록이 주어지면 해당 목록이 일관성 유무를 반환하는 문제이다. 여기서 일관성이 있다는 것은, 한 번호가 다른 번호의 접두어인 경우가 없다는 뜻이다. 이 문제를 선택한 이유는 트리 문제였기 때문이다. 그래서 웬만하면 트리로 풀고 싶었는데... 내 머리로는 이진트리밖에 생각이 나지 않아서 이걸로 어떻게 이 문제를 풀어야할지 감이 안잡혔다. 그래서 일단은 쉽게 정렬로 풀었다. 전화번호 목록을 오름차순으로 정렬한 다음, 앞에서부터 번호들을 비교해 이전 번호가 다음 번호의 접두어가 되는지 일일이 확인했다. 정렬만 하면 쉽게 해결됐던 문제... [정렬로 해결한 코드] // 5052_전화번호_목록 using namespace std; #include #include #include #in..

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