# breadth first search
[백준] 아기 상어
삼성 S직군 기출문제를 풀어 보았다. 중간에 너무 뻘짓만 안했다면 정말 재밌었던 문제 였고 내가 시나리오 + 도형 문제에 꽤 강점을 보인다는 자신감 또한 느꼈던거 같다. 일단 시나리오 자체를 설명하기에는 너무 어지럽게 상황이 많았다. 그래도 제일 중요하게 생각해야 하는
[백준] 이모티콘
확실히 쉴 수 있는 날이여서 그런지 문제를 푸는데 더 집중을 했고 시간이 생각보다 많이 나서 문제를 더 풀어보았다. BFS 관련 문제지만 사실 이 문제는 DP로도 Memoization 방법을 통해서도 풀 수 있는 문제다. 내 전 포스트에서 정리했던 DP 관련 문제에 이
[백준] 아기 상어 2
다시 기초를 다지자는 마인드로 원래는 자신이 있어서 안해도 된다는 마인드를 가졌던 그래프 탐색 문제에 좀 더 도전을 하게 되었다. 제목은 다르지만 내용만 보면은 이 문제는 예전에 리트코드에서 풀었떤 Find number of Enclaves 같은 문제와 비슷하다는 생각
Minimum Path Cost in a Grid
요즘은 하도 백준 문제들만 풀어봤기에 오랜만에 리트코드로 넘어가서 괜찮은 문제가 없나 보던 와중에 재밌어 보이는 문제를 한번 풀어보았다. 솔직히 설명 자체는 정말 어질 어질 하기때문에 몇번씩 다시 읽어보고 예시 또한 몇번씩 봤어야지 이해를 했던 문제였다. 첫번째 예시에
[백준] 공주님을 구해라!
BFS 와 시뮬레이션 타입의 문제를 풀어보았다. 솔직히 체감상? 골드5 의 문제라고는 했는데 다 풀고나니 어렵게 느껴졌다. 문제가 요구하는 조건을 잘 인지 못하고 풀었으면 무조건 에러가 났을거같고 애초에 정답비율도 23프로에 머무르고 있는거보면 어려운 문제이긴 하다.
[백준] 파이프 옮기기 1
시뮬레이션에 꽤 강하고 BFS 같은 탐색류의 문제에 나는 강력하다고 믿고있다. 그러나 최근에 좀 나를 괴롭히는 유형의 문제를 자주 풀고있는데 예를들면은 모든 로직과 코드가 맞았지만 미세먼지때 문제처럼 회전을 어느 특정한곳에서 안시작해서 틀렸다든지 등. 정말로 많은 시간
알고리즘
인접 행렬 구현 시, O(V^2)인접 리스트 구현 시, O(V + E)재귀함수 or 스택으로 구현가능한 최대 깊이까지 탐색하는 방식① 장점큐에 탐색할 노드들을 저장하는 BFS에 비해, 메모리 소비가 적음② 단점최적 해의 탐색을 보장하지 못함Worst Case의 경우,
[백준] 미세먼지 안녕!
가끔 이런 생각이 들때가 있다. 너무나도 완벽한 아이디어와 또 너무나도 완벽한 코드를 다 짜고나면 굉장히 뿌듯하고 테스트 케이스가 통과했을때 이건 무조건 맞췄다 하고 제출 하는 순간. 내 기쁨을 비웃기라도 하듯 "틀렸습니다" 문구가 나온다. 그리고 코드를 다시 봐도 아
[백준] 인구 이동
좋은 문제 추천 리스트를 보던 와중에 괜찮아 보여서 골라봤는데 삼성 기출문제 중 하나라고 한다. 문제는 N \* N 으로 이루어진 벡터에서 해당 시나리오에 따라 인구이동이 가능한데 이 과정을 더 이상 안해도 될때까지 루프를 돌린 후에 시나리오가 끝나는 날을 출력하면 되
[백준] 미네랄
요즘 아침에 일찍 일어나서 문제를 푸는 삶은 시전하고 있는데 어떤 패기를 앞세워서 몸풀기로 이 문제를 골랐다. 알고보니 이 문제는 골드2 수준에 꽤 어려운 문제에 속해 있었고 솔직히 몸풀기로 시작했는데 그냥 몸학대 같았다. 문제 설명은 여느 백준 문제들이 그렇듯 좀 웃
[백준] 두 동전
오랜만에 올려보는 코딩테스트 문제이다. 지금까지 굉장히 많은 DFS/BFS 류의 문제를 풀어봤지만 이 문제는 솔직히 조금 고민 많이 했었고 내가 지금까지 풀었던 방식에 조금 변화를 주자라고 결심을 하기도 했다. Matrix 위에는 동전 두개가 놓여있다. 그리고 이동 방
Minimum Genetic Mutation
오늘은 BFS 관련된 문제를 풀어보기로 했다. 이 문제는 프로그래머스에 나와있는 문제와 굉장히 유사했으며 실제로 Word Ladder 이라는 리트코드 하드문제와 동일한 문제다. 사실 하드 레벨의 난이도라고 하기 조금 민망할정도로 어려운 문제는 아니다. start 와 e
Minimum Jumps to Reach Home
오늘은 개인적으로 꽤 재미난 문제를 풀었다. 굉장히 낮은 acceptance rate 때문에 겁을 먹었지만 일단 들어와서 천천히 풀어봤다. 문제는 x 지점까지 a라는 전진 점프와 b라는 후방 점프가 있을때 가정 적은 점프에 수로 x까지 도달하는 포인트를 리턴해야 하는
Shortest Path with Altering Colors
꽤 새로운 유형의 문제를 풀었다. 그래프나 Matrix에서 탐색하는게 아닌 n이라는 노드가 주어졌을때. 색이 다른 Edge 벡터에 각 노드가 배치되어있는데 Directed Graph 이고 각 노드가 이어질려면은 연결되있는 edge에 색이 달라야한다. 즉, 빨강 색 라인
Nearest Exit from Entrance in Maze
리트코드 그래프 문제 추천리스트에 있었던 미로에서 가장 가까운 탈출구로 도망가야 하는 문제다. BFS유형의 문제는 내가 볼때 두가지의 패턴으로 나뉜다. 하나는 일반적인 Queue 자료구조를 이용한 가능한 모든 경우의 수 찾기, 그리고 Priority_Queue 를 이용
Path With Minimum Effort
BFS 문제를 어떤것들 풀까 하고 보던중에 발견한 문제이다. 언뜻보기에는 간단한 문제지만, 난 어느부분에서 막혔었고 배운점들도 있었기에 적어본다. 문제 내용은 되게 간단하다. 사각형 밑에 가장자리에 도달하기까지 숫자들을 지나게 될텐데 이 경로상에 절대값중에 마지막 숫자
Coin Change
오랜만에 사회에서 풀어보는 문제이다. 확실히 코딩 문제 푸는 기간을 오래 쉬었던만큼 부족한 부분이 많이 느껴졌고. 어떤 문제를 올릴까 고민을 많이 했는데 이 문제가 되게 좋은 문제라는걸 느껴서 올리고싶었다. 예전에 한참 고민을 많이 했었던 2022 SK ICT Fami
리틀 프렌즈 사천성
오랜만에 풀어보는 BFS 문제이다. 사실 요즘 코딩알고리즘을 푸는데 있어서 심한 슬럼프가 온거같은 기분이다. 문제를 읽어도 읽은 기분이 안들고 구현하는데 있어서 조금이라도 어려움이 있게 되면 금방 포기하고 답부터 찾을려는 내 모습이 한심하게 느껴지고 그랬지만 앞으로 문
[Leetcode]994. Rotting Oranges
📄 Description You are given an `m x n` grid where each cell can have one of three values: - `0` representing an empty cell, - `1` representing a
백준 13549, 숨바꼭질 3 - 다익스트라 / BFS
https://www.acmicpc.net/problem/13549목표 지점을 찾으면 탐색을 종료하는, 일반적인 DFS, BFS는 간선의 가중치가 모두 같아야 함.하지만, 본 문제는 +1, -1 로 가는 경우 가중치가 1,x2 로 가는 경우 가중치가 0 으로