# depth first search
DFS와 백트래킹
그래프 탐색 알고리즘으로, 그래프의 노드들을 탐색하는 방법 중 하나다른 그래프 탐색 알고리즘으로는 대표적으로 BFS(Breadth-First Search, 너비 우선 탐색)가 있다.DFS는 시작 노드에서 한 방향으로 가능한 멀리까지 탐색한 후, 더 이상 진행할 수 없을
Number of Distinct Islands
친구의 프리미엄 계정을 빌려서 문제를 풀고 있다 재밌는 문제를 발견했다. Distinct Islands, 즉 독립적인 섬의 숫자를 출력하면 되는 문제다. 그냥 단순하게 DFS를 사용해서 섬을 출력하는게 아니고 독립적인 섬의 "모양"이 같다면 그 섬들은 하나의 섬으로 취
Shortest Bridge
요즘 한참 코딩 테스트 보다 더 업무와 연관 있는 데이터 엔지니어링 지식들을 공부하다보니 코딩 능력이 많이 약해진것만 같다. 그래서 리트코드에 추천으로 나온 문제를 풀어봤는데 생각보다 많이 헤맸어서 좀 자극을 받을 필요가 있다고 생각했다 ㅠㅠ. 이 문제는 최소한의 0을
Surrounded Regions
리트코드에서 재미난 문제를 풀었다. 마지막으로 풀었던 기록을 보니깐 2020년이었는데 입대하기 전에 풀고 지금 다시 풀어봤다. 분명히 이 문제를 풀때 힘든 기억이 있지만 어렴풋이 기억이 나서 풀려고 했는데 테스트 케이스가 너무 쉽게 풀려서 내가 왜 고생했지 라는 생각으
Number of Operations to Make Network Connected (JAVA)
예전에 군대를 전역하고 풀었던 문제를 다시 도전해봤다. 그렇게 어려운 문제는 아니고 그냥 모둔 connected 그래프를 탐색해주고 연결이 되지 않은 그래프의 숫자를 가지고 오는 문제다. 이 문제를 어렵지 않게 풀었음에도 이렇게 다시 올리는 이유는 자바로 풀이를 했을때
수식 최대화
카카오에서 정말로 흔하게 내는 완전탐색류의 문제다. 이미 블로그로 커버한줄 알았는데 안해서 놀랐다. 백준 문제를 풀다가 문득 생각이 나서 풀게됐는데 처음에 구상을 생각하면서 더하기 뺼샘 구현을 생각하느라 시간을 많이 썼던거 같다. 그래도 여전히 재미있고 좋아하는 문제로
[백준] 연구소
삼성 기출 문제중 하나이다. 3개의 벽을 꼭 설치해야 하고 모든 바이러스가 상하좌우로 퍼진다는 가정하에 가장 많은 안전지대를 만들면 된다. 결국 이 문제의 핵심은 어느 위치에 벽을 두냐에 로직이였고 아이디어만 떠올리면은 쉽게 풀 수 있는 문제다. 솔직히 이 문제를
[백준] 모양 만들기
백준 문제를 보던 중 그래도 재미있는 문제를 푼거같은 기분이 든다. 0으로 나온 숫자를 1로 바꿀경우 인접해있는 1의 최대 숫자를 출력하면 되는 문제인데 예전에 리트코드에서도 비슷한 문제를 봐서 똑같이 접근해봤다. 말 그대로 완전탐색 문제이기때문에 숫자를 한번 1로 바
동굴 탐험
프로그래머스는 원래 레벨 2 ~ 3 문제 밖에 안푸는데 왜인지 모르게 오늘은 레벨 4의 문제를 읽고 꽤 풀만하다고 생각해서 도전해봤다. 사실 문제를 어떻게 풀지 계속 고민하느라 시간을 꽤 많이 사용하긴 했고 머리 속에 구현방법은 떠올랐으나 구현을 옮길려니 도저히 실행이
[백준] 빵집
그리디 문제를 보고 있는데 탐색 문제가 나와서 좀 반가운 마음에 풀어보았다. 문제를 읽었는데 진짜 무슨 소리인지 감을 못잡겠어서 예시를 보고도 솔직히 어떻게 푸는지 몰랐다. 그런데 정답 코드가 적혀있는 블로그를 보면서 풀이에 대한 해석만 보고 문제는 나 혼자 풀어야겠다
Reorder Routes to Make All Paths Lead to the City Zero
분명히 쉬운 문제인데 푸는 방법을 잘못 선택해서 시간을 좀 날린 문제라고 생각한다. Directed 노드가 있을때 몇가지의 노드 노선을 변경시켜서 모든 노드가 0번째 노드로 향할 수 있게 만들면 되는 문제이다. 여기서 내가 Union Find 형식으로 답을 찾아내려고
백준 1325, 효율적인 해킹 - DFS / BFS
https://www.acmicpc.net/problem/1325"A가 B를 신뢰" 하는 경우, B를 해킹하면 A도 해킹 가능=> 신뢰 관계 (방향이 있는 간선)을 따라 그래프 탐색=> 인접 리스트 List<Integer>\[] lists에 간선 정보 저
Word Search
최근에 봤던 코딩 테스트에서 봤던 문제랑 가장 유사하다고 생각해서 생각난김에 다시 풀어보았다. 최근에 백준에서 연습을 할때도 대부분 시뮬레이션을 조합한 BFS 방식을 많이 쓰다보니깐 나도 모르게 그게 되게 편해지고 익숙해져서 그래프 문제를 봤을때 BFS 옵션부터 생각하
[백준] 테트로미노
오랜만에 다시 풀어보는 DFS + 시뮬레이션 형식의 문제이다. 솔직히 문제를 처음 읽었을때 너무나도 어려운 문제를 예상 했었다. 문제 내용은 해당 모양의 도형을 Matrix 에서 찾은 후에 그 도형안에 있는 숫자의 최대합을 구하는 문제였고, 도형은 회전, 그리고 대칭
[백준] 폴더 정리 (small)
흥미로운 문제를 발견하고자 하는 내 노력으로 또 한번 백준에서 추천 문제들을 대거 찾은 후에 하나씩 도장 깨기 처럼 풀고 있는 중이다. 요즘들어 부쩍 들었던 생각중 하나는 시뮬레이션과 구현쪽에서 더 완벽하게 해야겠다고 생각했어서 집중적으로 풀고 있는 중이다. 문제는 처
알고리즘
인접 행렬 구현 시, O(V^2)인접 리스트 구현 시, O(V + E)재귀함수 or 스택으로 구현가능한 최대 깊이까지 탐색하는 방식① 장점큐에 탐색할 노드들을 저장하는 BFS에 비해, 메모리 소비가 적음② 단점최적 해의 탐색을 보장하지 못함Worst Case의 경우,
[백준] 단지번호 붙히기
백준 기준 실버1에 해당하는 문제이다. 솔직히 좀 어려운 문제들을 위주로 많이 풀어봐서 그런지 이런 단순한 DFS 류 문제는 너무 쉽게 느껴졌다. 그래도 어쨌든 문제는 푼거기 때문에 기록은 간단하게 남기겠다. 1이 집을 나타내는 숫자를 의미할때 집들만 탐색해서 상하좌우
[백준] 뿌요뿌요
이 블로그를 작성하는 지금 내 심정은 너무 진이 빠진 느낌이다. 골드5 수준에 문제고 뿌요뿌요 게임을 모티브로 만들어진 코딩 테스트 문제이다. 시뮬레이션 타입에 문제인데 DFS 까지 포함된 단순하지만은 않는 문제이다. 게임의 룰은 간단하다, R, G, B, Y, P
[백준] 전쟁-전투
두번째로 풀어보는 백준문제이다. 일단 당분간은 리트코드 보다는 이렇게 Visual Studio 를 쓰는 IDE 를 사용하면서 푸는 백준 위주의 문제를 풀것이고 블로그를 업데이트 할것이다. 백준에서 나오는 추천 문제는 제목이 어그로가 상당하다고 생각하지만 이번 문제는 그
Longest Increasing Path in a Matrix
리트코드 추천으로 처음 접하게 된 문제이다. 난이도가 Hard 여서 상당히 걱정을 하고 문제를 읽게 됐는데 생각보다 할만해 보였고 Memoization 을 이용한 DP 방식으로 쉽게 풀수있을거라고 생각했다. Matrix가 주어졌을때 각 원소를 탐색하면서 원소가 커지는