프로그래민👨‍💻

Trie와 백트래킹을 이용한 시뮬레이션 문제이다. 이 문제를 맨처음 보았을 때 일종의 사전 개념인 처음 5개의 입력을 보고 Trie 알고리즘을 사용할 생각을 하였다. 그리고 map이 4x4로써 크지 않고, 주어진 시간도 10초로 충분하여서 백트래킹을 통해 만들어질수 있는 모든 단어에 대해 Trie search를 해주는 방식으로 접근하였다. 여러가지 알고리즘이 혼합되어 있는 형태이기때문에 작은 실수만 해도 어려워 질수 있었던 문제였다. Trie와 다른 알고리즘을 같이 사용해볼 수 있던 좋은 문제였던 것 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 ..

2020 카카오 문제였다. 이 문제는 옳은 괄호를 찾는 문제인데, 재귀를 이용해서 푸는 문제였다. 다만 이 문제에서는 재귀의 모든 과정을 문제에서 제공해주었고, 단순 구현만 하면 되는 문제였다. 따라서 문제의 제공되어있는데로 그대로 재귀를 구현하여 쉽게 풀 수 있었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 8..

2020 카카오 인턴 2번 문제였다. 수식의 연산자에 대해 우선순위를 부여하고 그순간에서의 최대값을 구하는 문제였다. 주어진 연산자가 3개였으므로 순열을 이용하여 모든 경우의 수를 보았다. 그리고 수식의 전부를 token화 시켜서 List의 형태로 저장하였고, 계산을 할땐 list에서 remove해주는 방식으로 해주었다. 여기서 주의할점은 for문안에서 List의 사이즈를 건들수 있는 remove연산을 해주었기 때문에 index값을 조정해주는 것이 꼭필요했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 ..

단순 시뮬레이션 문제이다. 문제에 주어진 조건처럼 단순히 모든 경우수를 체크하는 방식으로 풀어보았다. 다음과 같은 로직으로 해결해보았다. 1. 모든 도형은 3개의 연속블록을 가지므로 가로, 세로로 나누어 3개가 연속이 되는 블럭을 찾음 2. 그 블럭에서 튀어나온 블록 하나를 찾음 3. 튀어나온 블록과 동일선상에 있는 검정블록 2개에 대해 위에서 떨어트릴 수 있는지 체크 4. 가능하다면 답+1 위와 같은 로직이지만 코드는 좀 어지럽게 나왔다. 리팩토링을 해보아야겠다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 ..

문자열을 파싱하는 문제이다. 주어진 조건대로 단순히 문자열을 파싱해주는 문제이다. 일단 봐야하는 문자열 길이를 1부터 전체길이/2 를 해주었고, keep이라는 변수를 통해 현재까지 같은 누적을 계산하여 문자열의 길이를 구해주었다. 단순 구현 시뮬레이션 문제이므로 조건을 꼼꼼히 읽는 것이 중요한 문제였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 package programmers; public class Solution_2..

파싱을 요하는 시뮬레이션 문제이다. 이 문제에서 요점은 입력으로 들어오는 시간을 밀리초(ms) 로 변환시키는 것과 트래픽의 변화가 생기는 것은 시작점과 끝점이라는 것을 파악하는 것이다. 모든 밀리초 시간을 확인할수 없으므로 시작점과 끝점의 1초를 확인하는 방식으로 푼다면 O(n*n) 시간안에 해결할 수 있는 문제이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 ..

간단한 시뮬레이션 문제였다. 이 문제의 경우 for문을 이용한 간단한 문제였지만 최악의 경우가 200,000 * 500 이므로 일중 for문 안에 해결을 해야한느 문제였다. 정렬을 필요로 하는 문제였기에 priortyqueue를 사용하였고, Pos 클래스를 만들어 comprable을 상속받아 compareTo함수를 구현하였다. 이 문제에서는 주의할것이 있었다. 바로 0으로 나누는 경우인데, 보통의 경우 0으로 나누면 Exception뜨게 된다. 하지만 캐스팅을 한경우 별도의 Exception 없이 infinty나 NaN이 뜨게 된다. 항상 0으로 나누는 것은 예외처리를 다시한번 봐주는 습관을 길러야 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 2..

단순 구현으로 접근하였다. 우선 알파벳의 순위를 정해주는 order 배열을 통해 우선순위를 정해주었다. 그리고 알파벳을 방문한다면 visit 배열을 통해 방문체크를 해주었다. 만족하지 않는 경우는 2가지를 생각하였다. 첫째, 현재 알파벳보다 우선순위가 높은 알파벳인데 방문을 안했다면 거짓, 두번째, 현재 알파벳보다 우선순위가 낮은 알파벳인데 방문을 했다면 거짓. 이런식으로 접근하였다. 체크해야할 알파벳이 26개, 또한 문자열도 최대 26이므로 26*26 이 큰 숫자가 아니어서 단순히 접근하여 풀이를 하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 ..

시뮬레이션 문제이다. 주사위는 10번을 굴리고, 말은 4개를 가지고 있으므로 전체 경우의 수는 4^10을 가지게 된다. 따라서 이 문제는 백트래킹을 통한 완전탐색을 할 수 있는 문제이다. 다만 주의할점은 윷놀이판을 2차원 배열의 형태로 바꿔주는 것과 각 교차점에서 분기를 해주는 것이 중요하다. 또한 교차점의 값이 두번 안들어가도록 체크해주는 것도 중요하다. 그리고 백트래킹을 하는 과정에서 현재 점을 되돌려 놓는 것과 방문체크를 되될려 놓는 것이 포인트이다. 문제에 주어진 그대로 구현만하면 되는 시뮬레이션 문제였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39..

DFS를 이용하여 풀수 있는 문제이다. 일단 문제에서 10번이하로 움직인다는 조건을 주었다. 조건을 가지고 생각해보았을때 현재 구슬을 굴릴수 있는 방향은 4방향이 있고 10번을 굴린다 생각하면 전체가지수는 4^10이 나오게 된다. 4^10은 1,048,576‬ 로써 충분히 완전탐색을 할수 있는 시간이 나온다. 하지만 좀더 최적화가 가능하기에 생각을 해보았다. 맨처음 구슬을 굴릴땐 4방향 다 굴릴수 있지만 그다음부턴 2방향으로만 굴릴수있다. 예를 들어 맨처음 위쪽으로 굴렸다 가정해보자면, 구슬은 벽을 맞닿을때까지 구르기 때문에 다음번엔 위쪽으로 굴리는 것은 무의미한 경우를 가지게 된다. 또한, 반대방향이 아래쪽으로 굴리는 경우는 다시 그 전 상태로 되돌아가기 때문에 그것 또한 무의마하게 된다. 그래서 결론..