본문 바로가기

분류 전체보기740

[백준 16928] 뱀과 사다리 게임 [Python] 풀이 뱀과 사다리 게임은 쉽게 출발지에서 주사위를 굴려 도착지까지 도달해야 하는 게임이다. 무조건 큰 숫자로 이동하는 '사다리'와 작은 숫자로 이동하는 '뱀' 이지만,'사다리-사다리' 보다 '뱀-사다리'가 더 빠를 수 있다는 점에 유의하자. 즉, 절대적으로 좋고(사다리) 안 좋은(뱀) 조건이 없다. 필자는 개인적으로 뱀을 좋아한다 (~쉬익~쉭) 그 때문에 이동 가능한 모든 칸에 대해서 탐색을 진행해야 한다. 다음 조건을 유의하자 주사위를 굴려 나온 수만큼 이동한 칸에 '사다리' 또는 '뱀'이 있을 때, 선택이 아닌 강제로 이동을 해야한다. '사다리'와 '뱀' 을 동시에 가지는 경우는 없다. 게임은 1회 이상 진행된다. 'N + M 2023. 4. 21.
[백준 10188] Quadrilateral [Python] 풀이 입력받은 길이와 너비에 맞는 직사각형을 'X'로 출력해주면 된다. 각 TC마다 한 줄 개행 해주어야 한다. 소스코드 소스코드 보기 출처 10188번: Quadrilateral A quadrilateral is a 4-sided figure. For this program, print out a 4 sided figure using the capital letter X. The largest side will be 20, and the smallest side will be 1. www.acmicpc.net 2023. 4. 20.
[백준 9019] DSLR [Python] 풀이 두 수 A, B가 주어질 때 문제에서 정의된 D, S, L, R 명령을 사용해서 A를 B로 만드는 과정에서 사용한 명령을 순서대로 출력해주면 된다. 시간 제한은 6초로 넉넉한 편이기 때문에 Bidirectional Search 방식을 사용하지 않고, 기본 BFS 방식으로도 해결할 수 있다. 우선, 동일한 숫자가 만들어져 중복된 탐색을 방지하기 위해, 해당 숫자를 만들지 않은 경우에만 만들어줘야한다. queue에 해당 숫자를 만들기 위한 명령어를 set으로 묶어 넣어줘도 되지만, visited 배열에 넣어주기로 했다. 단 위의 방식을 사용할 경우 boolean값이 아닌, 문자열이 탐색 기준이 되기 때문에, 초기값과는 분명히 다른 시작값을 넣어주어야 한다. (초기값 : '-', 시작값 : '') que.. 2023. 4. 19.
[백준 10828] 스택 [C] 풀이 스택이란 항아리 처럼 나중에 집어넣은 것이 먼저 나오는 제한적 접근 나열 구조이다. LIFO(Last In First Out) 형식이며, 기본 개념을 구현만하면 된다. 단, 한 줄에 하나씩 출력해야 한다는 것을 명심하자 pop 명령을 실행하기 전에 스택이 비었는지 확인하기 위해 empty 명령어만 함수로 구현했다. 실제 메모리에 대한 참조를 해제할 필요 없이, 변수 top을 사용해 값을 가르키는데 제한을 두었다. 소스코드 소스코드 보기 출처 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net.. 2023. 4. 18.
[백준 11403] 경로 찾기 [Python] 풀이 가중치가 없는 방향 그래프가 주어질 때, 모든 정점 간 연결이 가능한지 아닌지를 탐색 후 인접 행렬 형식으로 표현해주면 된다. Floyd Washall 을 사용해서 풀이했다. 가중치는 없지만, 결국 모든 탐색 가능한 정점에 대해 정점 간 연결이 존재하는 경우 또 다른 정점간의 간접적 연결이 되기 때문이다. 단, 단순히 정점간의 간접적 연결에 대한 유무 판단만 하면 되기에 아래의 조건만 충족한지 살펴보자 소스코드 소스코드 보기 출처 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 2023. 4. 18.
[백준 2798] 블랙잭 [C] 풀이 최대 100개의 카드 중에서 3장의 카드를 고를 수 있는 모든 경우의 수를 탐색해도 제한 시간 내 합을 출력할 수 있다. 3개의 카드를 골라야 하니 3중 loop을 사용해 탐색하자. loop의 조건이 순서대로 1씩 감소하는 이유는, 최악의 경우 중복된 카드를 뽑지 않고서는 N - 2 ~ N 번째 카드를 선택했을 때가 조건에 맞는 최댓값이 나오는 경우이기 때문이다. 소스코드 소스코드 보기 출처 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 2023. 4. 17.

티스토리툴바