내가 그린 코딩 그림

문제 요약) - 고슴도치 위치, 고슴도치 굴 위치, 물 위치, 돌 위치 등이 주어짐 - 고슴도치가 굴에 들어갈 수 있으면 이동거리, 없으면 주어진 문자 출력 주의점) - 예외 조건이 꽤 있는 편(물이 먼저 찰 예정이면 고슴도치는 진입 불가, 물은 고슴도치 굴에 접근 불가 등) 풀이) 조건 중 물이 접근 예정인 곳은 고슴도치가 접근할 수 없다는 조건이 있습니다. 따라서, 물을 먼저 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에 넣..

백준 17413번 단어뒤집기 자바 정답 코드 1. 정방향 글자 -> Queue사용 2. 역방향 글자 -> Stack사용 3. char를 더하는 경우가 잦아서 불변 객체인 String 대신 가변객체인 StringBuilder 사용 package bakjun.string; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; public class B17413 { public static void main(String[] args) throws IOExcepti..

[프로그래머스][L2] 최댓값과 최솟값 자바 문제 풀이 및 정답 피보나치에 대한 문제를 보면 재귀함수를 떠올릴 수 있지만 해당 문제는 재귀를 통해 풀면 안된다는게 유추되는 문제입니다. n번째 수를 1234567로 나눈 수를 구해야 하고 n은 최대 100,000까지로 주어지게되는데 재귀를 이용하면 50번째 근처만 가도 굉장히 오래걸리게 됩니다. 즉, 시간 효율이 굉장히 안좋기 때문에 10만번째의 수까지 재귀로 구한다는건 이미 아니란걸 어느정도 유추할 수 있습니다. 피보나치를 재귀로 풀어가는 과정에 대한 블로그를 참고해보면 조금 더 쉽게 알 수 있습니다. https://velog.io/@beton/문제풀이재귀함수의-형태로-피보나치-수열-구하기 [문제풀이]재귀함수의 형태로 피보나치 수열 구하기 n번째의 피보나..

[프로그래머스][L2] 최댓값과 최솟값 자바 문제 풀이 및 정답 프로그래머스 레벨2 최댓값과 최솟값 문제입니다. split을 사용할 수 있는지에 대한 문제로 보입니다. split을 사용해 문자열을 구분하고 int값을 가져오면 어렵지 않게 해결할 수 있는 문제입니다. 정답 코드 확인

[프로그래머스][L2] 숫자의 표현 자바 문제 풀이 및 정답 프로그래머스 레벨2 숫자의 표현 문제입니다. - 연속된 숫자와 구간의 합 -> 투포인터 - O(n) 자연수의 "연속된" 숫자의 합이라는 점에서 투포인터를 이용할 수 있다고 생각했습니다. 문제를 풀면서 슬라이딩 윈도우와 투포인터의 차이를 알게 됐는데 바로 가변적인 길이를 가지면 투포인터이고 고정적인 크기를 가지면 슬라이딩 윈도우라는 것입니다. 둘 다 연속적인 처리를 할 때 사용하는 알고리즘입니다. 해당 문제는 가변적인 크기를 가지기 때문에 투포인터라고 명명하는 것이 맞겠고 위 방식으로 접근 했을 경우 배열은 아니지만 배열과 같은 자연수들을 left, right 포인트 기점으로 한 번 훑고 지나가기 때문에 O(n)의 시간복잡도를 가지게 됩니다. 정..

[프로그래머스][L1] 자릿수 더하기 자바 문제 풀이 및 정답 두 가지 방법으로 문제를 풀 수 있습니다. 방법 1 - String으로 변환 후 자릿수 별로 잘라서 int값 계산해주기 방법2 - 한 자릿수가 될 때까지 10씩 나눠서 빼주기 코드보기