케이스윔의 개발 블로그

문제1부터 N까지 마을이 있을 때 마을을 순회할 수 있는 최소비용을 구하시오.문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/2098) 풀이이 문제는 Bitmask를 사용해서 dp를 만들어 나가보려고 푼 문제입니다. 여기서는 모든 마을을 순회해야할 때 방문한 마을을 표시하기 위해 Bitmask를 사용해보았습니다. dp를 통해 문제를 풀기 위해 배열이 필요하고, Bitmask를 사용한다면 어느 마을을 방문했는지 알 수 있으므로 dp배열에서 바로 사용을 할 수 있게 됩니다. 1번 마을을 방문했다면 1이고, 2번 마을을 방문했다면 10, 3번 마을을 방문했다면 100, 세 마을을 전부 방문했다면 111로 표현할 수 있습니다. 이 때 특정한 i번째의 마을을 방문했는지 알려면..

문제N, L, R이 주어진다. N개의 건물을 왼쪽에서 보았을 때는 L개가 보이고 오른쪽에서 보았을 때 R개가 보이는 경우의 수를 구하시오.문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/1328) 풀이처음에 보자마자 너무 어렵다고 생각이 들었습니다! 그리고 아주 이상한 방법으로 많이 접근을 했습니다. 다이나믹 프로그래밍 카테고리에서 골랐기 때문에 dp로 풀어야겠다는 생각은 들었지만 점화식을 세울 수 없었습니다. 처음엔 1~N까지의 건물이 주어질 때 높이가 N인 건물을 고정시키면 왼쪽, 오른쪽으로 경우의 수를 쪼갤 수 있어서 그 방법을 통해서 시도해보려 했지만 너무 어렵고 무식한 방법이었습니다. 결국 다른 분들이 풀이한 것들을 보고 힌트를 얻어서 풀었습니다. N-1개의..

문제각 배열의 원소가 주어지고, i, j, x, y가 주어질 때 (i, j)칸에서 (x, y)칸까지의 합을 구하시오.문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/2167) 풀이처음에는 단순히 일렬로 놓여있는 배열이라 생각하고 (i, j)칸에서부터 (x, y)칸까지의 합을 구하는 줄 알았는데 그게 아니라 사각형을 그린다고 했을 때 왼쪽 위의 점이 (i, j)이고 오른쪽 아래점이 (x, y)인 것이었습니다. 어떻게하면 숫자가 크지 않다면 2중 for문을 통해서 구할 수도 있겠지만 합을 구해야하는 경우의 수가 최대 10000개가 될 수 있기 때문에 dp를 이용해야했습니다. 처음엔 전.혀 감이오지 않아서 넘겨버렸던 문제였는데 그림을 그려서 생각해보니 쉽게 생각할 수 있었..

문제로봇이 동서남북 4개의 방향 중에 하나를 선택해서 이동하는데 N번의 행동을 취한다. 같은 곳을 한 번보다 많이 이동하지 않을 때, 로봇의 이동 경로가 단순하다고 한다. 각 방향으로 이동할 확률이 주어질 때 로봇의 이동 경로가 단순할 확률을 구하는 프로그램을 작성하시오.문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/1405) 풀이같은 곳을 한 번보다 많이 이동하지 않는 이동경로 = visited 배열이 0인 곳만 방문하는 경우를 의미합니다. N은 14보다 작거나 같으므로 visited 배열을 만들기 위한 값을 생각해보면 동, 서, 남, 북쪽으로만 N번 이동할 수 있으므로 (2*N)*(2*N)의 크기가 필요합니다. 출발점은 N, N이라고 생각할 수 있습니다. 그 다..

문제개수 N이 주어지고 가능한 모든 N*(N+1)/2개의 구간의 합에 대한 부호가 주어질 때, 수열 N을 구하시오.문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/1248) 풀이처음에 어렵다고 느껴서 헤맸던 문제입니다! N이라는 숫자가 주어지고 구간의 합의 모든 조합에 대한 +, -, 0가 주어질 때 이 모든 조건을 만족하는 수열을 구해야합니다. 처음에는 입력을 1차원 배열로 받다보니 i번째 자신에 대한 부호를 찾는 것도 몇번째에 위치하고 있는지 계산을 해야해서 복잡해졌습니다. 그래서 이 방법을 처음에 시도했다가 배열을 N*N으로 만들어서 첫째 줄에서는 N개를 사용, 두번째 줄에는 N-1개를 사용하도록 했습니다. 그렇게 하니 i번째 자리의 부호를 알기 위해서는 nu..

문제2차원 배열로 빙산이 주어졌을 때, 1년이 지날 때마다 0인 바닷물과 인접한 만큼 빙산의 높이가 줄어든다. 한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하시오.문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/2573) 풀이정답율이 낮은 문제여서 어려울 줄 알았는데 빙산을 녹이는 부분, BFS(또는 DFS)를 통해서 빙산의 덩어리가 두덩어리로 나누어질 때를 확인해주면 되는 문제입니다. 처음엔 이중 for문을 통해서 각 칸에서 빙산이라면 얼마나 녹아야하는지를 탐색하려했는데 빙산이 아닌 부분(0인 곳)이 많을 경우에는 시간이 많이 걸릴 것 같아서 처음 입력을 받을 때 queue를 통해서 따로 빙산을 저장해줬습니다. 그 다..

문제레이저, 쇠막대기를 표시하는 string이 들어올 때 레이저에 의해 잘리는 쇠막대기의 개수를 구하시오.문제 출처: 프로그래머스(https://programmers.co.kr/learn/courses/30/lessons/42585) 풀이문제가 레벨2인데도 처음에 보고는 좀 어렵다고 생각했습니다. 근데 매우 간단한 문제였습니다! '('와 ')'가 연속으로 들어올 때에는 레이저를 쏜 것이고 아닐 때의 '('는 쇠막대기의 시작, ')'는 쇠막대기의 끝을 의미합니다. 쇠막대기가 들어오면, 즉 '('이면 스택에 쌓아줍니다. 쇠막대기가 끝나면=')'이면 스택에서 pop해줍니다. 이러한 과정에서 '('와 ')'이 연속으로 들어오면, 레이저를 쏘게되면 그 때 쌓여있는 스택의 사이즈만큼 쇠막대기가 생겨납니다. answ..

문제 파일명에 포함된 숫자를 반영하여 정렬하는 프로그램을 구현하시오.문제 출처: 프로그래머스(https://programmers.co.kr/learn/courses/30/lessons/17686) 풀이파일명이 주어지면 head, number, tail로 나눈 다음 정렬을 통해 쉽게 구할 수 있는 문제였습니다. head에는 숫자가 포함되지 않기 때문에 숫자가 나오는 순간부터는 number 영역이고, char로 입력된 number 영역은 int형으로 바꿔줘야합니다. head와 number를 구하고 input에서 해당 input의 인덱스와 함께 구조체로 vector에 넣어주었습니다. index를 구조체에 넣은 이유는 stable하게 정렬하기 위해서, 값을 편하게 고쳐서 구조체에 넣기 때문에(전부 소문자로 바꾸..