주뇽's 저장소

웅덩이가 있는 길을 피해, 마을에서 학교까지 갈 수 있는 모든 다른 길을 찾는 문제를 해결해 보자. 이 글에서는 마을에서 학교까지 도달할 수 있는 가능한 경로의 개수를 구하는 방법과 함께, 동적 프로그래밍(DP)을 활용한 경로 추적 알고리즘을 단계별로 설명한다.문제점: 웅덩이가 있는 경우 갈 수 있는 길이 제한된다 😓마을에서 출발하여 학교까지 가려면 특정한 경로를 따라야 하며, 이 경로에 웅덩이가 있으면 그곳을 지날 수 없다. 따라서 웅덩이를 피해 가능한 모든 경로의 개수를 구해야 한다. 단순히 오른쪽이나 아래쪽으로만 이동할 수 있는 경우, 웅덩이를 피하면서 학교까지 도달하는 모든 가능한 경로를 찾으려면 어떻게 해야 할까?해결책: 동적 프로그래밍을 사용한 경로 계산 🛠️지도 그리기 먼저, 마을에서 학..

https://softeer.ai/app/assessment/index.html?xid=41187&xsrfToken=GqOGAPTHxdW4H9tiPzQNWSohI14FqXlw&testType=practice Candidate | Softeer Assessment UI softeer.ai 루팡은 배낭을 하나 메고 은행금고에 들어왔다. 금고 안에는 값비싼 금, 은, 백금 등의 귀금속 덩어리가 잔뜩 들어있다. 배낭은 W ㎏까지 담을 수 있다. 각 금속의 무게와 무게당 가격이 주어졌을 때 배낭을 채울 수 있는 가장 값비싼 가격은 얼마인가? 루팡은 전동톱을 가지고 있으며 귀금속은 톱으로 자르면 잘려진 부분의 무게만큼 가치를 가진다. 제약조건 1 ≤ N ≤ 106인 정수 1 ≤ W ≤ 104인 정수 1 ≤ Mi, ..

https://school.programmers.co.kr/learn/courses/30/lessons/159993#qna 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는..

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 문제 로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 방은 $N \times M$ 크기의 직사각형으로 나타낼 수 있으며, $1 \times 1$ 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 ..

정육면체 한번 더 굴리기 문제는 골드 3정도의 수준인 문제이다. 간단하게 문제에 대해 설명하면 N*N 보드판이 존재하며 각각의 보드판에는 점수가 부여되어 있다. 이제 주사위를 굴리면서 주사위가 위치한 보드판에 있는 점수들을 특정 방법을 통해 합산하고 다음 주사위의 방향을 결정하고 방향에 맞게 다시 주사위를 굴리는 방식으로 m번만큼 반복된 이후에 총 점수를 계싼하는 쉽지 않은 문제이다. 일단 N값이 20정도로 그렇게 높지 않다. 따라서 완전탐색 방법을 이용해서 구현하여도 시간초과가 나지 않는다. 대부분 구현문제는 정말 어려운 문제가 아니라면 완탐을 이용해도 괜찮은 것 같다. 일단 문제에서 주어진 조건들에 대해서 잠깐 정리를 하자면 다음과 같다. 주사위는 처음 -> 으로 이동한다. 주사위가 위치한 보드판위에..

https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 문제 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부터 2N까지의 번호가 매겨져 있다. 벨트가 한 칸 회전하면 1번부터 2N-1번까지의 칸은 다음 번호의 칸이 있는 위치로 이동하고, 2N번 칸은 1번 칸의 위치로 이동한다. i번..

https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 문제 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다. 이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반..

https://www.acmicpc.net/problem/20436 20436번: ZOAC 3 첫 번째 줄에는 두 알파벳 소문자 sL, sR이 주어진다. sL, sR은 각각 왼손 검지손가락, 오른손 검지손가락의 처음 위치이다. 그 다음 줄에는 알파벳 소문자로 구성된 문자열이 주어진다. 문자열의 www.acmicpc.net 문제 2020년 12월, 세 번째로 개최된 ZOAC의 오프닝을 맡은 성우는 누구보다 빠르게 ZOAC를 알리려 한다. 하지만 안타깝게도 성우는 독수리타법이다! 독수리 타법이란 양 손의 검지손가락만을 이용해 타자를 치는 타법이다. 성우는 한글 자음 쪽 자판은 왼손 검지손가락으로 입력하고, 한글 모음 쪽 자판은 오른손 검지손가락으로 입력한다. a의 좌표가 (x1, y1)이고, b의 좌표가 (..