코드를 느껴바라

문제 링크성공 여부(걸린 시간): 성공 (31분)아이디어우선 처음 든 생각은 DFS로 한 방향으로 숫자를 늘리면서 배열에 넣어주고막히거나 이미 방문한 곳이라면 우 -> 하 -> 좌 -> 상 -> 우로 방향전환을 해주려고 생각했다.만약 현재 방향대로 갈 수 있다면 같은 방향으로 이동시켜주고만약 현재 방향대로 갈 수 없다면 다른 조건은 동일하게 유효성검사를 해주고방향은 (dir+1)%4로 방향으로 변경한다. 정답 코드package codingTest;import java.io.*;import java.util.*;public class Main { static int N; static int [][] map; static boolean [] checked; public static vo..

문제링크성공 여부(걸린 시간): 성공(1시간 20분 21초)아이디어두 수레(빨간/파란)를 동시에 이동시키며 각각 도착지에 도달하는 데 필요한 최소 이동 횟수를 구해야 한다.두 수레는 다음 조건들을 만족하며 이동해야 한다.서로 같은 칸을 동시에 점유할 수 없음 서로 자리를 교차해 지나갈 수 없음 도착지에 도착한 수레는 더 움직이지 않음 각 수레는 이미 자신이 이동했던 칸을 다시 방문할 수 없음 벽(5)은 이동 불가BFS 사용 상태는{R_x, R_y, B_x, B_y, 이동 횟수} 각 상태에서 양쪽 수레가 독립적으로 상하좌우 움직임→ 최대 16가지 경우 탐색방문 체크는 boolean[N][M][2] 형태로각 수레가 방문한 칸을 저장 단, 두 수레의 동시 이동 + 교차 불가 등 제약 때문에visi..

문제 링크성공 여부(걸린 시간): 성공(45분 30초)아이디어좋습니다.요구하신 대로 아이디어(설계부터 코드 설명까지) 부분만 마크다운 형식으로 정리했습니다.이 내용을 그대로 티스토리에 ## 아이디어 아래 붙여 넣으시면 됩니다.아이디어문제는 두 개의 물통 A, B가 주어졌을 때, 각각 최대 용량이 a, b일 때 목표 상태 (c, d)를 만드는 최소 횟수를 구하는 것이다.이를 위해 BFS(너비 우선 탐색) 을 이용해 가능한 모든 상태를 탐색하며 방문처리는 10만 * 10만 배열을 만들기엔메모리 낭비가 너무 심하기에 HashMap으로 a의 물의 양+" "+b의 물의 양의 문자열 key로 카운트를 value로 저장하여방문처리 해준다모든 가능한 물의 조합을 그래프 노드로 보고,한 번의 조작을 간선으로 보는 방식으..

문제 링크성공 여부(걸린 시간): 성공(14분 30초)아이디어일단 그래프 탐색을 통해서 수빈이가 동생을 최단 시간 안에 찾을 수 있도록 하려 했다.그때 고민한 것은 DFS냐 BFS냐 였는데DFS로 했을때는 시간이 depth이고 DFS를 수행했을때일단 해당 시간대에 다른 성공 할 수 있는 경우는 뒷전이고주구장창 막히거나 도착할때까지 쓸데없는 연산을 반복하게 됨으로 해당 문제에서 너비(time)를 우선적으로 탐색하여 앞선 시간에서 도착하면 끝낼 수 있는 효율적인 BFS로 작성을 해보았다.수빈이가 이동하는 경우는3가지이다.x->2x로 순간이동, 시간 추가 Xx->x+1로 이동, 시간 +1x->x-1로 이동, 시간 -1이때 주의할 것은1번의 경우에는 시간이 추가되지 않음으로2,3번 처럼 큐의 add를 통해 뒤쪽..

문제 링크성공 여부(걸린 시간): 성공(31분 41초)아이디어일단 큰 포인트는 두 가지이다.블루레이 길이를 이분탐색으로 찾는다.해당 길이의 블루레이가 M개 있다면 모든 강의를 "순서대로" 저장이 가능한가?일단 첫 번째 // 이분 탐색으로 블루레이 수 찾기 int left = 1; int right = sum; int mid=0; while (left - 만약 findLen에서 true가 return 되었다면 가능한 길이라는 것이다.그렇다면 최대한 짧은 블루레이의 크기를 가져야함으로 가능할때까지 작은 수로 검증해본다. - 만약 false다?그럼 해당 블루레이 길이로는 부족하다는 의미이므로 수를 키워서 다시 찾는다. 그리고 해당 길이의 블루레이가..

문제 링크성공 여부(걸린 시간): 성공(1시간 9분)아이디어사실 단순 그리디로도 풀 수 있는 문제이지만 처음에 그렇게 짰다가 틀리고 나서 이분탐색을 이용해서 풀어주었다.깔끔한 코드랑은 거리가 있으나 이렇게도 풀구나~ 또는 나도 이분탐색으로 풀었다는 사람들을 위해 올린다. 내 아이디어는 이러하다. 크레인과 박스를 각각 오름차순 정렬한다. 박스는 무거운 것부터 처리하기 위해 뒤에서부터 탐색한다. 매 라운드마다 모든 크레인은 동시에 움직일 수 있고, 한 번에 한 개의 박스만 옮길 수 있으므로 각 라운드를 시뮬레이션한다. 각 라운드에서는 아직 옮기지 않은 박스들을 무거운 순서로 살피면서, 현재 박스를 옮길 수 있는 크레인을 이분 탐색으로 찾는다. 조건은 크레인의 무게 제한이 박스 무게 이상이어야 하고, 이번 라..

문제링크성공 여부(걸린 시간): 성공(43분)아이디어이 문제는 길이가 N인 수에서 K개의 숫자를 제거해 가장 큰 수를 만드는 문제이다. 핵심은 앞에서부터 가능한 한 큰 숫자를 남기기 위해 작은 숫자를 우선적으로 제거하는 것이다.먼저 입력받은 숫자를 큐에 차례대로 저장한다. 결과를 담을 자료구조로는 스택처럼 동작할 수 있는 Deque를 사용한다.숫자를 앞에서부터 하나씩 확인하면서, 현재 숫자가 다음 숫자보다 크거나 같다면 결과에 넣는다. 하지만 현재 숫자가 다음 숫자보다 작다면 뒤에 더 큰 숫자가 있다는 의미이므로 현재 숫자를 제거하고 K를 하나 줄인다. 이 과정을 K가 0이 되거나 큐가 빌 때까지 반복한다.그 후 큐에 남은 숫자들을 결과에 넣어주고, 만약 아직 K를 다 쓰지 못했다면 이는 이미 앞부분이 ..

문제 링크성공 여부(걸린 시간): 성공 (59분 40초)아이디어이 문제는 트리 구조 위에서 양과 늑대의 개체 수를 누적하면서 최상위 노드(1번)까지 올려보는 방식으로 해결할 수 있다.내가 정말 어려워 하던 return 이 있는 DFS였는데 사실 재귀를 차분히 생각해서 코드를 짜면 크게 어렵지 않았다.입력으로 주어진 관계는 부모–자식 형태이므로, 자연스럽게 루트(1번 노드)를 기준으로 한 트리 구조를 형성한다. 각 노드에는 양 또는 늑대가 주어지고, 양은 양수, 늑대는 음수 값으로 처리한다. 리프 노드(더 이상 자식이 없는 노드)에서는 단순히 max(양의 수, 0)을 반환한다. (늑대가 더 많으면 결국 양은 모두 잡아먹히기 때문) DFS를 통해 자식 노드부터 계산한 값을 부모 노드로 누적시킨다. 자..

문제 링크성공 여부(걸린 시간): 실패(15분)아이디어 처음에는 DP로 접근해서 점화식을 세워보았는데, 예제 입력에 대해서는 정답이 나오지만 조금만 변형된 반례가 나오면 깨지는 허술한 풀이였다.즉, 이 문제는 단순히 경우의 수를 세는 DP 문제가 아니라, 실제로 파이프를 설치할 수 있는 경로의 최대 개수를 찾는 탐색 문제라는 점을 깨달았다.그래서 다른 방법을 고민하다가 힌트를 참고했는데, 정답 풀이 방식은 바로 DFS(깊이 우선 탐색) 이었다.핵심 아이디어탐색 순서: 현재 위치에서 오른쪽으로 이동할 때,우상향(대각선 위 오른쪽)우측(바로 오른쪽)우하향(대각선 아래 오른쪽)순서대로 탐색한다.이렇게 하는 이유는, 위쪽 경로가 먼저 확보되면 아래쪽 경로에 영향을 덜 주고 더 많은 파이프라인을 설치할 수 있기 ..

문제 링크걸린 시간(성공 여부): 1시간 (실패)아이디어처음에 뒤집혀있는 삼각형 기준으로 dp를 사용해야 겠다는 생각은 했으나그다음부턴 점화식을 못짜겠어서 포기했었는데 풀이를 보고 푸니 새삼 너무 겁먹은 듯 하다.핵심은 열 i까지 덮었을 때 오른쪽 끝이 마름모로 튀어나와서 다음 열로 이어져야 하는 상태(dp1) 인지,아니면 딱 닫혀 있는 상태(dp2) 인지를 나눠서 생각하는 것.dp1[i]: 열 i까지 덮었을 때 오른쪽 끝이 마름모로 튀어나와 있는 경우dp2[i]: 열 i까지 덮었을 때 깔끔하게 닫혀 있는 경우그리고 i열 꼭대기에 삼각형이 붙어 있는지(tops[i-1]) 여부에 따라 경우의 수가 달라짐.점화식은 다음과 같이 됨:dp1[i] = dp1[i-1] + dp2[i-1](이전이 어떤 상태든 i열에..