겜돌이의 개발일지

문제 백준 1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 전형적인 트리 - dfs 문제입니다. 부모가 없는 노드(입력이 -1)를 루트 노드라고 하고, 루트 노드부터 dfs를 진행합니다. 이 때 제거하는 노드 처리가 중요한데, 루트 노드를 제거하였을 때는 0을 바로 출력해줍니다. 그 이외일 때는 제거한 노드를 기억하여, dfs를 실행할 때 방문하지 않습니다. 리프 노드는 자식이 없는 노드이므로 vector의 사이즈를 확인하여, 0이면 cnt를 ++해줍니다. 또한 제거된 노드 하나만을 자식으..

문제 백준 3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 풀이 처음에는 석순과 종유석을 입력받을 때 일일이 배열을 돌며 장애물을 계산해줬는데 당연하게도 시간 초과가 났습니다. (시간 복잡도가 N*H입니다) 따라서 누적합을 통해 시간 초과를 극복하고자 하였습니다. 먼저 석순과 종유석의 높이를 입력값으로 받습니다. (N은 항상 짝수이므로 석순과 종유석이 무조건 번갈아 나옵니다.) 높이를 각각의 배열에 체크해 둡니다. 그 후 루프를 돌며 높이마다의 석순과 종유석 개수를 누적합으로 구합니다. 예를 들어 석순의..

문제 백준 17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 풀이 bfs와 dp를 섞은 듯한 재밌는 문제였습니다. q는 순서대로 현재 파이프 끝의 x좌표 / y좌표 / 상태를 저장합니다. q에다가 push와 pop을 반복하면서, 갈 수 있는 경로의 수를 파악합니다. 각각의 상태에 대해 취할 수 있는 다음 상태를 하드 코딩 했는데, 따로 함수를 만들었다면 더욱 깔끔한 코드가 되었을 것 같습니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17..

문제 백준 14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 풀이 처음에 모든 블록을 하드 코딩하려다가 뭔가 잘못된 것을 깨닫고 풀이를 참조했습니다. ㅓ, ㅏ , ㅜ, ㅗ 모양을 제외한 테트로미노는 시작 지점을 깊이가 0이라고 했을 때, 깊이가 3인 dfs로 표현할 수 있습니다. ㅓ, ㅏ , ㅜ, ㅗ 모양은 하드 코딩(elseshape)으로 따로 점검해줍니다. map을 돌면서 해당 지점에서 만들 수 있는 테트로미노의 최댓값을 저장하고, maxsum을 넘는다면 maxsum을 바꿔줍니다. 모든 map을 다..

문제 백준 11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 풀이 n = 3일때 까지의 예시입니다. 첫번째 열은 1로 초기화를 해줍니다. 두번째 열은 길이가 1인 오르막 수 입니다. 1~9까지 10개가 있습니다. 세번째 열은 길이가 2인 오르막 수 입니다. 예를 들어서, 9x에 들어갈 수 있는 x는 9 1개 입니다. (누적 : 1개) 8x에 들어갈 수 있는 x는 8, 9 2개 입니다. (누적 : 3개) 7x에 들어갈 수 있는 x는 7, 8, 9 3개 입니다. (누적 ..

문제 백준 17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 풀이 투포인터를 사용합니다. 앞과 뒤에서 인덱스를 조절하며 팰린드롬인지 검사합니다. 만약 팰린드롬이 아니라면, check를 true로 바꿔주고 유사회문인지 검사하기 위하여 isPalin함수를 재귀호출합니다. 검사 후에, isP가 true고 check가 false면 팰린드롬, isP가 true고 check가 true면 유사회문, isP가 false인 경우에는 회문이 아니므로 각각에 맞는 정답을 출력합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14..

문제 백준 1756 1756번: 피자 굽기 첫째 줄에 오븐의 깊이 D와 피자 반죽의 개수 N이 공백을 사이에 두고 주어진다. (1 ≤ D, N ≤ 300,000) 둘째 줄에는 오븐의 최상단부터 시작하여 깊이에 따른 오븐의 지름이 차례대로 주어진다. 셋 www.acmicpc.net 풀이 오븐의 지름이 위에서부터 5 6 4 3 6 2 3 이라고 하면 i >=2일때, i번째 오븐의 지름은 i-1번째 오븐보다 큰 게 의미가 없어집니다. 따라서 오븐의 지름 5 6 4 3 6 2 3은 5 5 4 3 3 2 2 와 같습니다. 이렇게 정리해 준 후에는 도우가 들어갈 수 있는 인덱스를 찾아주면 됩니다. 이진 탐색으로 풀 수도 있고 끝에서 부터 루프를 돌며 풀 수도 있었습니다. 소스 코드 루프 1 2 3 4 5 6 7 8..

문제 백준 5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 풀이 점화식이 은근 간단한데 구현에 시간이 오래걸렸습니다. dp[i][j]는 i+1번째 차례에 +, - 연산으로 숫자 j를 만들 수 있는 경우의 수를 뜻합니다. dp[0][num[0]] 부터 시작하므로 1을 넣어줍니다. 그 후 루프를 돌면서 dp[i-1][j]값이 0보다 클 경우(가는 방법이 존재할 경우) 더한 값과 뺀 값을 비교하여 조건(0이상 20이하)을 만족한다면 dp에 저장합니다. 루프가 끝난 뒤 num[N-1] 값이 나오는 경..

문제 백준 2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 N자리 숫자에서 K개만큼을 꺼내 줘야 합니다. 예제 입력 3의 경우를 보겠습니다. 10 4 4177252841 10자리 숫자에서 4자리를 제거해 가장 큰 숫자를 만들어야 합니다. 스택이 비지 않았고, 꺼낼 수 있으며, 현재 넣을 수가 stack의 top보다 클 때 stack을 pop 하고, cnt를 증가시켜줍니다. [1번째 자리] 스택에 4를 push 합니다. (stack : 4) [2번째 자리] 1은 4보다 크지 않으므로 스택에 psuh 합니다. (stack : 41) [3번째 자리] 7은 1보다 크므로 스택을 ..

문제 백준 16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 bfs로 나라를 돌면서 인구 수 차가 일정 범위 이내라면 q, checkq에 push 합니다. bfs가 끝난 뒤 checkq에 있는 나라들의 인구를 같게 만들어줍니다. 인구 이동이 발생하지 않을 때 까지 이 과정을 반복하고, 횟수를 출력합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35..