알고리즘 (22) 썸네일형 리스트형 프로그래머스 - 2018 KAKAO BLIND RECRUITMENT > [1차] 프렌즈4블록 https://programmers.co.kr/learn/courses/30/lessons/17679 프렌즈4블록 블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록". 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다. board map 만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다. 같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다. board map 블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다. board map.. 프로그래머스 - 2019 KAKAO BLIND RECRUITMENT > [1차] 비밀지도 https://programmers.co.kr/learn/courses/30/lessons/17681 비밀지도 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 "공백"(" ") 또는 "벽"("#") 두 종류로 이루어져 있다. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 "지도 1"과 "지도 2"라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백.. 프로그래머스 - 2018 KAKAO BLIND RECRUITMENT > [1차] 캐시 https://programmers.co.kr/learn/courses/30/lessons/17680 캐시 지도개발팀에서 근무하는 제이지는 지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터베이스에서 읽어 보여주는 서비스를 개발하고 있다. 이 프로그램의 테스팅 업무를 담당하고 있는 어피치는 서비스를 오픈하기 전 각 로직에 대한 성능 측정을 수행하였는데, 제이지가 작성한 부분 중 데이터베이스에서 게시물을 가져오는 부분의 실행시간이 너무 오래 걸린다는 것을 알게 되었다. 어피치는 제이지에게 해당 로직을 개선하라고 닦달하기 시작하였고, 제이지는 DB 캐시를 적용하여 성능 개선을 시도하고 있지만 캐시 크기를 얼마로 해야 효율적인지 몰라 난감한 상황이다. 어피치에게 시달리는 제이지를 도와, .. 프로그래머스 - 2019 KAKAO BLIND RECRUITMENT > 오픈채팅방 https://programmers.co.kr/learn/courses/30/lessons/42888 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오픈 채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고, 나가는 것을 지켜볼 수 있는 관리자창을 만들기로 했다. 채팅방에 누군가 들어오면 다음 메시지가 출력된다. "[닉네임]님이 들어왔습니다." 채팅방에서 누군가 나가면 다음 메시지가 출력된다. "[닉네임]님이 나갔습니다." 채팅방에서 닉네임을 변경하는 방법은 다음과 같이 두 가지이다. 채팅방을 나간 후, 새로운 닉네임으로 다시 들어간다. 채팅방에서 닉네임을 변경한다. 닉.. 백준 - 2636번 치즈 - java https://www.acmicpc.net/problem/2636 접근법 오랜만에 감 다시 잡아야해서 살짝 쉬운문제로 꺼냈다 기본적인 BFS로 풀었다 1. 치즈가 모두 녹았는지 체크해서 모두 0이면, 반복문 종료 1-1. checkZero로 그냥 배열 탐색해서 0이 아니면 바로 false 리턴시키고, while 문 진입 2. TIME변수 값 증가시킴으로 시간흐름 현재 치즈배열을 로직에 따라 1시간 후 치즈로 변경 cheese = bfs(cheese) 3. bfs안에서는 우선 현재 치즈덩어리 개수를 MASS에 기록해둠 (0,0)에는 치즈가 놓이지 않은 공기 공간이니까 여기를 bfs로 탐색해서 구멍인 공간(0)과 외부공간(2)로 구분함 retArray를 주석에 설명한대로 완성해서 리턴함 소스 import j.. 백준 - 17070번 파이프 옮기기 1 - java https://www.acmicpc.net/problem/17070 이전 파이프의 상태에 따라서 다음 파이프가 3가지 타입으로 선택이 가능함 접근법 경우의 수를 따지는 BFS로 접근하였는데, 대부분 DP로 푼것 같다,, TODO DP로 푸는법도 해봐야할듯 끝좌표를 기준으로 BFS 탐색을 하는데, Pipe클래스를 만들어서 이전 파이프 타입을 챙김 curType의 값에 따라 3가지로 분기해서 경우를 따져보고, 해당되면 queue에 넣어줌 현재 좌표가 끝지점이면 answer값 올려주고, 다음 경우 탐색 애초에 끝지점이 1이면, 무조건 불가하니 0 출력하고 리턴 소스 import java.util.*; import java.io.*; public class Main { static int N; static in.. 백준 - 1719번 택배 - java https://www.acmicpc.net/problem/1719 접근법 다익스트라로 최단거리를 구하기 위해 ArrayList[] ADJ 배열을 생성함 배열에 양방향으로 간선 연결을 해줌2차원 배열로 하게되면, 연결되어있는지 아닌지 n번 탐색을 해야하는데, arrayList면 size만큼만 탐색하면 되니 시간을 아낄 수 있음 각각의 노드를 기준으로 다익스트라 함수를 탐색 path[] 배열로 현재 노드의 앞 노드를 기록해둠 출력 시, 현재 노드면 -를 출력 그게 아니라면, 현재 노드에서 앞 노드를 찾고, 그게 끝인지 보고 아니면 또 앞 노드, ... 반복하여 출력 소스 import java.io.BufferedReader; import java.io.IOException; import java.io.Inp.. 백준 - 11048번 이동하기 - java https://www.acmicpc.net/problem/11048 접근법 기본적인 DP 풀이법 핵심은 DP[nextX][nextY] < DP[x][y] + Array[nextX][nextY]를 판단해서 더 큰 경우 DP배열을 갱신해주고 출력할 때는 마지막 (N-1, M-1)값을 출력해줌 소스 import java.util.*; import java.io.*; public class Main { static int N, M; static int[][] Array; static int[][] DP; static int[][] dir = {{1,0},{0,1},{1,1}}; public static void main(String[] args) throws IOException { BufferedReader .. 이전 1 2 3 다음
