본문 바로가기

Programming/알고리즘

 (11)
[프로그래머스] 풍선 터트리기 Lv.3 코딩테스트 연습 - 풍선 터트리기 [-16,27,65,-2,58,-92,-71,-68,-61,-33] 6 programmers.co.kr 알고리즘 공부를 본격적으로 시작한지 3개월이 되어가는 오늘, 실력이 점차 늘어간다는 느낌을 받는다. 월간 코드 챌린지에 도전하면서 세번째 문제였던 풍선 터트리기 문제에서 끝까지 66.7점을 받고 결국 2.6솔을 하고 끝났었다. 해당 문제가 프로그래머스에 업데이트 된 1일 후 오늘 다시 도전하였고, 효율성을 올려서 결국 100점을 받았다. 첫번째 시도 처음에는 임의의 위치를 기준으로 왼쪽 그룹과 오른쪽 그룹으로 나눈 후, 각각의 그룹에 있는 원소들과 기준 위치 값을 비교하여 만약 기준 위치 값 보다 작은 값이 그룹에 있을 때, count를 늘리는 식으로 코드를 짰었다. ..
[java] 입력받은 문자열 처리하는 다양한 방법 입력으로 문자열 str 이 주어질 때, 이를 편리하게 이용할 수 있도록 변환하는 여러가지 방법이 있다. 1. toCharArray() 사용하여 문자열을 문자 배열로 변환 // string 을 문자 배열로 변환 char[] ch = str.toCharArray(); // 문자열로 반환 return new String(ch); // 1 return String.valueOf(ch); // 2 2. StringBuilder 사용하여 append, setCharAt 메소드 등 이용 StringBuilder sb = new StringBuilder(str); for(int i=0;i
[LeetCode/리트코드] 3Sum leetcode 의 3sum 문제는 많은 깨달음을 얻게 한 문제 중 하나이다. 처음에 문제를 보자마자 투포인터 방법으로 풀면 된다고 느꼈지만, 사실 투포인터 문제를 직접 풀어본적이 없었고 그래서 hashset 으로 접근을 하였다. 그런데, hashset 으로 접근을 하게 되면, 결국 완전탐색으로 모든 수를 탐색하면서 중복을 제거해나가는 방식이 되기 때문에 효율성이 떨어진다. 또한 처음에 hashset으로 풀이를 했을 때 얕은복사를 하는 바람에 마지막에 listIn.clear() 를 하면서 출력 리스트에 있는 값이 덩달아 날아가게 되는 문제도 겪었다. 마치 DFS 문제를 풀 때, 재귀호출하는 부분에서 값의 변형이 일어난 후에 재귀호출을 하면 출력이 이상하게 나오는 것과 비슷하다는 느낌을 받았다. 예전 어떤..
[알고리즘] 그리디(greedy) + 힙(heap) 을 같이 써보자 코딩테스트 연습 - 라면공장 라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니�� programmers.co.kr 이 문제는 이틀에 걸쳐서 4가지 방법으로 푼 문제이다. (사실 힙으로 한번에 풀고 재미삼아 다른방법으로도 풀어봤다) 1. 전체탐색 1-1. DFS - 재미삼아 이렇게 풀어봤다가 4시간동안 삽질끝에 결국 풀었지만, 효율성에서 영혼까지 털렸다. 2. 그리디 2-1. getMax 를 이용한 풀이 2-2. Collections.sort 를 이용한 풀이 2-3. 우선순위 큐를 이용한 풀이 역시 가장 효율성이 높은 방법은 4번째 방법이다. 그 이유는 현재 stock 으로..
[알고리즘] 우선순위큐(힙)는 왜, 언제 사용해야 할까 언제, 왜 우선순위 큐를 사용해야 하는가? 문제를 풀 때, 원소를 삽입 또는 삭제 후 매번 정렬을 해야하는 문제가 있다. 이럴 때에는 Collections.sort 와 같은 퀵정렬을 이용하게 되면 시간복잡도가 nlogn 이다. 이때 원소의 개수가 1e6 이상인 경우에 퀵정렬 시간복잡도는 1e8 을 넘어갈 수 있게 된다. 따라서 이때에는 우선순위 큐를 활용하여야 원소를 삽입 또는 삭제할 때 마다 nlogn 이 아닌, logn 의 시간복잡도로 정렬할 수 있게된다. 적용 가장 대표적인 문제는 프로그래머스의 '더 맵게' 문제이다. https://programmers.co.kr/learn/courses/30/lessons/42626?language=java 풀이1 위 코드는 내장 sort 를 이용하여 원소를 삭제..
[코테준비] 전체탐색으로 문제를 해결하자 - 1 들어가기에 앞서 단순히 문제를 많이 풀고 이를 통해 얻어진 내공으로 직관적으로 문제를 푸는 것은 한계가 있다. 알고리즘을 본격적으로 공부한지 7일차가 되는 오늘 내가 느낀 것은 바로 이것이다. '알고리즘은 수학문제 풀이와 사고과정이 비슷하다' 특히 수능 30번,21번 문제를 푸는 사고과정과 닮아있음을 체감하였다. 여담이지만, 알고리즘(코딩테스트) 은 '정시' 와 닮았고 포트폴리오(프로젝트)는 '수시 스펙'과 닮은 것 같다. 전체탐색으로 문제를 풀어보자 시뮬레이션 보통 시뮬레이션 문제는 특징이 다음과 같다. 문제에서 주어진 처리를 수행하기만 하면 되는 간단한 내용이 주를 이룬다 "이런 과정을 거쳐서 나온 결과가 무엇인가?" 라고 물어보는 문제가 많다. 전체탐색 vs 시뮬레이션 시뮬레이션 : 수행해야 하는 ..
[코테준비] PS를 하다가 오는 좌절감, 어떻게 극복할 것인가 프로그래머스 > 해시 > 베스트엘범 일단 자바 컬렉션에 대한 개념이 현저히 부족하였다. 큰 그림을 세워나가는데 너무나 큰 장애물이었다. 차라리 잘 모르는 것을 인정하고 일단 수학적으로 풀이방식을 설계하며 문제의 전체해결흐름을 이해했으면 좋았었는데.. 멘붕상태가 와서 늪에 빠지기 시작하면서 전체적인 사고를 하지 못했다. 나는 처음에 문제를 보고 일단 좀 복잡하다는 느낌을 받았다. 단순히 하나의 hashmap 으로는 문제를 풀 수 없다는 것을 직감했다. 사실 이 문제를 오후에 풀고 지금은 밤이라서 자세히 기억은 나지 않지만 그때 그 당시의 기억을 생각나는 대로 적으려 한다. 큰 그림 1. , 이 두개를 hashmap 으로 만들어야한다. 2. 특정장르를 가지는 index의 값을 얻어야 한다. 이때, 장르의 이..
[코테준비] 입문자를 위한 알고리즘 해결전략 - 3 프로그래머스 > 해시 > 위장 큰 그림 이것저것 문제 해결을 위해서 스케치를 해보다가 다시 문제의 발문을 보았다. 문제의 발문에서, "최소한 한 개의 옷을 입어야 한다"라는 조건을 보고 여사건으로 풀까? 라는 생각이 들었다. 그래서 이참에 수학적으로 알고리즘을 해결하기로 마음먹었다. 그러고 나서 고민했던 것은 다음과 같다 1. clothes [][] 배열을 hashmap으로 변환하자 - 어떻게 변환할 것인가? 2. 이차원 배열 length를 구해서 각 품목의 개수를 세야 한다 - 어떻게 셀 것인가? 3. 수학의 여집합(여사건) 개념을 사용하여 각 품목의 개수를 각각 곱한 후 -1을 해준다. (귀납적으로 수학적 증명을 했기에 시도할 수 있었음). 여기서 -1을 하는 이유는 아무 옷도 입지 않는 경우를 제외..

티스토리툴바