Algorithm/프로그래머스18 프로그래머스 - 표현 가능한 이진트리 필요지식 이진트리 트리순회 문제 설명 해당 수를 이진트리로 표현할 수 있으면 1 없으면 0을 출력하는 문제이다. 주어진 문제 예시를 보면 주어진 이진트리에 더미노드를 추가하여 포화 이진트리를 형성한다. 즉, 이 것을 이용해 이진트리로 만들 수 있는지 없는지를 판별하면 된다. 문제에는 포화이진트리를 만들수 있는지 없는지 이렇게 물어보지 않고 있다. numbers 에 주어진 순서대로 하나의 이진트리로 해당 수를 표현할 수 있다면 1을, 표현할 수 없다면 0 이진트리에 속해있는 것이 포화이진트리이다. - 이진트리는 자식노드가 최대 2개인 트리이다. - 포화이진트리는 이진트리이면서 모든 레벨이 노드로 꽉 차 있어야 한다. 그렇기 때문에 이 문제는 해당 수를 이진수로 표현하고 포화이진트리로 형태로 만들면서 이것이.. Algorithm/프로그래머스 2023. 4. 11. 프로그래머스 - 택배배달과수거 문제 설명 최소한의 이동거리로 배달과 수거를 모두 마치는 거리를 구하는 문제이다. 최대길이가 10만이다. 단순히 구현하는 문제인데, 구현을 해나가는 과정이 쉽지않다. 그래서 나는 이렇게 시도해봤다. 배달 또는 수거할 제일 먼곳을 찾는데, 먼곳을 가는 과정에서 배달할 물건을 내려놓는다고 생각했다. 그리고 끝지점에서 다시 물건을 실으러 오면서 회수할 물건을 최대 담아내는 탐욕법을 이용했다. 풀이 public long solution(int cap, int n, int[] deliveries, int[] pickups) { TreeMap d = new TreeMap(); for (int i = 0; i < n; i++) { if( deliveries[i] ==0 ) continue; d.put(i + 1, d.. Algorithm/프로그래머스 2023. 4. 9. 프로그래머스 - 행렬과 연산 문제 설명 행렬이 주어진다. 주어진 연산에 의해 행렬이 이동하고 난 후 결과를 출력하는 단순한 문제이다. 하지만 이문제는 효율성 측정되는 문제라 최적화를 생각해야한다. shiftRow, rotate 두가지 명령만이 존재한다. 일반적인 시뮬레이션으로 구현하면 shiftrow는 최대 n *m 번의 연산이 필요하고 rotate는 n+m-2번이 필요하다. 그리고 명령어는 최대 10만이라 정확성은 통과할지라도 효율성은 당연히 실패한다. 최적화하기에 시도했던 방법은 연산의 일부를 합치면 최적화가 가능한가 그려봤다. 하지만 나오지 않았다. 2022 테크 여름인턴십 코딩테스트 해설 해당 내용을 참고하였더니 자료구조의 쓰임을 잘 알고있는지 체크하는 문제였다. 각각을 단순한 시물레이션이아닌 자료구조의 최적화를 유도했던 문.. Algorithm/프로그래머스 2023. 4. 8. 프로그래머스 - 알고리즘 공부 문제 설명 모든 문제를 풀수 있도록 알고력과 코딩력을 얻는데 걸리는 최소 시간을 구하는 문제이다. 주의사항 배열의 인덱스 범위 설정 최고 가질 수 있는 알고력과 코딩력은 최대 150이다. 그런데 내가 문제를 풀 때 150이상의 알고력 또는 코딩력을 얻을 수 있음을 유의해야 한다. 배열을 더 크게 잡거나 혹은 배열 범위를 넘어갈때 안쪽으로 다시 조절해줘야 한다. 다익스트라 풀이 주의사항 아마 효율성 부분을 통과할 수 없을 수 있다. 이부분은 우선순위 큐에 있는 쓸데없는 데이터들이 많아서 그런것일 수 있다. 하지만 또다른 에외도 존재한다. 정제를 안해줘서 가 아니라 코드가 좀 길어서 시간초과가 난다.. 스타일 차이인데 왜 시간초과가 나는지 모르겠다.. TRY 다이나믹 2022 테크 여름인턴십 코딩테스트 해설.. Algorithm/프로그래머스 2023. 4. 6. 프로그래머스 - 등산 코스 정하기 문제 설명 n개의 등산지점이 있다. 출발지점으로 부터 목적지 지점까지 , 목적지점으로부터 출발지점까지 최소 인텐시티를 등상코스를 정하라 인텐시티란 거쳐가는 최대 간선 비용이다. 생각한 아이디어 인텐시티를 짧게 하려면 짧은 코스트를 가진 방향 리스트로 부터 구할 수 있다고 생각했다. 하지만 일반적인 다익스트라는 한 지점으로부터 다른지점의 최소 거리를 구하는 것이다. 조금 변형하여 최소거리가 아닌 최소 인텐시티 테이블을 두고 구하면 어떨까라는 아이디어는 해설을 참조하여 발견했다. 주의사항 간선의 정보를 저장하는 구조를 잘만들어야 한다. 봉우리는 단 한번만 지나야 하는 규칙이 존재한다. 다른 출입구는 거칠 수 없어야 한다. 이런 경우가 있을 수 있다 봉우리가 가장 작은 간선비용을 가져서 한번더 지날 수 있기 .. Algorithm/프로그래머스 2023. 4. 6. 이전 1 2 3 4 다음
