여름의 서재

📕 문제 NxN 크기의 미로에서 출발지 목적지가 주어진다. 이때 최소 몇 개의 칸을 지나면 출발지에서 도착지에 다다를 수 있는지 알아내는 프로그램을 작성하시오. 경로가 있는 경우 출발에서 도착까지 가는데 지나야 하는 최소한의 칸 수를, 경로가 없는 경우 0을 출력한다. 다음은 5x5 미로의 예이다. 1은 벽, 0은 통로를 나타내며 미로 밖으로 벗어나서는 안된다. 13101 10101 10101 10101 10021 마지막 줄의 2에서 출발해서 0인 통로를 따라 이동하면 맨 윗줄의 3에 5개의 칸을 지나 도착할 수 있다. [입력] 첫 줄에 테스트 케이스 개수 T가 주어진다. 1

📕 문제 V개의 노드 개수와 방향성이 없는 E개의 간선 정보가 주어진다. 주어진 출발 노드에서 최소 몇 개의 간선을 지나면 도착 노드에 갈 수 있는지 알아내는 프로그램을 만드시오. 예를 들어 다음과 같은 그래프에서 1에서 6으로 가는 경우, 두 개의 간선을 지나면 되므로 2를 출력한다. 노드 번호는 1번부터 존재하며, 노드 중에는 간선으로 연결되지 않은 경우도 있을 수 있다. [입력] 첫 줄에 테스트 케이스 개수 T가 주어진다. 1

후위표기식,,, 처음 문제로 접했을 땐 대체 이게 뭐지 일단 이해는 안 가지만 하라는 대로 코드짜고 그냥 흐린눈으로 넘어가자!! 생각했는데 그 이후로 후위표기식 문제가 3개나 더 나왔다.. 어쩔수 없이 직면해야만 했던.. 우리가 사용하는 중위 표기식을 후위 표기식으로 바꾸는 과정을 간단하게 설명하자면 아래와 같다. #1. 식: 3+(4+5)*6+7 stack : [ ] 출력: 3 -> 숫자이기 때문에 바로 출력 #2. 식: 3+(4+5)*6+7 stack : [ + ] 출력: 3 -> 연산자 스택이 비어있기 때문에 스택에 + 추가 #3. 식: 3+(4+5)*6+7 stack : [ +, ( ] 출력: 3 -> ( 는 + 보다 우선순위가 높기 때문에 스택에 ( 추가 ( ' ( '는 우선순위가 제일 높기 때..

📕 문제 NxN 배열에 숫자가 들어있다. 한 줄에서 하나씩 N개의 숫자를 골라 합이 최소가 되도록 하려고 한다. 단, 세로로 같은 줄에서 두 개 이상의 숫자를 고를 수 없다. 조건에 맞게 숫자를 골랐을 때의 최소 합을 출력하는 프로그램을 만드시오. 예를 들어 다음과 같이 배열이 주어진다. 2 1 2 5 8 5 7 2 2 이경우 1, 5, 2를 고르면 합이 8로 최소가 된다. [입력] 첫 줄에 테스트 케이스 개수 T가 주어진다. 1≤T≤50 다음 줄부터 테스트 케이스의 첫 줄에 숫자 N이 주어지고, 이후 N개씩 N줄에 걸쳐 10보다 작은 자연수가 주어진다. 3≤N≤10 [출력] 각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 합계를 출력한다. 💡 풀이법 1. 현재 행을 의미하는 idx라는 변..

📕 문제 사다리 게임이 지겨워진 알고리즘 반 학생들이 새로운 게임을 만들었다. 가위바위보가 그려진 카드를 이용해 토너먼트로 한 명을 뽑는 것이다. 게임 룰은 다음과 같다. 1번부터 N번까지 N명의 학생이 N장의 카드를 나눠 갖는다. 전체를 두 개의 그룹으로 나누고, 그룹의 승자끼리 카드를 비교해서 이긴 사람이 최종 승자가 된다. 그룹의 승자는 그룹 내부를 다시 두 그룹으로 나눠 뽑는데, i번부터 j번까지 속한 그룹은 파이썬 연산으로 다음처럼 두개로 나눈다. 두 그룹이 각각 1명이 되면 양 쪽의 카드를 비교해 승자를 가리고, 다시 더 큰 그룹의 승자를 뽑는 방식이다. 다음은 4명이 카드를 비교하는 경우로, 숫자 1은 가위, 2는 바위, 3은 보를 나타낸다. 만약 같은 카드인 경우 편의상 번호가 작은 쪽을 ..

📕 문제 NxN 크기의 미로에서 출발지에서 목적지에 도착하는 경로가 존재하는지 확인하는 프로그램을 작성하시오. 도착할 수 있으면 1, 아니면 0을 출력한다. 주어진 미로 밖으로는 나갈 수 없다. 다음은 5x5 미로의 예이다. 13101 10101 10101 10101 10021 마지막 줄의 2에서 출발해서 0인 통로를 따라 이동하면 맨 윗줄의 3에 도착할 수 있는지 확인하면 된다. [입력] 첫 줄에 테스트 케이스 개수 T가 주어진다. 1

📕 문제 Forth라는 컴퓨터 언어는 스택 연산을 기반으로 하고 있어 후위 표기법을 사용한다. 예를 들어 3+4는 다음과 같이 표기한다. 3 4 + . Forth에서는 동작은 다음과 같다. 숫자는 스택에 넣는다. 연산자를 만나면 스택의 숫자 두 개를 꺼내 더하고 결과를 다시 스택에 넣는다. ‘.’은 스택에서 숫자를 꺼내 출력한다. Forth 코드의 연산 결과를 출력하는 프로그램을 만드시오. 만약 형식이 잘못되어 연산이 불가능한 경우 ‘error’를 출력한다. 다음은 Forth 연산의 예이다. 코드 출력 4 2 / . 2 4 3 - . 1 [입력] 첫 줄에 테스트 케이스 개수 T가 주어진다. 1≤T≤50 다음 줄부터 테스트 케이스의 별로 정수와 연산자가 256자 이내의 연산코드가 주어진다. 피연산자와 연산..

해야 할 V개의 작업이 있다. 이들 중에 어떤 작업은 특정 작업이 끝나야 시작할 수 있으며, 이를 선행 관계라 하자. 이런 작업의 선행 관계를 나타낸 그래프가 주어진다. 이 그래프에서 각 작업은 하나씩의 정점으로 표시되고 선행 관계는 방향성을 가진 간선으로 표현된다. 단, 이 그래프에서 사이클은 존재하지 않는다 (사이클은 한 정점에서 시작해서 같은 정점으로 돌아오는 경로를 말한다). 아래 그림은 이런 그래프의 한 예다. 이 그래프에서 작업 1은 작업 4가 끝나야 시작할 수 있다. 작업 6은 작업 5와 작업 7이 끝나야 할 수 있다. 이 그래프에서는 사이클이 없다. 김과장은 선행 관계가 주어진 작업군을 한 번에 하나의 작업씩 처리해서 다 끝내려 한다. 위에서 예를 든 작업군에 대해서 이런 일을 한다면 아래..