Algorithm

출처https://school.programmers.co.kr/learn/courses/30/lessons/214289 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 이 문제는 에어컨을 적절하게 끄고 키며, 켜져있을때는 희망온도를 유지하거나 조절할 수 있는데 이때 전력 소비가 최소가 되도록 하는 문제이다. 다만 손님이 타있을 경우엔 적정온도를 항상 유지해야 한다.풀이이 문제는 DP를 활용해서 상태를 지속적으로 기록해주며 풀어야 하는 문제이다. 이 문제에서 우리는 경우를 아래와 같이 나눌 수 있다. 손님이 타고있는 경우, 적정온도를 유지할 수 없는 경우는 살펴보지 않는다에어컨을 튼 경우지금 온도를 ..

출처https://school.programmers.co.kr/learn/courses/30/lessons/12942 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제이 문제는 DP를 이용하여 모든 행렬을 곱하기 위한 최소 곱셈 연산의 수를 구하는 문제이다. 풀이이 문제는 DP를 이용하여 해결하는 문제이다. 연쇄행렬 최소곱셈 알고리즘 (Matrix chain multiplication)이라고 부르는 알고리즘을 사용하였다.아래 블로그를 참고하여 문제를 해결하였다.https://source-sc.tistory.com/24 [1][연쇄행렬 최소곱셈 알고리즘] (Matrix chain multiplicati..

출처https://school.programmers.co.kr/learn/courses/30/lessons/60062 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 이 문제는 원형 모양의 레스토랑의 취약점을 점검 할때, 친구가 한시간동안 이동할 수 있는 거리는 각각 다르고 이 친구들을 적절히 보내 모든 취약점을 할 때 보내야 하는 친구의 최솟값을 구하는 문제이다. 만약 모두 점검할 수 없다면, -1을 리턴한다.풀이뭔가 처음부터 많이 헤맸던 문제이다. 단순히 취약점의 순열을 구하여 거리가 높은 친구를 순서대로 배치하는 방법을 생각했는데, 반례가 중간에 떠올라 처음부터 다시 풀게 되었던 문제이다. 결..

출처https://school.programmers.co.kr/learn/courses/30/lessons/1836# 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 요약하자면, 직선으로 연결 또는 1번 이하로 방향이 꺾인 선으로 연결하면 카드는 제거되며, 이 작업을 반복하였을때 모든 카드가 제거되는지, 제거된다면 제거된 카드의 순서를 구하는 문제이다.직선은 다른 카드 위를 지나가거나 벽을 지나갈 수 없으며, 방향을 꺾을 시에는 단 1회만이 허용된다.풀이문제에서 제시한 조건을 그대로 구현하여 실행하는 시뮬레이션, 한마디로 그냥 구현 문제에 가깝다. 먼저 사전작업으로 아래와 같은 방식을 사용하였다.S..

출처https://school.programmers.co.kr/learn/courses/30/lessons/72415 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 이 문제는 짝이 맞는 카드를 뒤집어 모두 없어질때 까지 반복하는데, 가장 최소로 조작했을때의 횟수를 구하는 문제이다. 풀이이 문제는 어떤 카드를 먼저 뒤집어야 최소의 횟수가 되는지 알 수 없기 때문에 모든 순서에 대해 탐색을 진행하여야 한다. 따라서 DFS를 이용하여 순열을 만들어 완전 탐색을 진행한다. 또한 카드를 맞추기 위해 해당 카드로 이동하는 최단 경로를 구하기 위해 BFS도 사용하였다. DFS(현재 커서의 위치, 현재 dept..

출처https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4yLUiKDUoDFAUx SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 문제 한개의 메모리를 가지고, 주어진 명령 집합을 돌아다니면서 명령을 수행할 때 이 프로그램이 끝나는지, 끝나지 않고 무한히 실행하는지 판별하는 문제이다. 풀이이 문제에서 핵심은 어떻게 무한히 실행되는지를 판별하는 것이라고 생각한다. 단순히 2차원 배열로 방문 여부를 따지기에는 방향을 바꾸어 그냥 한번 지나칠 수 도 있고, 지나칠때 메모리의 값이나 방향이 다르면 다 다르기 때문에 불가능 하다. 따라..

출처https://www.acmicpc.net/problem/1039 문제  주어진 수에서 두가지 숫자를 골라 주어진 횟수만큼 바꾸는 연산을 하여, 얻을 수 있는 최대 값을 구하는 문제이다.풀이처음엔 무조건 그리디로 접근해야하나 라는 생각이 들었는데, 생각해보면 K번 교환을 하는 도중에 구해진 최대값이 아니고, 정확히 K번 교환했을때 구한 값중 최대값을 구해야 하기 때문에, 모든 경우의 수를 확인하는 완전탐색(Brute-Force)으로 문제를 해결하였다. BFS를 활용하여 모든 교환을 진행한 경우를 만들어 내 문제를 해결할 수 있었다. visited 배열을 통해 방문여부를 활용하여 DFS로도 해결할 수 있었다.코드 - BFSimport java.util.*;import java.io.*;class Mai..

출처https://school.programmers.co.kr/learn/courses/30/lessons/81303 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  문제 이 문제는 n개의 노드가 연결된 링크드 리스트에서, 주어진 명령어들을 처리하여 선택/삭제/복구의 과정을 거쳐 리스트의 상태를 업데이트하고, 마지막 상태를 출력하는 문제입니다. 풀이커서가 돌아다니면서, 표 중간에 있는 데이터를 삭제하거나 복구 시 다시 끼워넣어야 하는 문제입니다. 가장 먼저 떠올릴 수 있는 자료 구조는 바로 연결리스트(Linked List)였습니다. 연결 리스트는 앞 뒤 노드에 대한 정보를 가지고 있기 때문에, 삭제와 ..