![]()
문제 풀이 BFS 문제입니다. 어느 위치에서 움직일 수 있는 거리 k까지 field[][]에 count +1를 저장합니다. 추후에 이 값과 비교하여 더 작으면 skip(boolean visit[][]과 같은 동작) 하고, 아닐경우 값을 저장합니다. field[x2] [y2] 의 값을 출력합니다. 코드 import java.io.*; import java.util.*; class Main { static int dx[] = {0,0,-1,1}; static int dy[] = {-1,1,0,0}; static int k; static int n; static int m; static int chk=1; static char field[][]; static int field1[][]; static boole..
링크 https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 풀이 과정 2차원 배열을 BFS로 탐색하는 방식으로 풀었다. 2차원 배열이기 때문에 pair를 사용했고, food 변수에 해당 BFS 탐색에서의 음식물의 크기를 저장했다. 그리고 강의에서 배웠던 방식대로 dx[], dy[]를 이용해서 2차원 배열을 탐색했다. 이 외에는 딱히 기본적인 BFS와 크게 다른 점이 없어서 전체적인 틀 짜는 것 자체는 어렵지 ..
![]()
https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 문제 풀이 최솟값을 출력해야 하므로 BFS방식을 사용하되 이 문제에서는 힙큐(heapq)로 가중치가 작은 위치가 먼저 pop되도록 한다. 가장 위쪽의 표는 문제의 예시들 중 하나고, 아래의 표들은 순차적으로 가중치값을 구하는 과정이다. 첫번째 표는 (0,0)위치에서 시작하기 때문에 왼쪽 상단에 5를 먼저 넣어두고, 해당 칸과 밀접하게 붙어있는 칸들의 값에 5을 각각 더해서 두번째..
문제 링크 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 파이썬의 heapq 모듈을 사용해 우선순위 큐를 구현하였다. 처음에는 양의 정수와 음의 정수를 각각 다른 힙에 저장하여 풀었다. (코드1 참조) 다른 블로그를 보니 힙에 push할 때 (절댓값, 입력값) 쌍으로 저장하여 푼 풀이가 있어서 다시 풀어보았다. (코드2 참조) 코드1 import sys input = sys.stdin.readline from hea..
문제 https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 풀이 순서값과 풍선값의 pair를 담고있는 deque를 이용하여 풀었다. 풍선값이 양수일때에는 맨처음 풍선은 이미 사라지고 없으므로 for 조건문에서 -1을, 음수일때에는 조건문에 abs를 씌우는것을 유의하자. 코드 #include #include using namespace std; int n; int main() { cin >> n; deque a(n); for (int..
![]()
우리집 그린칙코뉴어는 맨날 나를 물었다. 문제 링크 Problem 예제 입력 1 3 i want to see you next week good luck i want next good luck week to see you 예제 출력 1 Possible 예제 입력 3 2 please be careful pen pineapple apple pen 예제 출력 3 Impossible 앵무새가 말한 단어들을 앞에서 부터 조합하여 최종 문장을 만들 수 있는가? 에 대한 문제 Before 이번 주차에 배웠던 큐, 덱, 스택, 우선순위 큐, 힙에대해서 꼭 알고 가면 좋을 듯 하다. 큐와 덱이 뭐예요?? 우선순위 큐와 힙, 이진트리는 뭘까요? Solution 앵무새가 말한 단어들을 queue나 List에 집어 넣음 n개의..
문제 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이 끝나는 시간이 빠른 순서대로 회의 시간을 정렬한 후 가능한 회의를 순서대로 선택을 하면 되는 그리디 문제이다. 그리디는 귀류법으로 가설을 증명하는데 실제 코딩테스트 환경에서는 그렇게 풀 수 없고 눈에 보이는 문제면 바로 풀어보고 긴가 민가하면 마지막에 푸는게 낫다고 한다. 코드 #include using namespace std; #define pii pair vector v; int n; bool cmp(pii a, pii b) { if (a.second != b.second) return a.sec..
BOJ 13975번 파일 합치기 3 Intro Min Heap을 구현하여 풀이하였습니다. Swift로 Heap을 직접 구현해본 것은 처음이라 틀린 부분이 있다면 조언 부탁드립니다. Heap 구현 시 해당 블로그를 많이 참고하였습니다. Solution 입력받은 리스트를 Min Heap 구조로 변경시킨다. 최솟값을 2번 pop하여 더한다. 더한 값을 Min Heap에 다시 push한다. Min Heap에 남은 요소의 개수가 1개가 될 때까지 2~3번 과정을 반복한다. 남은 요소가 1개면 3번에서 push한 값들의 합을 출력한다. Code Swift import Foundation let t = Int(readLine()!)! for _ in 0.. Int { var heap = heap var cost = ..
![]()
문제 풀이 간단하게 큐를 이용하여 풀었습니다. 1부터 N까지 큐에 입력한 뒤, 반복문을 실행합니다. 반복문은 2가지의 동작을 연속적으로 합니다. 첫 번째 동작은 큐의 숫자를 poll하여 삭제하는 것이고, 다음 동작은 poll한 숫자를 다시 큐에 add 하는 것 입니다. 이 과정에서 isEmpty() 가 true가 된다면 마지막의 값을 출력하고 종료합니다. 코드 import java.io.*; import java.util.*; class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWri..
![]()
https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제 풀이 첫째 줄에서는 n을 입력받고, 두번째 줄에서 네번째 줄까지는 arr이라는 배열을 생성하여 수열의 숫자를 입력해 저장하도록 한다. stack이라는 배열은 스택으로 사용하고 result라는 배열에는 +,-등의 값을 저장하도록 하며, idx 초기값은 0으로 설정한다. 반복문을 사용하여 숫자 i를 1부터 n까지 ..
https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 우선순위큐와 그리디 알고리즘을 적절히 섞어 써서 시간제한 내에 연산하는 것이 포인트였습니다. 각 보석의 무게와 가치를 튜플 배열로 입력 받습니다. 각 가방 용량의 최대치를 입력 받습니다 각 보석은 무게순으로, 각 가방은 용량 순으로 오름차순 정렬합니다. 각 가방의 용량을 순회하면서 가방에 담을 수 있는 보석들의 가치를 우선순위큐(maxh..
링크 https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 풀이 과정 큐를 이용하는 매우 간단한 문제였다. 1번을 제일 위에 놓고, N번까지 카드를 순서대로 놓은 뒤 1. 제일 위의 카드를 버린다 2. 1번을 수행한 이후의 카드들 중, 다시 제일 위의 카드를 제일 아래에 있는 카드 밑으로 옮긴다 위의 두 행동을 반복하는 문제로, 단순히 큐에 1부터 N까지 넣은 뒤 1번의 경우에는 pop()으로 제일 위의 카드를 버리고 2번의 경우에는 front()와..
