내가 그린 코딩 그림

문제 요약) - 익은 토마토가 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. 만약, 앞 작업이 끝나고 뒷작업 요청 시간이 아직 남았을 경우 실행대기를 한게 아니므로 해당 시간은 제외해서 계산 위 사진에서를 예시로 들면 실제 기다린 시간 + 실제 실행 시간만 계산해야한다.

프로그래머스 고득점 kit 해시 카테고리의 레벨 3 문제 "베스트앨범" 이라는 문제입니다. 문제요약) - 장르, 재생횟수가 주어짐 - 인기 있는 장르, 재생횟수, 인덱스 순서대로 분류해서 리턴 주의점) - 특정 장르의 모든 재생횟수를 더해서 가장 인기있는 장르 순서를 파악 - 한 장르에서 최대2곡만 선정해서 정답배열에 담아야함 풀이방법) 1. 특정 장르를 계산 -> HashMap활용해서 재생횟수를 더함 2. 인기있는 장르부터 선별하기 위해 내림차순 정렬이 필요하기에 List정의, 람다식을 활용해 재생횟수 기준으로 내림차순 정렬 3. List의 key값 순서대로 최대 두 곡을 뽑아서 정답배열에 분배 특정 장르에서 재생횟수가 많은 부분을 찾는건 조금 더 좋은 코드로 쓸 수 있을 것 같습니다. 코드의 중복 제..

프로그래머스 고득점 Kit 해시 분류의 "의상" 이라는 문제입니다. 문제요약) - 여러 종류의 의상이 주어짐 - 매일 다른 옷을 입는 경우의 수 리턴 주의점) - 옷을 하나라도 입으면 인정 풀이 방법) - 종류별로 옷의 개수 + 해당 종류의 옷을 안입는 경우를 계산해서 다른 옷의 종류와 곱 정답 코드) 경우의 수만 헷갈리지 않고 계산해준다면 큰 어려움 없이 풀 수 있는 문제 같습니다.

프로그래머스 고득점 Kit 해시 분류의 "전화번호 목록"이라는 문제입니다. 문제요약) - 전화번호 여러개가 주어짐 - 그 중 어떤 전화번호가 다른 전화번호의 접두사면 false, 아니면 true 리턴 주의점) - 시간복잡도 고려(phone_book의 길이가 100만이어서 O(n2)시 시간초과 위험) - 포함여부가 아닌, "접두사" 여부 판단 풀이 방법) 1. 단순 무식하게 for문 두번 돌리면서 비교 O(n2). -> 2022년까지 되던 방법이었으나 현재 효율성 기준을 보완한것으로 보임. 이 방법으로 진행 시 효율성 테스트 통과x 2. 문자열 정렬 특성을 활용해서 정렬 후 해시값 비교 1번 방법은 사실 잠깐이라도 되었던게 이상할 정도의 문제로 보입니다. 2번으로 풀이하시면 되겠습니다. 정답 코드) 여기서..