본문 바로가기

C++ 코딩 문제 풀이151

[Programmers] 등굣길 https://school.programmers.co.kr/learn/courses/30/lessons/42898 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 동적계획법(dynamic programming)을 활용해 문제를 해결하기 위해 시작점으로부터 $i$행 $j$열까지 도달하는 최단경로의 갯수를 저장할 배열 DP[$i$][$j$]을 사용하면, 오른쪽과 아래쪽으로만 이동 가능하므로 DP[$i$][$j$]에 도달하는 방법은 DP[$i$][$j - 1$]이 웅덩이가 아니면 왼쪽 칸에서 오른쪽 방향으로 이동하여 도달하는 경우가 존재한다.. 2023. 12. 19.
[Baekjoon] 2629번: 양팔저울 https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 문제 해결 과정 착안 추의 갯수가 $n$개일 때, 각각의 추를 사용하거나 사용하지 않고 무게를 만들 수 있는 경우의 수를 모두 계산하면 지수 시간($=O(2^n)$)의 시간 복잡도를 가지므로 동적계획법(dynamic programming)을 활용하여 문제를 해결하고자 하였다. 추가 하나씩 새로 주어질 때마다, 기존에 잴 수 있던 무게와 더불어 추가적으로 잴 수 있는 무게들은 다음과 같다. 새로 추가.. 2023. 12. 15.
[Programmers] 혼자 놀기의 달인 https://school.programmers.co.kr/learn/courses/30/lessons/131130 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 문제에서 주어지는 숫자 카드의 배열에 대해, 숫자 카드들을 게임 규칙에 따라 그룹으로 나누는 방법은 유일하다. 따라서 그룹에 포함되지 않은 카드가 없을 때까지 카드들을 게임 규칙에 따라 그룹으로 나누고, 숫자 카드가 많은 그룹부터 내림차순으로 정렬해 상위 2 개의 카드 그룹의 수를 곱한 값을 출력한다. 구현 각 숫자 카드 별로 그룹에 포함되었는지의 여부를 표시하는 변수를 별.. 2023. 12. 14.
[Baekjoon] 11967번: 불켜기 https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 그래프 탐색 알고리즘과 관련한 문제는 자신 있다고 생각했는데, 문제에서 요구하는 것 잘못 파악 + 문제에 들어있는 함정 때문에 처음 작성했던 코드가 왜 틀렸는지 이해하느라 엄청난 시간을 소모해버렸당 문제 해결 과정 착안 시작 지점으로부터 방을 방문할 때마다, 방에 존재하는 모든 스위치를 켜면서 불이 켜진 방의 갯수를 증가시킨다. 이후 인접한 방.. 2023. 12. 14.
[Programmers] N-Queen https://school.programmers.co.kr/learn/courses/30/lessons/12952 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 체스판 내에서의 퀸의 이동 법칙에 따라 한 줄마다 하나의 퀸만 놓을 수 있으므로, 가장 위쪽 줄부터 시작하여 아래쪽으로 한 줄씩 퀸을 순차적으로 배치하여 문제를 해결할 수 있다. 이때, 각 줄마다 퀸을 배치할 수 있는 칸이 있는지 확인하여 배치할 수 있는 경우에는 퀸을 배치, 그렇지 않은 경우에는 현재 줄에서 배치한 퀸을 다시 회수하고 이전 단계로 되돌아가는 백트래킹(back.. 2023. 12. 12.
[Baekjoon] 2580번: 스도쿠 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 빈 칸에 들어갈 숫자를 구하는 과정까지는 빠르게 구현했는데, 백트래킹 알고리즘 구현에서 빈 칸에 들어갈 숫자를 실시간으로 구해서 대입했어야 하는데 그 부분을 실수해서 디버깅에 한참을 소비하고 말았당 문제 해결 과정 착안 빈 칸으로 표시된 칸마다 재귀적으로 현재 칸에 넣을 수 있는 숫자를 넣고, 넣을 수 있는 숫자가 없는 경우에는 이전 단계로 돌아가 다른 숫자를 넣도록 하는 백트래킹 알고리즘을 통해.. 2023. 12. 11.

티스토리툴바