본문 바로가기

Algorithm10

비트 마스킹으로 상태 관리하기 (백준 1194. 달이 차오른다, 가자) 조건을 꼼꼼히 보자 조건을! 조건을! 조건을 꼼꼼히 보자! 조건이 너무 너무 많고 처리를 못 하고 놓친다 조건을 확인하자!문제 분석미로에서 출발점 '0' 에서 출구 '1' 까지 최단 거리를 탐색한다. (bfs)열쇠 (a~f) 를 주워서 문 (A ~ F) 을 열 수 있다.같은 위치라도 열쇠 보유 상태가 다르면 다른 상태다. 단순 좌표(r, c) 방문 처리는 불가능하며 어떤 열쇠를 가졌는지에 따라 같은 좌표라도 다시 방문해야 할 수 있다.문제 풀이처음에는 keys 배열에서 열쇠 목록을 관리하면서 해당하는 문을 만난다면 배열에서 빼고 넣고를 반복하는 방법으로 풀고자 했다. 하지만 bfs 는 여러 경로를 동시에 탐색하기 때문에 경로 간에 열쇠 상태가 공유되어서 그렇게 풀 순 없다.배열로 관리할 경우, visit.. 2026. 3. 4.
2차원 배열에서 동시 이동 (코드트리 숫자가 가장 큰 인접한 곳으로 동시에 이동) https://www.codetree.ai/ko/external-connection/classes/177/lectures/1766/curated-cards/intro-move-to-max-adjacent-cell-simultaneously/description Codetree: Master Coding Interviews - Data Structures & AlgorithmsMaster algorithms, ace tech interviews, and elevate your coding skills with Codetree's systematic curriculum and expert-crafted problem sets.www.codetree.ai문제 분석M 개의 구슬이 서로 다른 위치에서 시작해서 1.. 2026. 3. 1.
바깥 껍데기 부터 완탐 하기 (백준 16926. 배열 돌리기 1) 문제 분석반시계 방향으로 돌아가는데, 빙글뱅글 달팽이가 아니라 맨 바깥 껍데기 돌아가고, 그 안쪽 껍데기가 돌아간다. 고민한 것코너에서 값 밀기를 어떻게 구현할 것인지껍데기를 어떤 기준으로 나누어 완전 탐색할 것인지코너에서 값을 미는 것의 경우 r 값이 달라지기 때문에 코너 마다 어떤 식으로 다음 좌표를 설정해주어야 할까?껍데기는... 진짜 어떻게 나누지... 맨 바깥 한바퀴 돌고, 열이나 행을 하나 줄여서 안으로 들어가기를 반복하기?풀이for 문을 사용하여 상하좌우 변을 처리해줄 수 있었지만, 조건에 인덱스를 설정해주는 과정 실수할 가능성이 커서(복잡해서) 델타 탐색 방식을 사용했다. 방향 값만 dir 에 저장하여 꺾어줄 수 있었다. 하지만 "상단만 시계 방향으로 움직이기" 등의 독립 조건이 붙는다면 .. 2026. 2. 27.
중위 순회로 트리 복원하기 (코드트리 2 + 1) 각 순회가 작동하는 과정전위 순회 (preOrder): parent -> left -> right중위 순회 (inOrder): left -> parent -> right후위 순회 (postOrder): left -> right -> parent중위 순회가 꼭 필요한 이유먼저 중위 순회는 어떤 순회와 조합되더라도 꼭 있어야 한다. 왜냐하면 트리의 복원에서 가장 중요하게 여겨지는 것은 "어디까지가 왼쪽 자식이고, 어디서부터가 오른쪽 자식인가" 이기 때문이다. 그래서 중위 순회에서 parent 를 찾아서 해당 원소를 기준으로 왼쪽 오른쪽 서브 트리를 나눈다. (경계선이 되어줌)후위 순회 혹은 전위 순회가 꼭 필요한 이유위 과정을 확인하면, 전위 순회와 후위 순회의 첫 번째 원소 혹은 마지막 원소는 root 원.. 2026. 2. 24.
행과 열도 구분 못 하는데 내가 코테를 어떻게 풀어 쿨하게 못 하는 걸 인정 b... 사실 너무 쪽팔려영 하지만 공부를 안 했으니까 어렵겠지이제는 그냥 싸피 코테 하나라도 풀은 게 너무 다행이라는 생각만 든다...https://www.codetree.ai/ko/trails/complete/curated-cards/intro-snail-number-square/description 빙빙 돌며 숫자 사각형 채우기 설명 | 코드트리빙빙 돌며 숫자 사각형 채우기을 통해 문제 요구사항과 입력·출력 예시를 꼼꼼히 확인해 정확한 풀이 전략을 세워보세요.www.codetree.ai바보 같아도, dx dy 델타 탐색 부터 다시 하고 있음 왜냐하면 나는... dfs bfs 가 뭔지도 제대로 모르는 전공자였기 때문에ㄴ 안 알려줬잖아 나암튼 이 문제는 맨날 하던 dx dy 상.. 2026. 2. 24.
BFS + Backtracking 으로 연구소 풀기 (백준 14502. 연구소) 문제 분석0 빈 칸1 벽2 바이러스바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다.새로 세울 수 있는 벽의 개수는 3개이며 꼭 3개를 세워야 한다.바이러스의 확산을 막기 위해 가장 효과적으로 벽을 세워야 한다.벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 풀이backtracking 으로 벽 3개를 세우는 조합을 구한다.벽 3개를 세웠을 때, BFS 로 바이러스를 최대한 퍼뜨린다.그 상황에서 안전 영역을 세고, backtracking 함수 에서 min 값을 구한다.Backtracking 함수 구현역할: 벽을 3개 세우는 조합을 구한다.depth 는 지금까지 구한 벽의 개수!!static void backtracking(int depth) { if (depth.. 2026. 2. 17.
DFS 랑 BFS 언제, 어디서, 어떻게 쓰는 거임? (알고리즘 유형 정리) 이번 코테 벼락치기하면서 느낀 거. dfs bfs 는 그래프에서만 쓰이는 게 아니다~ㄴ 진짜 몰 랐 어 DFS 는 탐색 (검색) 문제에서 "한 경로 끝까지 들어갔다가 다시 돌아오는 방식" 이다.즉, 모든 경우의 수/경로를 전부 확인해야 할 때 자주 쓴다.깊게, 끝까지 탐색하는 것이다. (재귀/스택) 반면에 BFS 는 "가까운 것부터 차례차례 넓혀 나가는" 탐색이다.넓게, 가까운 곳에서부터 탐색하는 것이다. (큐)최단거리 문제에 자주 사용된다. DFS경로 전체 탐색, 경우의 수 세기, 연결 요소 찾기, 순열/조합그래프/트리 탐색DFS 는 한 갈래 끝까지 갔다가 못 가면 돌아오는 (backtracking) 방식이라, 트리/그래프 구조에 잘 맞음경로 찾기/모든 경우 탐색미로 탐색, 백트래킹 문제(N-Queen.. 2025. 9. 27.
그리디가 뭔데? 투 포인터는 또 뭔데? 프로그래머스 구명보트로 알아보기 먼저 문제를 보면구명보트에는 한 번에 두 명까지만 탈 수 있고무게 합이 limit 을 넘으면 안 된다.이때 필요한 최소 보트 수를 구하라그리디란, 매 순간 가장 최적의 선택을 해나가는 알고리즘이다. 이건 나도 알고 있다. 전체 최적해가 아니라 매 순간 "좋아 보이는 선택" 을 하는 것이다. 이 문제에서의 그리디 전략은 다음과 같다.제일 무거운 사람은 반드시 태운다.이 사람과 가장 가벼운 사람을 짝지을 수 있으면 최선이다.보트 수를 최소화하려면 무거운 사람은 최대한 가벼운 사람과 함께 타야 보트의 낭비가 없기 때문이다. 가장 무거운 사람과 가장 가벼운 사람을 알려면 어떻게 할까? 배열을 정렬하고, 양 끝에 포인터 두 개를 둔다. 이후 조건에 따라 이동시키며 문제를 해결한다. 정렬된 people 배열:[i].. 2025. 4. 1.
나를 울게 만든 BFS... 그리고 백준 토마토 접근도 못 하겠는 사람 모여 네이버 코테 전날 알고리즘을 1 도 모르면서 벼락치기 라도 해보겠다고 BFS 문제를 허겁지겁 풀다가 토마토에서 막혀버렸다... 밤은 늦었고 내일 코테는 어차피 글렀고... 어차피 경험 삼으려고 신청한 거고... 하며 답답한 마음으로 집에 가는데 서러워져서 울었다 ㄹㅇ임그니까 BFS 란 그래프나 트리에서 가까운 노드부터 탐색해 나가는 알고리즘이다. BFS 는 같은 레벨 (거리) 에 있는 노드를 먼저 다 본 다음, 그 다음 레벨로 넘어간다. BFS 알고리즘을 작성할 때의 특징큐(Queue) 자료구조 사용최단 거리 문제에 자주 쓰임방문한 노드를 다시 방문하지 않도록 visited 배열을 사용동작 방식시작 노드를 큐에 넣고 방문 표시큐에서 노드를 꺼냄해당 노드와 연결된 (방문하지 않은) 노드들을 큐에 추가하고 .. 2025. 3. 26.

티스토리툴바