전체 글

너비 우선 탐색(BFS, Breadth-First Search)BFS는 그래프 탐색 알고리즘 중 하나로, 시작 노드와 거리가 가장 가까운 노드를 우선하여 방문하는 방식의 알고리즘이다. BFS는 최단 경로를 찾는 알고리즘으로도 많이 쓰이곤 하는데, 시작 노드로부터 직접 간선으로 연결된 모든 노드를 먼저 방문하기 때문이다. 쉽게 말해 문제에 대한 답이 많은 경우 너비 우선 탐색은 이 답 중에서도 가장 가까운 답을 찾을 때 유용하다. BFS는 주로 FIFO(선입선출) 방식인 큐 자료구조를 사용하여 구현한다.인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다.(DFS는 이와 반대로 스택을 통해 구현한다.) BFS 작동 원..

난이도 : 골드 5유형 : BFS / 큐링크 : https://www.acmicpc.net/problem/7569구현 시간 : 1시간       문제풀이토마토 박스를 3차원 배열에 저장한다.1번 과정에서 빈칸의 개수, 익은 토마토의 개수를 저장한다.(총 배열의 크기 - 빈칸의 개수) 가 익은 토마토의 개수와 같다면 0 을 출력하고 종료한다.익은 토마토가 있는 좌표를 Queue에 저장한다.Queue 가 비어있지 않을때까지 반복문 시작Queue의 현재 size 를 저장하고, size 만큼 for문을 돌린다. (BFS 탐색의 Depth를 기준으로 하루가 지남을 판별하기 위함)Queue에서 poll한 익은 토마토의 위치 기준 상하좌우아래위 6방향으로 탐색한다.만약 탐색 위치가 박스 위치를 벗어나면, 다음 방향으..

난이도 : Level 3유형 : BFS / 큐구현 시간 : 1시간 (못품)링크: https://school.programmers.co.kr/learn/courses/30/lessons/67259 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr      문제풀이위 문제는 2020 카카오 인턴십 코딩 테스트에 출제된 문제로 현재까지 풀어본 BFS 문제와는 다르게 생각이 많이 필요했다.최단 경로를 구한다고 하더라도 그 경로가 가장 저렴한 비용이 들지 않기 때문에 최소 비용을 저장해서 문제를 구현했다.  x, y 좌표 및 방향 정보를 저장하는 cost 배열을 사용해서 시작점을 제외한 모든 데이터를 최대값으로 저..

난이도 : Level 2유형 : BFS / 큐구현 시간 : 30분링크 :https://school.programmers.co.kr/learn/courses/30/lessons/159993  프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr      문제풀이위 문제는 BFS 탐색 알고리즘을 사용하여 최단 경로를 찾는 문제이다. 앞서 백준을 통해 BFS / DFS 문제를 많이 연습해두었기에 알고리즘을 구현하는 것은 오래 걸리지 않았지만 BFS 를 총 2번 실행하는 과정에서 데이터 초기화에 문제를 겪었다. 시작점, 레버, 도착지의 위치 정보 저장시작점 -> 레버까지 최단 경로를 BFS 를 통해 구함만약 레버까지..

깊이 우선 탐색(DFS, Depth-First Search)DFS는 그래프 탐색 알고리즘 중 하나로, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.시작 노드부터 탐색을 시작하여 간선을 따라 최대 깊이 노드까지 이동하여 차례대로 탐색하는 알고리즘이다. DFS는 주로 스택(Stack)을 통해 구현하거나, 재귀문을 통하여 구현한다.DFS 작동 원리1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면 그 인접 노드를 스택에 넣고 방문 처리를 한다.3. 방문하지 않은 인접 노드가 없다면 스택에서 최상단 노드를 꺼낸다.4. 2 ~ 3번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.   DFS의 작동원리를 이해하기 위해 아래 사진을 준비..

난이도 : 골드 4유형 : 구현 / 시뮬레이션 / 큐링크 : https://www.acmicpc.net/problem/3190구현 시간 : 1시간   문제풀이앞서 풀었던 시뮬레이션 / 구현 문제인 로봇 청소기보다 구현하는데 오랜 시간이 걸린 것 같다. 뱀의 길이는 조건에 따라 늘어나고, 늘어나는 뱀의 몸을 저장할 자료구조를 생각하는게 특히 고민할 부분이였던 것 같다. [BOJ] 14503번 로봇 청소기 - JAVA[자바]난이도 : 골드 5유형 : 구현 / 시뮬레이션링크 : https://www.acmicpc.net/problem/14503      문제풀이로봇 청소기의 규칙대로 알고리즘을 차례대로 구현했다.구현에  대한 고민은 크게 어렵지 않았다tenaciously.tistory.com 보드(룸)의 크기..

난이도 : 골드 5유형 : 구현 / 시뮬레이션링크 : https://www.acmicpc.net/problem/14503      문제풀이로봇 청소기의 규칙대로 알고리즘을 차례대로 구현했다.구현에  대한 고민은 크게 어렵지 않았다. 로봇 청소기의 방향은 Map 자료구조를 사용해서 저장했다.   1차 시도 - 통과import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.HashMap;import java.util.Map;public class Main { public static void main(String[] args) throws IOException { ..

난이도 : 실버 3유형 : 구현 / 시뮬레이션링크 : https://www.acmicpc.net/problem/1966      문제풀이문서 출력 인덱스, 우선순위를 저장할 PrintJob 클래스 구현우선순위 비교 (현재 PrintJob 보다 높은 우선순위가 있는지 확인)2번에서 현재 PrintJob 보다 높은 우선순위가 있다면현재 문서를 다시 큐의 맨 뒤로 삽입현재 PrintJob 의 우선순위가 제일 높다면출력 순서 +1출력된 문서의 idx 가 M이라면 반복문 탈출 후 출력   1차 시도 - 통과import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList..

난이도 : 실버 5유형 : 그리디 / 구현 / 우선순위 큐링크 : https://www.acmicpc.net/problem/1417     문제 풀이후보의 수가 1 이하일 경우 0 반환1번(다솜이) 득표수 저장, 이외 다른 후보들의 득표수 저장각 후보 득표수들의 최대 득표수 저장 및 후보 인덱스 저장다솜이의 득표수가 최대 득표수보다 크다면 반복문 탈출아니라면 최대 득표자의 득표수를 -1, 다솜이 득표수 +1 1차 시도- 통과import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { public static void main(String[] args) throws ..

난이도 : 실버 4유형 : 문자열 / 그리디 / 구현링크: https://www.acmicpc.net/problem/1213      문제 풀이문자열의 길이가 홀수인 경우팰린드롬을 만들기 위해서는 개수가 홀수인 알파벳이 정확히 하나여야 함개수가 홀수인 알파벳이 하나가 아닌 경우 디폴트 메시지(“I’m Sorry Hansoo”)를 출력팰린드롬 구현홀수인 알파벳을 제외하고 문자열을 사전순 정렬문자열의 절반(인덱스 0부터 짝수 간격으로 선택한 문자)을 추출하여 반쪽 문자열을 생성.2번에서 만든 문자열 + 홀수인 알파벳 + 2번에서 만든 문자열을 reverse한 문자열을 결합하여 팰린드롬 반환문자열의 길이가 짝수인 경우팰린드롬을 만들기 위해서는 개수가 홀수인 알파벳이 없어야 함개수가 홀수인 알파벳이 존재할 경우..