Algorithm/프로그래머스18 프로그래머스 - 퍼즐조각 맞추기 문제 설명 한 게임판과 퍼즐조각이 흩어져있는 판이 주어진다. 게임판에 비어있는 란에 흩어져있는 판에 있는 퍼즐을 끼워 넣어 빈 공란을 채우는 개수를 구하는 문제이다. 여기서의 핵심은 퍼즐조각이 위치한 판에서 도형을 추출하는 과정이 중요하다. 그리고 이 도형을 빈 공란에 맞춰 끼울 수 있는지 여부도 판단해야 한다. 나는 해당 도형을 BFS로 추출했다. 그리고 해당 정보를 가지고 객체를 생성했다. 객체는 해당 도형을 표현한 2차원 배열을 필드변수로 가지고 있다. class Puzzle { int cnt; // 1의 개수 int map[][]; public Puzzle(int map[][], int cnt) { this.map = map; this.cnt = cnt; } } 여러 도형들을 BFS로 추출하여 해.. Algorithm/프로그래머스 2023. 4. 17. 프로그래머스 - 아이템 줍기 문제 설명 여러 사각형의 겉면을 따라 목표지점으로 갈 수 있는 최단 거리를 구하는 문제이다. 주의 사항 단순 선을 격자의 칸으로 생각하고 최단거리를 탐색하게 되면 이슈가 있을 것이다. 왼쪽 그림 처럼 겉면이 표시된 경우를 보면 우리가 기대하는 탐색과는 다르게 탐색을 하게 된다. 왜냐하면 4방향을 탐색하면서 갈 수 있는지 판단할 것이기 때문이다. 2배율로 격자판을 확장하면 저런 경우를 방지할 수 있다! 기대하는 바와 다르게 탐색 하는 경우를 방지하기 위해 2배율을 한다면 이런식으로 좌표도 확장 되어 거리가 생기니 기대하는 탐색과 다르게 탐색 되지 않게된다! 또다른 시도로는 각 칸에 갈수 있는 방향을 넣어줬다.(정사각형의 입력을 주어질때) 하지만 해당 방법에서 위 그림의 경우 예외를 방지할 수 있지만 또다른.. Algorithm/프로그래머스 2023. 4. 16. 백준 - 무기공학 문제 설명 격자가 있는 칸에 부메랑(4가지 도형)을 형성하여 최댓값을 구하는 문제이다. 격자의 최대 칸이 5*5이므로 완탐해도 상관 없었다. 현재 위치하고 있는 칸을 부메랑의 중심부라 가정하고 부메랑을 형성하였다. 방문 여부를 판단하여 현재 위치에서 부메랑을 만들 수있는지 판별하였다. 풀이 static boolean v[][]; // 부매랑들의 강도 합의 최댓값을 출력하시오 public static int solution() { v = new boolean[n][m]; pick(0, 0); return answer; } public static void pick(int cnt, int sum) { if (n * m = n || nx >= m; } Algorithm/프로그래머스 2023. 4. 16. 프로그래머스 - 미로탈출 명령어 문제 설명 출발점 , 도착점이 주어진다. 도착점 까지 k거리가 걸려 올 때, 올수 있는 경로는 여러가지이다. 그중 사전순으로 가장 앞선 경로를 나타내는 문제이다. 주의할점 출발지 , 목적지를 다시 방문해도 상관없음에 유의해야 한다. 그래서 아마 일반적인 BFS 큐가 커져 시간초과가 난다. BFS를 사용한다면 큐에 담긴 객체를 최적화 해야한다. TRY 큐안에 담긴 객체를 최적화 하기위해 3가지 시도를 했다. 현재 온 거리 +1 > k 크다면 삽입 x [시간초과] - 4개 맞음 현재 온거리 + 맨헤튼 거리 > k 일 경우 삽입 x [시간초과] - 6개 맞음 3차원 방문 [통과] 사전 순으로 먼저 인것을 골라내기 위해 d,l,r,u 으로 거리백터까지 생성해야함 풀이 public String solution(i.. Algorithm/프로그래머스 2023. 4. 15. 프로그래머스 - 표 편집 문제 설명 주어진 명령을 따라 이행한 뒤 그에 맞는 표 값을 출력하는 문제이다. 완벽한 구현문제이다. 자료구조를 어떻게 사용하지도 물어보는 문제인것같다. TRY 2차원 배열과 map 이 두가지를 이용했다. 2차원 배열에는 각 칸이 가지고 있는 문자값을 저장했고 map에는 해당 칸과 연관되어 있는 각 칸들의 정보를 저장했다. 왜냐하면 병합 또는 병합제거, 정보 수정에 이전에 수행했던 연관되어 있는 칸들이 필요했기 때문이다. 병합시 - 이전에 수행된 연관정보들로 부터 추가로 병합을 이어나가야 하기 때문. 병합제거 - 이전에 수행된 연관정보들 모두 초기화 해야하기 때문. 정보수정 - r,c와 병합을 한 셀들을 기반으로 모든 값을 교체해야하기 때문. 주의사항 다른 연관관계를 이어붙이기 위한 과정에서 변경에 대한.. Algorithm/프로그래머스 2023. 4. 12. 이전 1 2 3 4 다음
