취업 준비 및 일상

https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 나의 접근 방법 숫자도 작고, 케이스도 얼마 안 많을 거 같아서 경우 나눠주면 될 거라고 생각했습니다. 그런데 경우 나누는게 꽤 빡세더라고요. 못 하겠어서 알고리즘 분류를 보고 풀었습니다. 풀이 A, B, C A ret[2][0] = Math.min(a+b, A); ret[2][1] = Math.max(b-(A-a), 0); ret[2][2] = c; // B -> C ret[..

https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 나의 접근 방법 N = 10000, M = 100000이므로 O(N^2)보다 작은 시간복잡도를 갖는 풀이가 있을 거라 생각했습니다. 시작점을 기준으로 특정 점까지 가는 거리를 구하는 문제이기에, 다익스트라에서 로직을 살짝 바꿔주면 될 거라고 생각했습니다. 한 번 틀렸는데, min을 써야할 곳에 max를 쓰는 실수를 고치니 정답을 얻었습니다..

백준 13459번: 구슬 탈출 백준 13460번: 구슬 탈출 2 백준 15644번: 구슬 탈출 3 백준 15653번: 구슬 탈출 4 3달 전 즈음에 구슬 탈출 2를 풀었습니다. 당시 구현에 급급하여 간신히 풀었고, 풀고 나서 '어휴 이런 문제는 꼴도 보기 싫다~' 하고 눈 앞에서 치워버린 기억이 납니다. 다시 풀어보니, 구현이 적당히 많고 까다로우며, 시간 커팅할 부분이 많은 흥미로운 문제라 느껴집니다. 풀이 '백준 13459번: 구슬 탈출'을 기준으로 설명합니다. 기본 구현 0) 기울일 때마다 움직이는 건 구슬 2개뿐이므로, 각 구슬의 좌표를 따로 저장하여 관리합시다. 그리고 구멍 좌표도 따로 저장해둡니다. 1) 방향과 빨간 구슬, 파란 구슬 위치에 따라 어느 구슬을 먼저 움직일 지 결정합니다. 2) ..

https://www.acmicpc.net/problem/18235 18235번: 지금 만나러 갑니다 첫 번째 줄에 세 정수 N, A, B가 주어진다. (2 ≤ N ≤ 500,000, 1 ≤ A, B ≤ N, A ≠ B) www.acmicpc.net 풀이 풀이를 쓸 생각이 없었는데, 1) 왠지 모르겠는데 난이도가 골드 3이나 되길래 인터넷에 검색해보니 2) 다들 이차원 dp로 풀이를 적길래 풀이를 작성합니다. 1. BFS 처음 Queue에 시작점, 도착점을 넣고, 각 단계마다 visited 배열을 초기화하여 한 단계 내에서 특정 지점을 두 번 방문하면 그 단계를 정답으로 출력하면 됩니다. 이진수의 특성 상 특정 점 s에서 x단계에 e로 가는 경우의 수는 (존재한다면) 유일하기에 가능한 풀이입니다. 2. ..

https://www.acmicpc.net/problem/2196 2196번: 이진수 XOR 길이 B(1 ≤ B ≤ 16)인 이진수들이 E(1 ≤ E ≤ 100)개 있다. 이 이진수들을 두 개씩 선택하여 XOR연산을 하여, 어떤 이진수를 만들려고 한다. 이 과정에서 만들어지는 이진수들을 이용하여 XOR연산을 www.acmicpc.net 문제 길이 B(1 ≤ B ≤ 16)인 이진수들이 E(1 ≤ E ≤ 100)개 있다. 이 이진수들을 두 개씩 선택하여 XOR연산을 하여, 어떤 이진수를 만들려고 한다. 이 과정에서 만들어지는 이진수들을 이용하여 XOR연산을 해도 되며, 같은 두 이진수를 XOR연산을 해도 된다. 만약 우리가 만들고자 하는 이진수를 만들 수 없다면, 이 이진수와 제일 가까운 이진수를 만들려고 ..

https://www.acmicpc.net/workbook/view/7313 문제집: 0x09강 - BFS (BaaaaaaaaaaarkingDog) www.acmicpc.net 문제 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다. 호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다. 아래에는 세 가지 예가 있다. ...XXXXXX..XX.XXX ....XXXX.......XX .....XX.......... ....XXXXXXXXX.XXX .....XXX..

https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 문제 농부 존은 최근에 N × N개의 방이 있는 거대한 헛간을 새로 지었다. 각 방은 (1, 1)부터 (N,N)까지 번호가 매겨져있다(2 ≤ N ≤ 100). 어둠을 무서워하는 암소 베시는 최대한 많은 방에 불을 밝히고 싶어한다. 베시는 유일하게 불이 켜져있는 방인 (1, 1)방에서 출발한다. 어떤 방에는 다른 방의 불을 끄고 켤 수 있는 스위..

https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 문제 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이는 상하좌우로만 이동할 수 있다. 상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄..

https://www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 동생..

https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 문제 스타트링크가 "스타트 택시"라는 이름의 택시 사업을 시작했다. 스타트 택시는 특이하게도 손님을 도착지로 데려다줄 때마다 연료가 충전되고, 연료가 바닥나면 그 날의 업무가 끝난다. 택시 기사 최백준은 오늘 M명의 승객을 태우는 것이 목표이다. 백준이 활동할 영역은 N×N 크기의 격자로 나타낼 수 있고, 각 칸은 비어 있거나 벽이 놓여 있다. 택시가 빈칸에..