[백준 python] 9658번 돌 게임 4 - 동적프로그래밍 레벨: 실버2 언어: python 문제풀러가기 9658번: 돌 게임 4 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 📑풀이 과정 DP를 이용해서 풀이할 수 있는 문제이다. 나는 이 문제를 풀기 위해 돌이 N개 있을 때 후공자의 승패 여부를 dp 배열에 저장하고 사용하였다. dp[N]이 True 면 선공자의 승이면서 후공자의 패이다. 아래의 표와 같이 후공이 지고 이기는 상황을 알 수 있다. 이때 돌이 N개 일때 누가 이기는 알기 위해서 N - 1 일때 N - 3 일때 N - 4 일때 후공자가 승인지 패인지를 보면 현재 게임에서 누가 이기는지 알 수 있다. 상근이가 돌을 가져가는 갔을 때..

[백준 python] 2225번 합분해 - 동적프로그래밍(DP) 레벨: 골드 5 언어: python 문제풀러가기 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제설명 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 입력값 첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다. 출력값 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. 📑풀이 과정 DP 동적프로그래밍은 문제를 보고 식을 만들 수 있으면 쉽게 풀..

[백준 python] 2579번 계단 오르기 - 동적프로그래밍(DP) 레벨: 실버 3 언어: python 문제풀러가기 문제설명 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟..

[백준 python] 2644번 촌수 계산 DFS 레벨: 실버2 언어: 파이썬 문제풀러가기 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 문제 설명 우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버..

백준 1012번 유기농 배추 레벨: 실버2 언어: python 문제풀러가기 문제설명 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다. 한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는..

백준 4375번 레벨: 실버 3 언어: python 문제풀러가기 문제설명 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. 이 설명을 듣고 이해가 잘 되지 않아서 찾아보았다. 예제 3이 출력에서 3으로 나오는 이유은 3의 배수 중에서 '111'이 1로만 이루어진 배수여서 '111'의 자리수가 3이기 때문에 출력이 3으로 나온다. 입력값 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다. 출력값 1로 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력한다. 📑풀이 과정 처음에는 브루트포스 문제여서 가장 단순하게 생각했다. 주어진 수에 직접 수를 곱하여 모든..

최종합격 감사합니다! ㅎㅎ 면접 보고 하루만에 결과가 나왔다. 최종 합격! SW정글을 준비하면서 다양한 블로그의 후기를 보고 도움을 많이 받았다. 감사합니다!! 나도 다음 기수분들이 도움이 될 수 있도록 내가 준비했던 내용과 후기를 작성해 본다. SW 정글 홈페이지 지원동기 일단 나는 전공자이고 스타트업에서 3개월 인턴도 해보았다. 어느 정도 기초는 있는 상태로 지원했다. 대학을 졸업하고 취업을 해야하는데 나의 실력이 많이 부족함을 느꼈고 집에서 2개월 정도 독학을 하면서 준비했다. 하지만 혼자서 독학하는 것에 한계를 느끼고 몰입할 수 있는 환경인 SW정글을 지원했다. 그리고 전공자이지만 학부 수업을 열심히 하지 않아서 자료구조, 알고리즘 같은 전공 지식이 많이 부족해서 전산학 기초도 보강하고자 지원하게..

백준 2805번 문제 나무자르기 이진탐색 레벨: 실버3 언어: JavaScript 문제풀러가기 문제설명 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15,..