본문 바로가기

Algorithm

백준 1408 24 Java 2021. 3. 14. 24 친구가 풀어달라고 해서 오랜만에 풀어본 백준 문제이다. 구글에 검색해도 자바 풀이는 안 나온다고 해서 제일 먼저 올려보고픈 욕심에 풀이를 올려본다.😉 문제에서 핵심은 현재 시각이 임무 시작 시각보다 큰 경우를 처리하는 방식이다. boolean 변수로 뺄셈 시 앞의 수를 빌려왔는지 체크한다. 그리고 다음으로 넘어갔을 때 boolean 변수에 체크가 되어있으면 1을 빼주면 된다. 빌려오는 경우에 hour면 24를 더해주고 minute, second면 60을 더해준다. 그리고 boolean 변수에 체크한다. 초심자 친구에게 최대한 쉽고 친절하게 알려주고 싶어서 api를 최대한 안쓰고 변수명을 한글로 지었다. 불편해도 이해해주시길..ㅎ import java.util.Scanner; public class ..
프로그래머스 구명보트 Java 2020. 11. 23. 구명보트 재밌게 푼 문제여서 오랜만에 알고리즘 문제 풀이 글을 쓴다. 문제 제한사항으로 무인도에 갇힌 사람이 최대 50,000명까지 주어질 수 있다. 이중 for문을 돌리기만해도 약 25억번 연산이 일어나서 O(N^2)으로는 풀 수 없겠구나 생각했다. 그래도 처음엔 이중 for문을 사용한 방법밖에 떠오르지 않아서 이중 for문에 최대한 if문으로 연산 회수를 줄이기 위해 Map 인터페이스를 활용하는 방법으로 풀고자 했다. 결과는 시간 초과가 나왔다. 허허. 결국 이 문제는 곧 죽어도 한 번의 for문으로 해결해야하는 문제인 것을 확인했다. 그렇게 고민하다가 나온 방법이 있는데 코드로 설명하는게 가장 빠를 듯하다. import java.util.Arrays; public class Solution { pu..
백준 1937 욕심쟁이 판다 Java 2019. 12. 10. 정답률 29%인 dp 문제 욕심쟁이 판다 문제이다. 분류가 dp인것을 모르고 푼 문제라서 DFS로 판다가 살 수 있는 최대경로를 찾아내면 되겠다! 생각해서 구현했는데 시간초과가 나왔다. 그리고 나서 고민...또 고민했지만 시간을 줄일 수 있는 방법을 생각해내지 못했다. 답은 메모제이션을 활용하는 것이였다. 메모제이션은 DP의 핵심 기술이다. 메모제이션 설명 링크 https://namu.wiki/w/%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98 DFS에서 메모제이션을 활용한다면 실행시간을 훨씬 단축할 수 있다. 무튼 판다가 시작할 수 있는 위치를 전부 메모제이션을 활용한 DFS로 최대 생존 일을 구하면 된다. 편한 방식에 익숙해져서 기본적인 메모제이션을 ..
좌표가 원의 범위안에 포함되어있는지 체크 2019. 11. 14. 원의 중심 좌표 X, Y와 반지름 R이 주어졌을 때 임의의 좌표 TX, TY가 원의 범위 안에 포함되어 있는지 찾아야 한다면 피타고라스 정리를 바탕으로 원의 반경을 계산할 수 있다. 반지름 제곱의 값이 (원의 중심 좌표 X - 임의의 좌표 TX)의 제곱 + (원의 중심 좌표 Y - 임의의 좌표 TY)의 제곱 값보다 크다면 임의의 좌표는 원의 범위에 포함되어 있다고 할 수 있다. (반지름^2) > (((원의 중심 좌표 X - 임의의 좌표 TX) ^ 2) + ((원의 중심 좌표 Y - 임의의 좌표 TY) ^ 2))) 이를 자바 코드로 표현하면 if (Math.pow(R, 2) > (Math.pow(X - TX, 2) + Math.pow(Y - TY, 2))) { 포함 = true; } 만약 원의 경계에 있는..
백준 10827 a^b Java 2019. 11. 1. BigInteger는 몇 번 써 봤지만 BigDecimal은 한 번도 안 써봐서 몰랐다가 그 존재를 알게해준 문제이다. 처음엔 double로 삽질하다가 BigDouble이 있을까 해서 쳐봤는데, 없었다. 덕분에 더 삽질을 했었다.. 아무튼 BigInteger같이 큰 수를 표현해주는 객체가 BigDecimal이라고 소수에도 있었다. 사용법은 BigInteger랑 비슷한데 다른 점이 있다. 소수를 표현하고 그것을 출력할 때 방식인데. 이 문제도 BigDecimal에 담아서 제곱한 값을 그대로 출력하면 어떠한 값에서는 지수형태로 출력을 하기 때문에 틀리게 된다. 예를 들어 예제 입력 2의 0.1 10을 입력하면 1E-10을 출력하면서 틀리게 된다. BigDecimal의 표현방식엔 3가지의 메소드가 있다. to..
백준 3055 탈출 Java 2019. 10. 24. 구현, 시뮬레이션에 약한 것 같아서 그쪽 관련 문제만 풀어보다가 오랜만에 풀어본 BFS문제이다. 시뮬레이션 분류에서 발견했지만 BFS를 오랜만에 사용해서 실수를 좀 많이했던 문제이다. 돌은 X 물은 * 비버굴은 D 고슴도치는 S 물과 고슴도치는 상, 하, 좌, 우로 움직일 수 있고 물은 돌과 비버굴을 지날 수 없고 고슴도치는 물과 돌을 지날 수 없다. 1분에 한 칸씩 물과 고슴도치가 움직인다고할 때 고슴도치가 비버굴에 몸을 피하는 최소 시간을 출력하면 되는 문제이다. 문제 설명에서도 알 수 있듯이 물이 먼저 움직이고 고슴도치가 움직이는 로직으로 구현해주면 해결되는 문제이다. 상, 하, 좌, 우로 움직이고 최소시간을 구하는 것이기 때문에 당연하게 BFS를 사용해서 해결했다. 고슴도치의 위치를 담을 큐와 물..
2020 KAKAO 자물쇠와 열쇠 Java 2019. 10. 17. 문제 3 정답률: 7.4% 문제3 풀러 가기 고고학자인 “튜브”는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다. 잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다. 자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 ..
백준 1918 후위 표기식 Java 2019. 9. 25. 중위 표기식을 후위 표기식으로 바꾸는 문제이다. 스택으로 후위 표기식을 계산하는 방법을 배운 적은 있어도 중위 표기식을 후위 표기식으로 바꾸는 알고리즘은 잘 모르고 있었다. 이 방법을 어떻게 구현하면 좋을까 고민해봤지만 생각해내기 어려웠다. 그러다 알게 된 알고리즘이 차량기지 알고리즘(Shunting-yardAlgorithm)이다. 차량기지 알고리즘은 중위 표기식을 후위 표기식으로 바꿔주는 알고리즘이다. 차량 기지 알고리즘은 스택에 문자열을 전부 넣는 방식이 아닌 연산자만 넣어주고 그 연산자들의 우선순위를 비교하여 출력해주는 방식이다. 1. 연산자가 아닌 경우엔 출력한다. 2. 연산자인 경우엔 스택에 넣어준다. 단 ')'는 넣지 않는다. 2번의 연산자인 경우에 스택에 넣어줄 때 조건이 있다. - ')'의..

티스토리툴바