프로그래머스 무인도 여행 https://school.programmers.co.kr/learn/courses/30/lessons/154540 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 전 나의 생각 BFS를 사용하여 공간을 탐색하는 문제다. 우선 식량이 있는 무인도를 탐색하기 위해선 양방향 탐색이 필요하다. 하지만 양방향 탐색을 하면서 오류가 날만한 상황을 모두 배제해줘야 한다. 1. 탐색할 다음 위치가 배열의 크기를 벗어나면 안된다. 2. 탐색할 다음 위치가 방문한 곳이 아니면서 X(바다)가 아니여야 한다. 두 조건을 만족할 시 다음 탐색 위치..
분류 전체보기
백준 15486 https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 풀이 전 나의 생각 본래 퇴사1 문제는 경우의 수가 적어서 DFS로 풀이가 가능했다. 하지만 퇴사2에서는 무려 N이 1500001까지 가능하기 때문에 무조건 DP로 풀어야한다. 이 문제의 포인트는 특정 날짜까지 최대 얼마를 벌 수 있는지 처음부터 탐색하는 것이다. 문제에서 나온 첫 예시를 기준으로 진행하면 1일까지 버는 돈이 없으니 0원 2일까지 버는..
백준 9461https://www.acmicpc.net/problem/9461 9461번: 파도반 수열오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net풀이 전 나의 생각삼각형이 n번째에 어떤 삼각형이 더해져서 값이 나오는지 규칙을 먼저 찾아야 한다. 앞서 말하자면 뭔가 쭉 나열해놓고 규칙을 찾아서 풀었는데 다른 사람들과 점화식이 달랐다. N번째 삼각형이 만들어지기 위해선 N번째 삼각형의 변을 이루고 있는 두 삼각형 변의 길이를 더해줘야 한다고 생각했다. 그래서 되는데로 규칙을 적어봤다. 초반에 나오는 1, 1, 1은 초기값으로 생각하고 적어..
백준 12852 https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 풀이 전 나의 생각 어느 연산 과정을 통해 최솟값을 구해야 하는 문제들은 대부분 역추적을 이용하면 한층 더 쉽게 접근 할 수있다. 문제의 연산 조건을 보면 1. X가 3으로 나누어 떨어지면, 3으로 나눈다. 2. X가 2로 나누어 떨어지면, 2로 나눈다. 3. 1을 뺀다. 여기서 알 수 있는건 지정한 수의 연산과정 최대값 즉, 최악의 값은 계속 1을 빼주는 것이다. 그렇기 때문에 DP의 초기값을 모두 자신의 값으로 넣어준다. ex) dp[1] = 1, dp[2] = 2, dp[3] = ..
백준 2579 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 전 나의 생각 일정 조건에 의하여 계단을 올랐을 때 최대로 나올 수 있는 점수를 얻어야 하는 문제다. 조건 1. 한 번에 한 계단, 두 계단 씩 오를 수 있다. 2. 연속해서 3개의 계단을 밟을 수 없다. 3. 마지막 도착 계단은 반드시 밟아야 한다. 이 조건을 의식하면서 처음부터 DP(최대값)를 구해 나가면 생각보다 쉽게 점화식을 구할 수 있다. 문제의 예시인 (10, 20, 15, 25..
백준 11659 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 풀이 전 나의 생각 주어진 N의 범위를 보면 100000개 까지 주어질 수 있다. 이 조건의 의미는 2차원 배열과 2중 for문은 사용이 불가능하다는 것이다. 그럼 1차원 배열로 for문 하나만 써서 해결하면 쉽게 풀릴 수 있는 문제라고 힌트를 준 것이다. 문제의 풀이를 생각해보면 구간의 합을 구해야 한다. 그러면 각 상황마다의 구간 합을 모두 구해주고 이를..
백준 12865 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 전 나의 생각 DP를 풀 때 생각해야 하는 두 가지 1. for문을 이용한 DP는 이전 값에 접근해야 되기 때문에 초기값을 0으로 설정해줘야 한다. 2. 어느 분기에 도착했을 때 이전에 구해 놓은 최대 값을 탐색해야 한다. 배낭의 들어갈 수 있는 물건들과 최대로 넣을 수 있는 무게가 주어진다. 이 때 최대 무게..
백준 9251 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 전 나의 생각 이 문제는 최장 공통 부분 수열(LCS)을 구해야 한다. 언뜻보면 같은 문자열만 구하면 되는 것이 아닌가 생각할 수 있지만 수열이기 때문에 값을 뛰어 넘는 부분까지 생각해야 한다. 1. if (i == 0 || j == 0) for문을 이용한 DP특성 상 이전에 저장된 값에 접근해야 하기 때문에 문자열을 1부터 시작하도..
