내가 그린 코딩 그림

문제 요약) - 고슴도치 위치, 고슴도치 굴 위치, 물 위치, 돌 위치 등이 주어짐 - 고슴도치가 굴에 들어갈 수 있으면 이동거리, 없으면 주어진 문자 출력 주의점) - 예외 조건이 꽤 있는 편(물이 먼저 찰 예정이면 고슴도치는 진입 불가, 물은 고슴도치 굴에 접근 불가 등) 풀이) 조건 중 물이 접근 예정인 곳은 고슴도치가 접근할 수 없다는 조건이 있습니다. 따라서, 물을 먼저 q에 넣고 고슴도치 위치를 별도로 저장해서 BFS돌 당시에 물이 먼저 bfs를 돌면서 위치를 선점할 수 있게하면 해당 조건을 만족 시킬 수 있습니다. 두 번째로, 고슴도치가 굴에 도착하는지 판단할 수 있도록 고슴도치 굴의 위치는 저장해놓고 map에서 고슴도치가 가는 길은 고슴도치로, 물이 가는 길은 물로 바꿔주면 최종적으로 저장..

문제 요약) - 나이트의 위치가 주어지고 8방향으로 이동이 가능 - 시작점부터 도착지점까지의 이동 거리 출력 주의점) - 8방향 좌표만 잘 기억하면 큰 어려움 x 풀이) 보통은 4방향 탐색을 많이 하는데 약간 응용해서 8방향으로 탐색을 하는 문제이기에 방향만 잘 정해서 8방향 탐색루프를 돌며 bfs 진행 정답) *Scanner 대신 bufferedReader를 사용하면 시간을 더 줄일 수 있습니다. import java.util.*; public class KnightMove7562_blog { static int[] dx = {-1, -2, -2, -1, 1, 2, 2, 1}; // 8방향 탐색 static int[] dy = {-2, -1, 1, 2, 2, 1, -1, -2}; static int t..

문제 요약) - 세로 n, 가로 m이 주어짐 - 출발위치에서 마지막 위치의 최소거리 주의점) - x 풀이) BFS로 풀이를 진행하며 q를 사용할때 x, y등 좌표값을 줘야하기 때문에 class를 선언해주거나 배열자체를 q에 넣어야하는데 별도 클래스를 만드는 것보다 배열이 조금 더 편해서 배열로 풀이했습니다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Maze2178_blog { static int[] dx ..

문제 요약) - 익은 토마토가 4방향의 토마토를 익히는데 1일씩 걸림 - 토마토가 없는 구간은 빈 구간 - 모든 토마토를 익히는데 걸리는 최소 일 수 구하기 주의점) - 보통 세로, 가로 순서로 주는데 해당 문제는 가로, 세로 순서로 주어짐 - 출발점이 한 곳이 아닌 여러 곳일수도 있다. - 토마토가 없는 곳으로 둘러싸여 있으면 평생 안익는 토마토 존재 가능 풀이) BFS로 접근했을 때 가장 직관적인 방법은 토마토 있고 없고 표기할 맵, 방문배열, 거리를 표기할 거리배열 등 총 3개를 사용하면 가장 직관적으로 풀 수 있습니다. 하지만 거리 배열을 잘 활용하면 방문배의 역할도 같이 할 수 있기 때문에 메모리 낭비를 줄여나갈 수 있습니다. 배열을 어떻게 쓰든 시작점을 q에 차곡차곡 넣어놓은 뒤 4방향 탐색을..

문제요약) - 땅에 배추가 심어져 있는 곳 1, 아닌 곳 0으로 주어짐 - 각 분리된 땅의 개수 세기 주의점) - BFS로 풀 때 메모리 초과 주의 풀이) BFS로 풀어본다면 방문 배추가 심어져있고 방문 안했다면 방문해서 채워나가는 식으로 진행할 수 있습니다. BFS가 한번 돌고 count를 더해주면 끝입니다. BFS 코드의 일부분인데 위에 주석처리를 해놓은 것처럼 q에 이미 넣은걸 빼면서 방문처리하게되면 다음껄 q에 넣는 동시에 방문처리 하는 것과 비슷해보이지만 해당 케이스가 많아진다면 q에 들어가는 양이 많아지기 때문에 메모리 초과가 발생할 수 있습니다. 실제로 해당 문제에서 bfs로 풀면서 주석친 부분에서만 방문처리를 하게된다면 메모리 초과가 뜨게 되기 때문에 bfs문제를 만나면 방문처리를 q에 넣..

지금까지 풀어왔던 문제들을 기록하는 공간입니다. 비슷한 문제를 모아보거나 제가 풀었던 것 중 어떤부분에서 주로 틀렸는지 기록용입니다. 색칠 = 다시 풀기 완료 ★ = 추천 문제 백준(B)(https://www.acmicpc.net/) 프로그래머스(L)(https://programmers.co.kr/) 리트코드(L)(https://leetcode.com/) 특정 유형이 많은 알고리즘(우선순위) - 완전탐색, 그래프(DFS/BFS), 해시테이블/문자열, 다익스트라 변수가 많아 많이 풀어봐야하는 알고리즘(후순위) - 구현/시뮬레이션, 스택/큐, 우선순위큐, DP 유형별 출제 빈도 - 완탐 - 구현/시뮬레이션 - DFS/BFS - 문자열/해시 - 힙/다익스트라 - DP DFS B/실버2/연결 요소의 개수 B/실..

문제요약) - 시작단어, 타겟단어가 주어짐 - 주어지는 단어리스트를 통해 시작단어부터 타겟단어까지 변환시키기 - 한번에 한 글자만 바꿀 수 있음 주의점) - DFS를 쓴다면 단어 사용후 백트래킹 할 때 사용한 단어 초기화 - BFS를 쓰는 경우 최단 거리만 찾으면 되기에 크게 중요x 풀이) dfs, bfs 둘 다 괜찮게 사용이 가능한 문제입니다. 다만, 최단 거리를 구하는 문제인 만큼 웬만해서는 bfs를 쓰는게 효율성은 더 잘나오게 됩니다. 1. DFS -> boolean배열 혹은 HashMap을 통해 사용한 단어 구분 -> 사용한 단어가 아니고, 다음단어로 갈 수 있는 단어면 DFS이어서 진행 -> 사용한 단어 표기 해제 package programmers.kit.dfsbfs; import java.u..

테스트 케이스는 맨 아래에 있습니다. 문제요약) - 주어진 맵에서 최단거리(칸 수) 리턴 주의점) - 맵은 n * m 으로 이루어져 있고 서로 다를 수 있음 풀이) 1. 최단거리를 찾기에 BFS로 접근 2. 거리를 판단해야 하기에 주어진 map과 같은 visit 배열을 만들어서 거리를 표기 3. 4방향 탐색을 하면서 q에 넣는데 맵을 벗어나지 않게 처리, 이미 방문한곳을 안가게 처리 4. n과 m의 범위를 주의해야합니다. 저의 경우 이 부분을 헷갈려 시간을 낭비했습니다. 정답코드) import java.util.*; public class gameMinDistance { // 각 4방향을 보기 위한 dx, dy static int[] dx = {0, 1, 0, -1}; static int[] dy = {..

문제요약) - 던전 출입에 필요한 피로도, 클리어시 소모되는 피로도 주어짐 - 최대한 많은 던전 돌았을때의 클리어 던전수 리턴 주의점) - X 풀이방법) 1. 모든 던전 케이스를 확인해야해서 DFS로 완전탐색 2. 이미 돈 던전은 전역으로 방문 배열 잡기 3. 방문배열, 피로도 등 확인해서 던전 돌 수 있는지 판단 4. 뎁스를 answer에 저장 DFS를 통해 완전탐색을 해야하는 유형이 문제인데 풀이가 바로 떠오르지 않아서 던전이 A, B, C 총 3개인 경우로 생각하고 재귀로 들어가는 과정을 그림을 그려보았습니다. public class Fatigue { static boolean[] visited; static int answer = 0; static boolean flag; public static..

문제요약) - 작업의 요청시기, 작업 소요시간으로 날라옴 - 각 작업이 요청부터 작업 끝까지 걸린시간 평균 리턴 풀이방법) 우선 순위큐를 사용 1. 각각 요청온 순서대로 job 정렬, 빨리 끝나는 순서대로 우선순위큐 정렬 2. 만약, 요청 처리가 가능한 시간이면 빨리 끝나는 작업부터 시행해서 대기시간 최소화 3. 만약, 앞 작업이 끝나고 뒷작업 요청 시간이 아직 남았을 경우 실행대기를 한게 아니므로 해당 시간은 제외해서 계산 위 사진에서를 예시로 들면 실제 기다린 시간 + 실제 실행 시간만 계산해야한다.