잡담연구소

www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net IDEA 아 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ 최근에 본 네이버부캠 코테에서 같은 유형의 문제가 나왔었는데,,,,,ㅜㅜ 못풀었다. 생소한 느낌이라서 DFS나 BFS로는 맨날 2차원좌표만 접하다보니까 2차가 아닐때의 BFS나 DFS가 생소했었나보다,,,,, 익숙해질겸 이후 비슷한 문제를 추천받아 백준 5014번 스타트링크 (www.acmicpc.net/problem/5014) 연습..

www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net IDEA 아래 두가지 조건을 만족시키는 자료구조의 기능을 구현해주면 된다. 배열에 정수 x (x ≠ 0)를 넣는다. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다. 우선순위 큐를 활용해 구현하였다. 우선순위 큐에 배열을 넣어준 후 , 정렬 기준을 따로 정의해두었다. 절댓..

www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net IDEA 문제에서 양방향 순환 큐라는 얘기를 한다 -> 양방향 큐 = 덱 이라고 생각하고 문제를 풀었다. 아래와 같은 3가지 조건을 수행한 후 2,3번을 수행하는데 얼마나 걸렸는지 구하는 문제다. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다. 👉 내가 맨 처음에 착각했던 문구다. 원소를 뽑아내는 행위는 맨 앞에서만 할 수..

www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net IDEA 50 * 50 짜리를 8 * 8로 쪼개 완전탐색을 진행해도 십만번이 조금 넘기때문에 주어진 시간 안에 돌아갈 수 있다고 판단했다. 체스판의 구성은 왼쪽 위가 W냐 , B냐에 따라서 달라진다. 그래서 나는 왼쪽 위가 W면 WHITE 배열 , B면 BLACK배열이라고 두었다. WHTE 배열 - 홀수번째 행 & 홀수번째 열 : W , 홀수번째 행 & 짝수번째 열 : B 짝수번째 행 & 홀수번째 열 :..

www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net IDEA 가장 긴 증가하는 부분 수열을 구하는 문제다. A전깃줄의 위치 , B전깃줄의 위치 순으로 입력을 받는데 , A전깃줄의 위치에 대해서 오름차순으로 정렬해보면 아래와 같은 그림이 나온다. 왼쪽 A전깃줄번호를 인덱스로 가지는 배열이 있고, 그 값이 B전깃줄번호라고 생각해보자. [8,2,9,1,4,6,7,10] 이 된다. 이 중 전깃줄이 교차하지 않기 위해서는 i < j 라면 arr[i] < arr[j] 여야한다. ..

www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net IDEA 숫자들 사이에 어떤 기호가 들어갈지 백트랙킹으로 구현하는 문제인 거 같다. 연산자를 해당 숫자 (0 ~3) 으로 cal이라는 배열에 저장 연산자가 1 0 2 1 식으로 주어진다. 인덱스 번호에 맞춰 cal 이라는 연산자 배열에 해당 횟수만큼 저장한다. 0 2 2 3 이렇게 cal에 들어간다. cal 인덱스로 순열을 구현한다. 숫자가 n개면 연산자는..