취업 준비 및 일상

https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 풀이 처음 보면 꽤 막막합니다. 케이스를 잘 나누어 각 경우마다 최적의 움직임을 수행하면 될까? 일단 케이스를 분류하는거조차 모르겠고, 각 상황별 최적의 움직임이 뭔지도 모르겠네요. 이 방법은 아닌 듯 합니다. 한 단계의 움직임을 분석해보니까, 0을 (가능한 방향의) 사방의 숫자랑 바꾸는 것이고, 이는 사방 탐색으로 구현할 수 있어 보입니다. 거기에다가 특정 상태에 가장 먼저 도착...? => BFS로 될 겁니다. 그러면, 상태 공간을 저장할 배열을 만들어야 할 겁니다. 가..

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/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/17090 17090번: 미로 탈출하기 크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문 www.acmicpc.net 풀이 각 위치에서 주어진 방향대로 이동해서 탈출할 수 있는지 구현해야 합니다. 다만, M=N=500(총 25만개의 칸)이고, 모든 칸의 경로가 하나로 연결되어 탈출하는 시나리오를 생각해봅시다. 이 경우, 각 칸에서 탈출할 수 있을 지 여부를 계산하는 횟수는 1, 2, 3, ... , 25만번인, O(M^2N^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의 위치로 이동하게 된다. 동생..

문제 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다. 입력 첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다. 출력 첫째 줄에 N번째 감소하는 수를 출력한다. 풀이 1. bfs 등의 탐색 처음에 큐에 0~9를 넣은 후, (숫자의 맨 앞자리 + 1)부터 9까지 붙인 수를 큐에 넣어서 bfs 진행 2. 비트마스킹 생각해보면 감소하는 수에서 0~9는 각각 최대 한 번만 나올 ..