알고리즘 문제/백준 2023. 11. 9.
14938 서강그라운드 Java
14938 서강그라운드 Java 오늘은 내가 골드 2를 달성한 영광스러운 날이다. 이 영광을 룸메이트인 서강대 출신 ○** 양에게 돌린다. (희성이라 성을 밝힐 수 없음) 문제 🌐 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 하는 게임이다. 서강그라운드에서 1등을 하면 보상으로 치킨을 주는데, 예은이는 단 한번도 치킨을 먹을 수가 없었다. 자신이 치킨을 못 먹는 이유는 실력 때문이 아니라 아이템 운이 없어서라고 생각한 예은이는 낙하산에서 떨어질 때 각 지역에 아이템 들이 몇 개 있는지 알려주는 프로그램을 개발을 하였지만 어디로 낙하해야 자신의 수색 범위 내에서 가장 ..
알고리즘 문제/백준 2023. 10. 24.
21608 상어 초등학교 Java
21608 상어 초등학교 Java 문제 🌐 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호가 매겨져 있고, (r, c)는 r행 c열을 의미한다. 교실의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다. 선생님은 학생의 순서를 정했고, 각 학생이 좋아하는 학생 4명도 모두 조사했다. 이제 다음과 같은 규칙을 이용해 정해진 순서대로 학생의 자리를 정하려고 한다. 한 칸에는 학생 한 명의 자리만 있을 수 있고, |r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸이 (r1, c1)과 (r2, c2)를 인접하다고 한다. 비어..
알고리즘 문제/백준 2023. 10. 18.
17142 연구소 3 Java
17142 연구소 3 Java 문제 🌐 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽, 바이러스로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다. 예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴..
알고리즘 문제/백준 2023. 10. 17.
17141 연구소 2 Java
(17141) 연구소 2 Java 문제 🌐 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러스는 퍼지게 된다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 빈 칸은 바이러스를 놓을 수 있는 칸이다. 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 칸이다. 2 0 0 0 1 1 0 0 0 ..
알고리즘 문제/SWEA 2023. 10. 13.
1249 [D4] 보급로
(1249) [D4] 보급로 문제 🌐 2차 세계 대전에서 연합군과 독일군의 전투가 점점 치열해지고 있다. 전투가 진행 중인 지역은 대규모 폭격과 시가전 등으로 인해 도로 곳곳이 파손된 상태이다. 그림 1(a)에서와 같이 도로들은 전투로 인해 트럭이나 탱크와 같은 차량들이 지나갈 수 없다. 전투에서 승리하기 위해서는 기갑사단과 보급부대가 신속하게 이동하기 위한 도로가 있어야 한다. 공병대는 출발지(S)에서 도착지(G)까지 가기 위한 도로 복구 작업을 빠른 시간 내에 수행하려고 한다. 도로가 파여진 깊이에 비례해서 복구 시간은 증가한다. 출발지에서 도착지까지 가는 경로 중에 복구 시간이 가장 짧은 경로에 대한 총 복구 시간을 구하시오. 깊이가 1이라면 복구에 드는 시간이 1이라고 가정한다. 지도 정보는 그림..
알고리즘 문제/백준 2023. 10. 12.
17471 게리맨더링 Java
(17471) 게리맨더링 문제 🌐 백준시의 시장 최백준은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 최백준은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 백준시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다. 백준시는 N개의 구역으로 나누어져 있고, 구역은 1번부터 N번까지 번호가 매겨져 있다. 구역을 두 개의 선거구로 나눠야 하고, 각 구역은 두 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다. 중간에 통하는 인접한 구역은 0개 ..
자료구조 2023. 9. 8.
자료구조 Queue - 정의, 특성, 선형 큐
질풍노도였던 21세 시절을 지나고 22살 이후 나에게 큐란 이 남성밖에 없었다. 큐 (Queue) 큐 선형큐 큐의 활용 Queue 큐(Queue)의 특성 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조 큐의 뒤에서는 삽입만 하고, 큐의 앞에서는 삭제만 이루어지는 구조 선입선출구조 (FIFO: First In First Out) 큐에 삽입한 순서대로 원소가 저장되어, 가장 먼저 삽입 (First In) 된 원소는 가장 먼저 삭제 (First Out) 된다 큐의 구조 및 기본 연산 큐의 선입선출 구조 큐의 기본 연산 삽입: enQueue 삭제: deQueue 연산 기능 enQueue(item) 큐의 뒤쪽(rear 다음)에 원소를 삽입하는 연산 deQueue() 큐의 앞쪽(front)에서 원소를 삭제..
알고리즘 2023. 9. 7.
재귀 호출, Memoization
재귀 호출 재귀 호출이란? 再歸 자기 자신을 호출하여 순환 수행되는 것 함수 호출은 메모리 구조에서 스택을 사용한다. (이름만 같은 다른 메서드) 간단한 문제에 대해서는 반복문에 비해 메모리 및 속도에서 성능 저하가 발생한다 일반적으로 기본 부분 (Base case), 재귀 부분 (Recursive case)로 구성된다 Base case: 재귀 호출에서 빠져나가기 위한 조건 (탈출 조건) Recursive case: 자신을 호출하는 부분 (Base case로 유도하는 방향으로 작성한다) 재귀적 프로그램을 작성하는 것은 반복 구조에 비해 간결하고 이해하기 쉽다 하고자 하는 연산에서 여러 가지 분기가 있을 때 적용하기 좋다. 재귀 호출 작성 재귀 호출의 예) 팩토리얼 계산 함수에서 실행해야 하는 작업의 특성..
알고리즘 문제/백준 2023. 8. 28.
2116 주사위 쌓기 (Java)
(2116) 주사위 쌓기 🌍TISTORY 문제 🌐 천수는 여러 종류의 주사위를 가지고 쌓기 놀이를 하고 있다. 주사위의 모양은 모두 크기가 같은 정육면체이며 각 면에는 1부터 6까지의 숫자가 하나씩 적혀 있다. 그러나 보통 주사위처럼 마주보는 면에 적혀진 숫자의 합이 반드시 7이 되는 것은 아니다. 주사위 쌓기 놀이는 아래에서부터 1번 주사위, 2번 주사위, 3번 주사위, … 의 순서로 쌓는 것이다. 쌓을 때 다음과 같은 규칙을 지켜야 한다: 서로 붙어 있는 두 개의 주사위에서 아래에 있는 주사위의 윗면에 적혀있는 숫자는 위에 있는 주사위의 아랫면에 적혀있는 숫자와 같아야 한다. 다시 말해서, 1번 주사위 윗면의 숫자는 2번 주사위 아랫면의 숫자와 같고, 2번 주사위 윗면의 숫자는 3번 주사위 아랫면의 ..
알고리즘 문제/백준 2023. 8. 10.
1874 스택 수열 (Java)
(1874) 스택 수열 생성일: 2023년 8월 10일 오전 10:21 🌍TISTORY 문제 🌐 스택 (stack) 은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다. 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지킨다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 ..
