문제 링크 : https://softeer.ai/practice/7726 사용 언어 : JAVA 아무튼 유령에게 잡히지 않고 남우가 탈출할 수 있다면 Yes, 못한다면 No를 출력 내 생각 초기 생각 유령은 필요에 따라 이동하지 않아도 되므로, 그냥 남우는 냅두고 최대한 빨리 탈출구로 가서 버티면 된다고 생각했다. 그래서 남우가_탈출구에_도착하는_시간(bfs) >= 유령이_탈출구에_도착하는_시간이라면 남우는 반드시 탈출 할 수 없을 것이라고 생각했다. MIN = 남우~출구까지의 최단 거리 for 유령: 유령들 min = Math.abs(유령.x - 출구.x) + Math.abs(유령.y - 출구.y) min **유령보다 먼저 도달할 수 있는 곳** // 만약 중간에 이동할 수 있는 곳이 없다면 탈출 실패..
문제 링크 : https://softeer.ai/practice/6266 사용 언어 : JAVA 내 생각 초기 생각 처음에는 HashMap를 만들어서 회의 시간마다 true로 체크하고, 출력할 때 다시 계산하는 방식을 사용하려 했다. 그런데 회의실이 빈 start시간, end시간을 일일이 구하는게 너무 귀찮아서 다른 방식을 생각했다. 개선 회의가 (9-10), (12-13), (16-17) 이렇게 있다면, 회의실이 비어있는 시간대는 (10-12), (13-16), (17-18) 이렇게 된다. 아래의 (1)처럼 주어진 회의 시작/종료 쌍을 (2)처럼 변경하여 새로운 쌍을 짓는 것이다. (1) (회의1 시작, 회의1 종료) / (회의2 시작, 회의2 종료) / ... / (회의N 시작, 회의N 종료) (2)..
문제 링크 : https://www.acmicpc.net/problem/14500 사용 언어 : JAVA 내 생각 초기 생각 모든 N X M 칸을 돌면서 5가지 테트로미노를 모두 대조, 최댓값을 갱신한다. 근데 테트로미노의 블록들을 회전시키는 함수를 짜는게 까다로워서,, 그냥 회전으로 만들 수 있는 모든 모양을 2차원 배열로 만들어서 돌렸다. 그래서 이 정보를 담을 ArrayList 를 생성하고 수기로 열심히 넣어줌 코드는 아래와 같다. 더보기 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTok..
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/49191 사용 언어 : JAVA 내 생각 초기 생각 처음에는 Topology Sort를 활용한 문제인 줄 알았는데 아무리 생각해도 정렬을 하고서 어떻게 순위를 계산할 방법이 떠오르지 않았다... 결국 구글 신의 도움을 받고, "플로이드 와샬"을 활용해야 한다는 것을 알게되었다. 적용 어떻게 플로이드 와샬을 사용할 수 있을까? 일단 2차원의 인접 배열을 만든다. 그리고 가중치를 세가지를 사용할 것인데, 각각 1, 0, -1이다. (사실 값은 중요하지 않고 세가지 상태를 나타낼 수 있으면 된다) array[A][B] == ? 1: A가 B를 이긴다 0: 알 수 없다. -1: A가 B에게 진..
링크 : https://school.programmers.co.kr/learn/courses/30/lessons/86053 사용 언어 : JAVA 풀이 변수, 조건 정리 a : 신도시에 필요한 금 총량 b : 신도시에 필요한 은 총량 g[i] : i번째 도시가 가지고 있는 금 총량 s[i] : i번째 도시가 가지고 있는 은 총량 w[i] : i번째 도시가 트럭에 적재할 수 있는 최대 적재량 t[i] : i번째 도시에서 신도시까지 편도로 이동 시 걸리는 시간 각 도시에서 출발하는 모든 트럭은 동시에 운행할 수 있으며, 마지막까지 움직이는 트럭의 이동 시간까지만 구하면 된다. 아이디어 목표 금 a kg과 은 b kg을 전달할 수 있는 가장 빠른 시간을 구한다. 이럴 때 사용할 수 있는게 이분 탐색이다. 스무..
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12984 사용 언어 : JAVA 내 생각 초기 생각 // floor in [max_floor, 0] func(money, floor) { // 현재 floor를 기준으로 지형을 모두 메운다 // money1: floor까지 다 채우는 비용 money1 = fillFloor(floor); MIN = Math.min(MIN, money); // 현재 floor의 모든 지형을 삭제한다 // money2: floor를 다 삭제하는 비용 money2 = delFloor(floor); // 현재 층을 다 밀고 아래 층을 기준으로 func 반복 func(money + money2, floor-1);..
링크 : https://www.acmicpc.net/problem/1167 사용 언어 : JAVA 문제 설명 짧은 하소연 🥲 더보기 이 문제도 정말..^^ 어이없는 실수로 근 이틀을 고민했었다. 정석대로 짠 것 같은데 왜 안되지? 다른 사람의 소스코드를 참고해봐도 내 코드랑 다른 게 없었다. 심지어 그 사람은 Scanner 쓰고 통과했는데 난 BufferedReader 썼는데도 안됐다ㅋㅋㅋ 그래서 뭐가 다른거지... 하고 코드 한줄씩 바꾸면서 계속 돌려봄 ㅋㅋㅋ 내가 이 문제 골2에서 골1로 올려버리겠단 마음으로 함. 근데 나중에서야 내 문제를 알게 되었고 내가 멍청이라는 걸 깨달았다. 내 생각 초기 생각 플로이드 와샬 처음에는 든 생각은 플로이드 와샬(Floyd Warshall)이었다. 골드 2라 안될..
링크 : https://www.acmicpc.net/problem/2981 사용 언어 : JAVA 내 생각 대체 왜 그랬는지는 모르겠는데 골드 4라 쉽겠지 생각했다. 근데 아무리 생각해도 어떻게 해야하는지 감도 안오고,, 혹시나 제출해봐도 계속 틀리고 시간초과나고ㅋㅋㅋ 결국 멘탈 터져서 나중에는 출력에 println 써서 0퍼 컷 당하고 그랬다ㅎㅎ;; 처음에 쉽다고 얕봐서 더 멘탈이 나간 듯 하다. 결국 패배를 인정하고 구글링했다. 그리고 내 기초 지식이 부실했음을 깨닫고 컴공의 기본 of 기본인 유클리드 호제에 대해 다시 공부하였고, 까먹지 않기 위해 울면서 포스팅을 쓴다 ㅠㅠ 초기 생각 사실 맨 처음에도 유클리드 호제 같긴 했는데 당최 어떻게 써먹어야하는질 몰라서 그냥 냅다 풀었다. for (extr..
링크 : https://www.acmicpc.net/problem/5052 사용 언어 : JAVA 내 생각 초기 생각 트라이 구조를 활용하자. 트라이(trie) 자료구조란? 동적 집합이나 연관 배열을 저장하는 데 사용되는 트리 자료 구조이다. 주로 문자열이 키인 경우가 많다. 쉽게 말해 그냥 문자열을 트리 구조로 표현(할 때 주로 사용)하는 것인데, 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유한다는 특징이 있다. 루트는 빈 문자열에 연관된다. 이 자료구조를 어떻게 활용할 수 있을까? 하나의 Node 객체에 담겨야하는 데이터는 두가지라고 생각했다. boolean: 이 노드를 마지막으로 갖는 문자열이 있는가? Node[10]: 자식 노드 (자식으로 올 수 있는게 0~9, 총 10가지이므로 ..
링크 : https://www.acmicpc.net/problem/13904 사용 언어 : JAVA 풀이 마감일이 많이 남은 순으로 정렬한 후, 가장 마지막 날부터 선택할 수 있는 가장 최선의 선택을 고른다. ex) 일 별 해결할 수 있는 과제 목록 6일 째 : 5 5일 째 : 5 4일 째 : 5 60 40 10 3일 째 : 5 60 40 10 30 2일 째 : 5 60 40 10 30 50 1일 째 : 5 60 40 10 30 50 20 6일 째부터 1일 째까지 선택할 수 있는 최고의 가치를 가진 숙제를 선택한다. 그리디 알고리즘의 경우 몇가지 팁이 있다고 한다. 이번 선택이 다음 선택에 영향을 받지 않도록 만들어 보기 뒤에서부터 생각하기 이번 문제의 경우 두 가지 팁 다 적용된 사례라고 볼 수 있다...
