[백준 20949] 효정과 새 모니터 (자바)
www.acmicpc.net/problem/20949 20949번: 효정과 새 모니터 효정은 새해를 맞이하여 새 모니터를 구매하고자 한다. 효정은 돈이 많기 때문에 77인치 모니터를 구매할 것이다. 모니터를 구경하던 효정은 놀라 자빠질 수밖에 없었다. 모니터가 너무 많아 고 www.acmicpc.net 난이도 : 실버 5 정렬하는 문제입니다. PPI가 높은 순서 -> 같다면 번호가 작은 순서로 정렬하면 됩니다. 모든 모니터의 크기가 같으므로 나누고 루트 씌울 필요 없이 w^2 + h^2로 계산했습니다. 함수 main 단순히 입력 받고 정렬 후 출력했습니다. 정렬은 람다로 작성해봤습니다. class Monitor 번호와 계산된 값을 변수로 가집니다. 생성자에서 calculator를 호출해 계산된 값을 넣어..
[프로그래머스] 프렌즈4블록 (자바)
https://programmers.co.kr/learn/courses/30/lessons/17679 코딩테스트 연습 - [1차] 프렌즈4블록 프렌즈4블록 블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 프렌즈4블록. 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙 programmers.co.kr 난이도 : 레벨 2 구현만 잘한다면 무리 없이 풀 수 있는 문제입니다. 인접한 4개의 블록을 검사하고 이 블록들을 삭제하며 밑으로 내린 후 다시 검사하면 되는 문제입니다. 여기서 주의할 점은 4개의 블록을 검사하자마자 삭제 후 다음 블록을 검사한다면 부분 겹치는 블록이 있을 경우에 문제가 생깁니다. 저는 이 부분을 큐를 이용하여 모든 블록을 ..
[LeetCode] Two Sum (자바)
https://leetcode.com/problems/two-sum/ Two Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 난이도 : Easy 배열에서 2개의 원소를 더한 값이 target과 일치하면 이 원소들의 index를 반환하는 문제입니다. 가장 쉬운 방법으로는 2중 for문을 이용하여 풀 수 있지만, O(N^2)의 시간복잡도를 가지게 되어 매우 느린 방법입니다. 어떤 숫자 num이 있을 때 target을 만들 수 있는 다른 원소는 target ..
[백준 5052] 전화번호 목록 (자바)
https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 난이도 : 골드 4 트라이를 이용했습니다. 2021/01/07 - [문제풀이/자바] - [백준 14725] 개미굴 (자바) [백준 14725] 개미굴 (자바) https://www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 ..
[백준 14725] 개미굴 (자바)
https://www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net 난이도 : 골드 2 트라이를 이용하여 풀었습니다. 트라이는 문제에서 주어진 그림처럼 문자열 트리라고 생각할 수 있습니다. 전역 변수 StringBuilder sb = 트라이 구조를 그려서 저장할 변수 함수 void main 입력을 받고 트라이를 구현합니다. 19번째 줄에서는 n개의 입력을 받고 24번째 줄에서는 한 줄의 입력에서 k개의 입력을 트라이에 넣습니다. 노드는 트라이를 탐색..
[백준 1937] 욕심쟁이 판다 (자바)
https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 난이도 : 골드 3 DFS와 메모이제이션을 이용했습니다. 메모이제이션은 다이나믹 프로그래밍처럼 이전에 계산해 둔 값을 나중에 계속 이용하여 불필요한 계산을 줄일 수 있습니다. 이 문제에서 숲의 최대 크기는 500x500입니다. 메모이제이션을 이용하여 계산의 중복을 막아 시간 초과를 예방했습니다. 판다가 이동할 4방향의 칸을 DFS를 통해 계산해줬습니다. 그리고 4방향 중 최댓값에서 1을 ..
[백준 3860] 할로윈 묘지 (자바)
https://www.acmicpc.net/problem/3860 3860번: 할로윈 묘지 오늘은 할로윈이다. 상근이와 친구들은 할로윈을 기념하기 위해 묘지를 방문했다. 상근이와 친구들은 한 명씩 묘지로 들어가고, 혼자서 묘지의 출구를 찾아야 한다. 이제, 상근이의 차례가 돌아 www.acmicpc.net 난이도 : 플레 5 벨만-포드를 이용했습니다. 입구, 귀신 구멍의 입, 출구 등 각 포인트를 기준으로 적절히 경로를 구했는데 시간 초과를 받았습니다. 모든 좌표가 포인트인 경우를 고려하지 못한 풀이였습니다. 그래서 각 좌표에서 이동할 수 있는 경우의 수를 경로로 만들고 벨만-포드를 돌리니 성공했습니다. 전역 변수 int w, h = 맵의 크기 int map[][] = 맵의 상태를 저장할 배열 long ..
[백준 1865] 웜홀 (자바)
https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 난이도 : 골드 4 음의 가중치가 있는 그래프의 최단 거리를 구할 수 있는 벨만-포드 알고리즘을 이용했습니다. 다익스트라 알고리즘은 음의 가중치를 가지는 그래프의 최단 경로를 구하지 못하고 무한 루프에 빠지게 됩니다. 하지만 벨만-포드 알고리즘은 최단 경로를 구할 수 있고 엄청난 시간 복잡도를 자랑합니다. 또, 음의 가중치들이 만드는 사이클을 탐지할 수 있습니다. 벨만-포드 알고리즘은..