본문 바로가기

알고리즘 풀이

[프로그래머스] Lv2 요격시스템 java 쉬운 풀이 1. 문제 설명 📌문제 설명문제 설명 생략2. 접근 방식 🗃️KEY WORD: GREEDY ALGORITHMGreedy 알고리즘은 매 선택의 순간에 당시 할 수 있는 최선의 선택을 하는 것이 전체 문제에서도 최적의 해를 구하는 것임을 가정하는 알고리즘이다.여기서는 미사일의 묶음을 끝지점 기준 오름 차순으로 정렬하고, 미사일 묶음의 최대한 끝지점에서 차례대로 요격해 나가면 최소한으로 요격 미사일을 사용하는 것이다. 해당 방법은 다음과 같은 이유로 유효하다.미사일을 만나면 무조건 요격해야 한다. 안하고 지나치는 경우는 없다.따라서 미사일을 만나면 최대한 겹치게 삭제해야 한다.하나의 미사일 묶음 A가 다른 미사일 묶음과 최대한 겹치는 경우는 A의 끝지점에서만 발생한다.예를 들어보겠다.다음과 같이 폭격 미사.. 더보기
[백준] 1541 잃어버린 괄호 1. 문제 설명 📌문제링크2. 접근 방식 🗃️KEY WORD: GREEDY ALGORITHMGreedy Algorithm은 매 선택의 순간마다 당시 최선의 선택을 하는 것이 전체 문제에서 봤을 때 최선이라는 가정을 하는 알고리즘이다. 해당 문제는 -를 만난 순간부터 뒤에는 무조건 괄호를 활용해 모든 값을 -로 만들어버리면 된다. 최초 -를 만난 후 뒤의 계산에 +가 오든 -가 오든 적절히 괄호만 치면 모든 값을 -로 만들 수 있다. 예를 들어 25 + 32 - 26 - 27 + 28 - 29 + 30 - 3125 + 32 - 26 - (27 + 28) - (29 + 30) - 31처럼 말이다. 3. 코드 소개 🔎(0) 사전 지식문제의 입력이 String으로 뭉뚱그려 주어지기 때문에 문자열 자르기에 .. 더보기
[백준] 1931 회의실 배정 쉬운 풀이 ^^ 1. 문제 설명 📌문제 링크회의시간의 시작과 끝이 주어질 때, 최대한 많은 강의를 회의실에 배정해라 (A 강의의 끝시간과 B 강의의 시작 시간이 같으면 연달아 배정할 수 있는 것으로 간주한다.) 2. 접근 방식 🗃️KEY WORDS: GREEDY ALGORITHMGreedy Algorithm은 선택의 순간에 최적의 선택지를 고르는 것이 전체 문제에서 최적의 선택을 하는 것이라 가정하는 알고리즘이다.빨리 끝나는 순으로 회의를 정렬제일 빨리 끝나는 회의가 A라면 A 회의 이후에 시작할 수 있으면서도, 최대한 빨리 끝나는 회의를 선택하는 것이 전체 문제에서 봤을 때 최대한 많은 강의를 고를 수 있는 방법임.2번을 모든 회의를 돌아보며 더 이상 고를 수 있는 회의가 없을 때까지 반복 3. 코드 소개 🔎.. 더보기
[백준] 1744 수 묶기 java 쉬운 풀이^^ 1. 문제 설명 📌문제 링크문제에서 수열이 주어지는데, 수열은 기본적으로 모두 더해진다. 하지만 만약 사용자가 임의의 수 2개를 골라서 괄호를 쳤을 경우, 해당 수는 곱해진다. 모든 수는 단 하나의 괄호에 포함되거나 아니면 괄호에 아예 포함되지 않는 2가지 선택지밖에 없다고 했을 때, 수열로 만들 수 있는 최대값을 구하라.예를 들어 수열이 [0,1,2,4,3,5]로 주어졌을 때, 괄호가 없다면 합은 15이지만, 다음과 같이 괄호를 활용하면 0 + 1 + (2*3) + (4*5) 가 되면 값이 27로 최대가 된다.2. 접근 방식 🗃️KEYWORD: GREEDY ALGORITHM(1) 경우의 수 생각하기먼저 주어진 두 개의 수로 최대값을 만들 수 있는 경우는 무엇이 있을까?두 수 모두 0보다 클 때: 이.. 더보기
[프로그래머스] Lv2 석유 시추 Java 쉬운 풀이🥰 1. 문제 설명 📌문제 링크문제 내용이 직관적이기 때문에 부가 설명은 생략하겠다.2. 접근 방식 🗃️KEY WORD: BFSoils라는 1차원 배열을 만든다. 해당 배열의 index 는 land의 열이고, value는 열 당 얻을 수 있는 석유의 양이다.land 전체에 대해서 이중 반복문으로 석유(1)이 있는 위치를 찾는다만약 석유를 찾는다면 해당 위치부터해서 연결된 석유 덩어리를 BFS로 찾는다.BFS로 해당 위치에서 시작해 석유 덩어리를 모두 찾았으면, 지금까지 거친 적 있는 열에 지금까지 찾은 석유량을 더한다.(예를 들어, 열을 1,2,3 거쳤고, 찾은 석유량이 7이면 oils[1] += 7, oils[2] += 7, oils[3] += 7 이 된다.)3. 코드 소개 🔎먼저 전체 코드를 보여주.. 더보기
[프로그래머스] Lv2 막대와 그래프 접근 힌트부터 세세한 코드 분석까지! JAVA 1. 문제 설명 📌문제 링크문제에서는 다음 3가지 단방향 그래프를 제시하고 있다.도넛형은 순환형 그래프이고, 간선의 개수와 정점의 개수가 같다.막대형은 비순환형 그래프이고, 정점의 개수 - 간선의 개수 = 1 이다.팔자형은 순환형 그래프이고, 간선의 개수 - 정점의 개수= 1 이다.이러한 3가지 유형에 해당하는 그래프가 최소 2개 이상 주어진다. 이때 주어진 모든 그래프를 잇는 정점을 하나 그린다. 우리는 이번 문제 풀이에서 해당 정점을 뿌리 정점이라 부르겠다. (문제에서 마땅히 해당 정점을 지칭하는 용어가 없어서 임의로 명명하겠다.) 뿌리 정점을 부착한 예시는 다음과 같다.이때 뿌리정점의 번호, 도넛형 그래프의 수, 막대 그래프의 수, 팔자형 그래프의 수 를 순서대로 기록한 1차원 배열을 출력하면 된.. 더보기
[프로그래머스]Lv3 합승 택시 요금 java 접근 방식부터 코드 분석까지 1. 문제 설명 📌문제 링크무지랑 어피치랑 야근을 끝내고, 집에 갈려고함.버스가 끊겨서 택시를 타야 하는데, 택시 요금이 걱정됨.마침 무지랑 어피치가 집 가는 방향이 같은 쪽이라, 최대한 합승해서 전체 택시 비용을 줄이려고 함. 다만 합승하지 않고 가는게 전체 택시 비용이 더 작을 경우, 그 경우의 수를 선택함.회사 위치 : s, 무지 집: a, 어피치 집: b 의 위치가 주어진다고 치자.어피치와 무지의 택시 요금을 전부 합쳤을 때, 최소 택시 요금을 반환하라.힌트만 얻고 가실 분들은 접근 방식까지만 보고 가시길 바라고, 풀이법을 보실 분들은 끝까지 읽어주시라2. 접근 방식 🗃️KEY WORD: 다익스트라해당 문제가 다익스트라인 것을 알아채기는 쉽지만 거기에 더해 아이디어가 필요하다. 왜냐하면 그저 .. 더보기

티스토리툴바