알고리즘 공부/ps12 [백준] falling apples - 13732번 문제 https://www.acmicpc.net/problem/13732 13732번: Falling Apples The input begins with a line containing integers R and C, designating the number of rows and columns of the grid, such that 1 ≤ R ≤ 50 000 and 1 ≤ C ≤ 10. The first line is followed by R additional lines, each designating a row of the grid, from to www.acmicpc.net 풀이 방법 문제가 영어로 만들어져 있어 당황스러울 수 있지만, 요구하는 바가 간단하다. 'a' 가 apple, '#'이 벽으.. 2024. 1. 9. [프로그래머스] PCCP 기출문제 4번, 수레 움직이기 문제 https://school.programmers.co.kr/learn/courses/30/lessons/250134 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 제가 복잡해하는 유형입니다. 동시에 여러개의 타겟이 움직일 수 있는 형태요 ㅎ 문제에서 '최소 혹은 최대의 경우를 구해봐라' 라고 나온다면, 보통 백트래킹으로 모든 경우를 체크해가며 최소인 경우를 찾으려 하는 것 같습니다. 추가로 구하려는 값이 최소라면, 현재 구해진 답보다 큰 값이 나오고 아직 구해야 할 연산들이 남아 있다면 더 체크를 해주지 않아도 되는 것이 백트래킹의 기본 아이디어이기.. 2023. 12. 24. [백준] 선수과목 - 14567번 문제 https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 내가 하는 이해 예제 입력 1을 생각해보면, 3번과목을 듣기 위해서는 2번과목을 선수해야하고 또 그 2번과목을 듣기 위해서는 1번과목을 선수해야 한다. 즉 1 -> 2 -> 3 순으로 이수해야 한다. 동일하게 예제 입력 2를 생각해보면, 1 -> 2 -> 5 1 -> 3 4 -> 5 위와 같이 1 -> 2 -> 5, 4 -> 5 처럼 5번 과목의 입장에서 생각할 때, 독립적인 깊이를 가진 여러 선수과목 코스가 생길 수.. 2023. 12. 6. [백준] 부분수열의 합 - 1182번 문제 https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 백트래킹으로 접근 가능한 문제이다. 내가 백트래킹으로 풀려고 하는 문제의 특징은 1. 가능한 케이스들을 체크해주는 완전탐색의 성격 2. 특정 조건에서 더이상 체크해줄 필요가 없는 특징이 있다. 답이 되는 리스트들은 그 원소의 수가 다르거나, 같더라도 다른 원소를 포함하고 있을 것이기에, 현재의 index값을 가지고 포함시킬지, 포함시키지 않을 것인지를 체크.. 2023. 12. 3. 이전 1 2 3 다음
