Leo.K | To become a cooler Developer

알고리즘 챌린지 11일차이다. 아무리 생각해봐도 주말엔 쉬는게 좋아서 쉬기로 했다. ㅋㅋ 귀찮아서 그런게 아니고,, 좀 더 오랜 기간 동안 챌린지를 이어나가기 위함이다. 오늘도 프로그래머스 Level2에 분류된 BFS문제를 가져왔다. https://school.programmers.co.kr/learn/courses/30/lessons/169199?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 기존의 BFS 로직을 사용해 문제를 풀면 쉽게 풀이할 수 있지만 문제에서 주어진 조건에 따라 조금의 추가 수정을 거치면 되는 쉬운 문제이다..

오랜만에 다시 알고리즘 풀이를 시작하려 한다. 최근 가까운 지인을 통해 알고리즘 말고 다른 간단한 챌린지를 시작했는데, 챌린지 형식으로 진행하다 보니 열심히 빠짐없이 한 달 동안 완수할 수 있었던 것 같다. 혼자 하다 보니 금세 또 보여지는 면이 없어서 실천이 어려울 수도 있지만, 같은 방식으로 스스로 챌린지를 진행하여 매일 한 문제씩 알고리즘을 풀고 블로그에 포스팅을 남기는 도전을 해보고자 한다. 메인 언어인 자바를 비롯하여 가능하다면 파이썬까지 풀이를 두 가지로 하여 파이썬 복습 겸 챌린지를 시작해 보겠다. 오늘 풀이해 볼 문제는 프로그래머스 level 2로 배정된 너비 우선 탐색 문제이다. https://school.programmers.co.kr/learn/courses/30/lessons/159..

최근에 네이버 공채를 지원해보고, 코딩테스트를 보았다. 나름 준수하게 푼 것 같긴 한데, 생각보다 애먹었던 내용과 비슷했던 문제를 다시 풀어보고자 한다. 너비우선탐색을 진행하는데, 실제탐색은 2차원 배열로 진행하지만, 각 요소가 익숙했던 정사각형이 아닌 정육각형으로 이질감이 있게 생겼다. 물론 이에 따라서 이동가능한 경우의 수도 (상, 하, 좌, 우) 4가지에서 (좌, 좌상, 좌하, 우, 우상, 우하)6가지로 바뀌었다는 점, 더불어 현재 행이 짝수인지, 홀수인지에 따라서 이동하는 위치가 다르다는 것이다. 말로만 설명하면 어려우니 간단한 예시를 보자. 문제에서 예시로 주어진 그림을 보면 척 봐도 모든게 복잡하다. 일단 그림부터도 불편하긴 한데, 행과 열이 거꾸로 되어 있기까지 하다니,,, 하지만 이는 모양..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제를 풀기 위한 조건이 많기도 하지만 조건을 맞추기가 굉장히 까다로웠다. 충족해야 하는 조건을 크게 잡아보면 아래와 같다. 최단거리 탐색 방법 최단거리하면 떠오르는 알고리즘은 단연 다익스트라가 먼저일 것이다. 하지만 모든 간선의 가중치가 1인 경우에는 더 효율적인 BFS가 있기 때문에, BFS를 활용해서 풀이해보도록 하자. 거리가 같은 경우 우선순위가 높은 물고기를 잡으러 가는 방법 가장..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 오늘부터는 본격적으로 코딩테스트를 준비하기 위해서 그래프 탐색문제를 집중적으로 풀이해보려 한다. 오늘 풀이해볼 문제는 골드5문제로 너비우선 탐색을 이용해서 구현을 하는 문제이다. 문제만 보면 조금 복잡해 보일 수 있지만, 예시에 친절하게 나와있기 때문에, 인구이동이 일어나는 날에 필요한 작업을 해주고, 최종적으로 인구이동이 일어난 날을 반환하는 것이다. 천천히 단계적으로 풀이를 해보..

오늘은 알고리즘 스터디원들과 문제풀이를 하는 도중 다들 이 문제를 어려워 하길래 정리할 겸 풀어보았다. 필자는 별 다른 문제를 못느끼고 문제를 풀었는데, 아무리 해도 안된다는 스터디원들의 말을 듣고, 다른 풀이를 인터넷에 검색해보았다. 한 가지 다른 점이 있다면 인터넷과 팀원들의 풀이는 입력값에 반대 방향으로 그래프를 그렸고, 필자는 입력값 방향 그대로 그래프를 구성했다. 문제를 보면 그래프가 방향성이 없는 무방향 그래프가 아니라 방향성이 있는 단방향 그래프라는 것은 눈치챘을 것이다. 사실 필자도 구글링을 해보면서 찾아보았지만 시간 초과가 나는 정확한 이유를 모르겠다... 예상가는 바라고 한다면, 1만개의 정점이 10만개의 간선으로 모두 연결이 되어 있는 상태라면, 모든 노드를 탐색해야 하는 이번 문제에..

오늘은 백준 단계별로 문제풀기 카테고리 중에서 그래프 순회로 분류되어 있는 문제를 풀어보았다. 최근에 그래프 탐색문제로 너비우선탐색 문제를 많이 풀이해왔는데, 이번 문제는 생각보다 까다로웠다. [ 문제 분석 ] 시작점과 도착점은 벽이 없음이 보장된다. 시작점과 도착점을 포함해서 이동 거리의 최소값(최단거리)를 도출한다. 이때 단 한 번의 벽은 부술 수 있다. 도착점에 도달할 수 있는 경우는 최단거리를, 도달할 수 없으면 -1을 출력한다. [ 오답노트 ] 처음에는 그렇게나 골치를 썩이던 벽을 뚫을 수 있다는 말에 반가웠지만 막상 구현에 앞서보니 어떤 벽을 뚫어야 최단거리가 가능할까? 라는 생각을 하다가, 이렇게 생각하기엔 경우의 수가 너무 많아서 도달달 수 있는지 없는지를 판단하기로 했다. 위를 구현하기 ..