본문 바로가기

Algorithm

[동적 계획법] 도둑질 - Java 코드
2021. 8. 2. https://programmers.co.kr/learn/courses/30/lessons/42897 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 programmers.co.kr 문제 이해 원형의 구조를 가지기 떄문에 첫번째집을 털면 마지막집을 털수없고, 두번째 집부터 털어야 마지막까지 비교가 가능해진다. 그러므로 두 가지 Case를 나눠서 순회하여 최댓값을 구하고, 두 경우 중 큰값을 반환해주면 된다. 중요한건 DP를 사용해야하므로, 두번의 케이스의 메모이제이션을 위해 Array를 만들어야한다. (두번 돌려면 원본을 훼손하면 안되니깐....
[동적 계획법] 등굣길 - Java코드 ★★★ (설계가 어려움)
2021. 8. 2. https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 문제 설계 오른쪽, 아래로만 움직이면서 침수된 판을 제외하고 지나갈수 있는 경로중 최소값 경로의 갯수를 구하는 문제이다. 최단 경로를 구하라 했지만, 사실 어떻게 가도 경로값은 같을수 밖에 없다;; 포인트 경로를 구하는 법은 내머리로 나오지 않았고 한 블로그를 참고했다 M,N의 이차원배열을 선언하고, 경로값을 초기화해주되, 범람지역은 0으로 생각하고 ..
[동적 계획법] 정수 삼각형 - Java코드
2021. 8. 2. https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 문제 풀이 아래에서 부터 순회하면서, 상위노드에 값을 더해주면서 메모이제이션 한다. class Solution { public int solution(int[][] triangle) { for(int i=triangle.length-2;i>=0;i--) { for(int j=0;j
[동적계획법] N으로 표현 - Java 코드 ★★★(★★)
2021. 8. 2. https://programmers.co.kr/learn/courses/30/lessons/42895?language=java 코딩테스트 연습 - N으로 표현 programmers.co.kr 문제 이해 DP는 메모이제이션이 필요하다. 해당 문제에서 이전단계에 대한 메모이제이션을 위해서는 각각의 N을 사용하여 만들어지는 모든 경우의 수를 만들어 저장하고, 그렇게 저장한 이전의 경우들을 바탕으로 이후에 단계를 만들어가는 풀이가 필요하다. 풀이 메모이제이션을 위해 Set배열을 만들어서 푼 풀이이다. 각각의 Set 배열에는 연산의 숫자로 만들어질 수 있는 모든 값들을 저장한다. 이후에 Set 배열의 낮은 인덱스에서부터 만들고자했던 목표값 number가 있는지 검사해주면, 최솟값 연산을 반환 할 수 있다. imp..
[그리디] 단속카메라 - Java코드 (프로그래머스 버그존재)
2021. 7. 30. https://programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 문제 항상 느끼는건데 문제가 참 상냥하지 못함. + 이번에는 문제 설명에 이상한점이 있음, 입출력의 설명 부분에서 -5, -15 지점을 지난다는 말은 틀린말이 아니지만, 사람들에게 혼동을 줄 수 있는 말들임 로직상 통과하는 부분에 카메라를 설치해주어야 최소값을 찾을수 있을것으로 보인다. 올바른 로직으로 구현했을때 카메라는 제일 먼저 빠져나가는 3번 차량의 -13에서 카메라가 설치되어 1번, 2번 을 같이 찍고, 그외에 포함되지않는 4번차량의 범위내에 한번더 설치되어 ..
[그리디] 섬 연결하기 - Java코드 ★★★ (크루스칼, 신장트리)
2021. 7. 29. https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 문제 설계 일단 최속밧을 찾기위해서는 Costs로 오름차순 정렬은 필수이다. Costs가 1이거나 작다고 해서 불필요하게 무작정 연결해서는 안된다. 모든섬 하나 이상의 선이 연결되어도 전체 통행에 대한 연결이 안됬을 수 있다. 선이 이어지는지 여부를 체크하기위한 부분이 필요하다. 이 문제는 신장 트리 구조를 알고 트루스칼 알고리즘을 사용해야하는 문제이다. 트루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하는 알고리즘이다. 연결해야 하는 노드수만큼의 배열..
[그리디] 구명보트 - Java코드 ★★
2021. 7. 29. https://programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 문제 설계 정렬된 자료에서 몸무게가 높은 순서로 뽑으면서 Count하되, 제일작은 사람과의 합이 limit을 넘지않으면 같이 뽑을 수 있도록, Deque 자료구조를 활용하여, 정렬된 자료에서 앞뒤로 poll()을 해주도록 하였다 풀이 public static int solution(int[] people, int limit) { int..
[그리디] 큰 수 만들기 - Java코드 ★★★
2021. 7. 28. https://programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr https://hsin.hr/coci/archive/2011_2012/ Croatian Open Competition in Informatics hsin.hr 문제 출처이자 다양한 테스트케이스를 볼 수 있음 (4번의 테스트 다운후, kerk 폴더내 in, out 파일 참고) 문제 나의 접근법 (오답) number 문자열안에 가장 큰수인 9 ~ 0까지 순서대로 반복문을 돌면서, 해당수를 문자열 내에 큰수를 가장 먼저 만나는 부분에서 문자열을 잘라서, 가장 작은숫자부터 차례차례 제거하는 연산을 해서 반복해서 답을 구하려했지만, 테스트케이스 3..
[그리디] 조이스틱- Java코드 ★★★
2021. 7. 27. https://programmers.co.kr/learn/courses/30/lessons/42860 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr 문제 이해 문제 설명이 조금어렵다. 이해가 중요하다. AAA 시작해서 위아래로 알파벳이동은 하나씩 움직인다. 그리고 또다른 움직임인 커서이동이 있다. 커서이동은 문자열에 자리 이동이다. 첫번째 문자를 목표하는 값으로 셋팅하였으면, 다음 두번째 문자로 이동할 수 있다. 그런데 문제에서는 다음 두번째 문자는 이미 A이므로 좌측이동이아닌 우측이동으로 맨끝지점으로 한번에..
[그리디] 체육복 - Java코드
2021. 7. 27. https://programmers.co.kr/learn/courses/30/lessons/42862?language=java 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr 문제 접근법 전체사람 중, 잃어버린 사람을 제외하고, 그들중, 빌릴 수 있는 경우마다 count해서 정답을 반환해주어야겠다. 나는 리스트를 이용하면 빌려준 사람들의 요소를 삭제할수있기 때문에 좋을것같다는 바보같은 생각을 했다. 포인트 예제에는 존재하지 않지만, 잃어버린 사람들중 여벌을 가지고 있을수 있다. 그런 경우를 대비하여, 잃어버린 ..
[완전탐색] 카펫 - Java 풀이
2021. 7. 27. https://programmers.co.kr/learn/courses/30/lessons/42842 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 programmers.co.kr 문제 접근법 들어온 두 값의 합이 카펫의 수이고, 카펫수를 인수분해하여 경우의 수를 검사하여 가로세로 크기를 맞춰야 한다. 풀이 public static int[] solution(int brown, int yellow) { int[] answer = {0,0}; int sum = brown+yellow; for(int x=2; x
[완전탐색] 소수찾기 - Java 풀이, 순열 포인트,★★
2021. 7. 27. https://programmers.co.kr/learn/courses/30/lessons/42839?language=java 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 문제 접근법 이것은 순열이 필요해 보인다. 모든 경우에 수로 순열로 만들고, 중복을 제거 해야 한다. (HashSet에 담으면 해결될것 같음) 중복 제거된 리스트에서 소수를 찾아서 count 해주면 끝! 포인트 1. 순열을 만드는 메소드의 구현 (그동안 순열 조합 코드를 안해봐서 이번기회에 외울 예정) 2. 소수검사는 아리..
[완전탐색] 모의고사 - Java 풀이
2021. 7. 27. https://programmers.co.kr/learn/courses/30/lessons/42840 코딩테스트 연습 - 모의고사 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 programmers.co.kr 문제 접근법 완전탐색, 브루트포스는 결국 모든 경우에 수를 따져야하는 알고리즘이이다. 풀기 위해서는 무식해보이는 코딩을 할 수 밖에 없다. 1. 학생별로 반복되는 패턴을 배열에 담아서 맞춘수를 카운트해주고, 2. 맞춘수 중에서 Math.max를 이용해 최댓값을 구해, 제일 많이 맞춘 학생들을 추려내서 배열에 넣어준다. 3. 배열은 크기를 지정해야하는 특성상 정답..
[정렬] H-Index - Java 풀이
2021. 7. 24. https://programmers.co.kr/learn/courses/30/lessons/42747 코딩테스트 연습 - H-Index H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표 programmers.co.kr 문제 접근 H-Index는 발표한 N개의 논문중 h이상 인용된 논문이 h이상이여야 하므로, 해의 범위가 0 ~ N 이다. 나는 역순정렬후 H-index를 N부터 0까지로 순회하면서 H-index 이상 인용된 논문이 H개 이상인지를 확인후 루프를 탈출하도록 구현해보았다. 풀이 import java.util.Arrays; import..
[정렬] 가장 큰 수 - Java 풀이
2021. 7. 24. 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 접근법 Comparator를 어떻게 잘 사용해야 값들을 서로 잘 비교하면서 정렬해줄수 있을까 고민하였다. 이 문제는 주어진 배열의 숫자를 문자열로 형변환후 서로 값들을 붙여서 비교후 내림차순 정렬하여 그 값들을 모두 붙여 문자열을 반환하는 문제이다. 방법 1. 서로의 값을 붙여 비교하기 위해 반드시 int array -> String Array 형변환 2. Comparator 를 이용해 정렬방식 재정의 + 마지막 반환시, 0,0,0,0... 과 같이 0 값들로만 들어 왔을 때, 0으로 반환 (TestCa..
[정렬] K번째 수 - Java 풀이
2021. 7. 24. https://programmers.co.kr/learn/courses/30/parts/12198 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 이해 commands 를 통해 [ start, end, K ] 가 들어온다. command에 start, end 길이만큼 배열을 자른다. 자른 배열을 오름차순으로 기본 정렬한 후, K번째 수를 정답 배열에 저장 포인트 여기서 포인트는 , 반복하면서 주어진 배열을 자르는 방법이다. 자바에서 배열의 범위만큼 자르는 메소드로 쓰기 좋은것이 copyOfRange(Array, int startIndex, int La..
정렬 알고리즘 (2) - 퀵, 머지, 힙, JAVA 구현코드
2021. 7. 8. 지난번 정렬 알고리즘중 O(n2)의 시간복잡도를 갖는 알고리즘 (버블정렬, 선택정렬, 삽입정렬) 을 정리해보았다. 정렬 알고리즘(1) - 버블, 선택, 삽입 , JAVA 구현코드 정렬 알고리즘 정렬 알고리즘은 알고리즘 과목 중에서 기초적으로 반드시 알고 지나가야되는 파트입니다. 데이터를 정렬하는 방법이 다양하다. 다양한 정렬알고리즘 종류별 특징과 장단점이 bangu4.tistory.com 이번에는 그 보다 좀 더 빠르고 효율적인 O(n logn)의 복잡도를 갖는 알고리즘 (병합정렬, 퀵정렬 , 트리정렬) 을 정리해보자. 1. O(n logn)의 시간복잡도 퀵소트, 힙 소트, 머지소트 3가지가 존재한다. 모두 다 트리의 개념이 들어간 정렬 알고리즘이며, 퀵소트와 머지소트는 분할 정복 알고리즘이라고도 분류한..
정렬 알고리즘(1) - 버블, 선택, 삽입 , JAVA 구현코드
2021. 7. 7. 정렬 알고리즘 정렬 알고리즘은 알고리즘 과목 중에서 기초적으로 반드시 알고 지나가야되는 파트입니다. 데이터를 정렬하는 방법이 다양하다. 다양한 정렬알고리즘 종류별 특징과 장단점이 있으며, 상황별로 각각 유리한 정렬알고리즘이 있으니 정리해보자. 정렬 알고리즘의 종류는 아래와 같다 모든 정렬이 다 유용하지 않고, 반드시 알아야할 개념과 자주 사용하는 정렬 알고리즘 위주로 정리하겠다. 저 중 중요한것은 O(n2)의 시간복잡도를 갖는 알고리즘 (버블정렬, 선택정렬, 삽입정렬) 들과 그보다 좀더 빠르고 효율적인 O(n logn)의 복잡도를 갖는 알고리즘 (병합정렬, 퀵정렬 , 트리정렬) 들이다. 1. O(n2)의 시간복잡도 버블정렬, 선택정렬, 삽입정렬 3가지가 존재한다. 한줄로 특징을 줄여보자면 버블정렬은 서로..
[알고리즘] 알고리즘별, 자료구조별, 시간복잡도 - 총정리
2021. 7. 2. 1. 시간 복잡도란 ? 알고리즘의 효율성을 판단하기 위한 지표로서, 프로그램 수행에 걸리는 절대적 시간이 아닌, 알고리즘을 수행하는데 사용되는 연산들이 몇 번 이루어지는가에 대한 것을 상대적 지표로 나타낸 것이다. 연산에는 산술, 대입, 비교, 이동이 있다. 시간 복잡도, 즉 성능 측정에 사용되는 표기법은 Big-O, Big-Omega(Ω), Theta(θ) 크게 세 가지로 나뉜다. 2. 시간복잡도 성능지표 Better O(1) O(log n) O(n2) O(1): Operation push and pop on Stack O(log n): Binary Tree O(n): for loop O(n×log n): Quick Sort, Merge Sort, Heap Sort O(n2): Double for lo..
[Hash] 베스트 앨범 - Java 풀이★★★
2021. 6. 17. https://programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr 문제 해당 문제를 잘 풀기 위해서는, 문제를 잘 이해하는게 제일중요하다. 일단, 장르별로 Play횟수를 sum한 값을 저장해주어서, sort후 해당 장르에서 2곡씩 뽑아주어야 하는 문제이다. 장르별 Sum값은 Map을 이용하면 되지만, 곡의 가지는 정보는 id(인덱스), 장르, Play횟수 총 3가지 정보를 가지고 있으며, 각각의 속성별로 우선순위를 가지게 정..

티스토리툴바