이것이 코딩테스트다 Chapter 03 그리디 Greedy 알고리즘이란 현재 상황에서 지금 당장 좋은 것만 고르는 방법 매 순간 가장 좋아 보이는 것을 선택하고, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음 언제, 어떻게 사용할까 현재 상황에서 가장 좋아 보이는 것만 선택해도 문제를 풀 수 있을 때(정확한 답이 나온다는 보장이 있을 때) 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 제시해주는 기준으로 정렬해주는 경우가 많다 주로 정렬 알고리즘과 짝을 이룸! 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때는 매우 효과적이고 직관적이다 문제 풀이를 위한 아이디어를 떠올리고, 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다
https://school.programmers.co.kr/learn/courses/30/lessons/12915 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr - 정렬 기준인 인덱스 n번째 문자를 맨 앞에 붙여주고 정렬, 후 맨 앞 글자는 떼고 answer에 넣어준다 def solution(strings, n): answer = [] for i in range(len(strings)): strings[i]=strings[i][n]+strings[i] strings.sort() for i in range(len(strings)): answer.append..
순차검색 알고리즘(Sequential Search) 모든 값을 검색하기 때문에 O(n)의 시간 복잡도를 지닌다. 이분검색 알고리즘(Binary Search) 중간의 값과 비교하여 그보다 작으면 그 왼쪽에 있는 값을 대상으로, 크면 오른쪽에 있는 값을 대상으로 다시 범위의 중간값과 비교하는 검색을 진행한다. 반복문을 수행할 때마다 검색 대상의 총 크기가 반으로 줄기 때문에 최악의 경우라도 O(log n)의 시간 복잡도를 가진다. 최악의 경우를 상정했을 때, 순차검색은 n번인 반면 이분검색은 lg(n+1) 이므로 이분검색이 훨씬 효과적이다.
시간 복잡도 입력크기에 따라서 단위연산이 몇 번(n) 수행되는지 결정하는 절차 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는 지 즉, 알고리즘을 위해 필요한 연산의 횟수를 대략 구할 수 있다. 단위연산의 정의에 따라서 복잡도의 계산이 달라질 수 있다! 별다른 언급이 없다면 대부분 시간 복잡도를 칭함 공간 복잡도 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미 알고리즘을 위해 필요한 메모리의 양을 대략 구할 수 있다. 표현의 척도 입력 크기(input size) 배열의 크기, 리스트의 길이, 행렬에서 행과 열의 크기, 트리에서 마디와 이음선의 수, 그래프에서는 정점과 간선의 수 단위연산(basic operation) 비교(comparison), 지정(assignm..
https://school.programmers.co.kr/learn/courses/30/lessons/176962 멈춘 과제들 -> stack사용(가장 최근에 멈춘 걸 다시 시작하니까) 1. 배열 시간순으로 정렬 -> Map 사용, key를 List 사용해서 정렬 2. 지금 하고 있는 것의 끝 시간 vs 다음 할 일의 시작 시간 비교 - 다음 시작 시간이 더 먼저일 경우 시작 시간 전까지 시간 빼서 stack에 이름과 저장 - 만약 다음 시작 시간이 더 늦거나 같을 경우 이번 거 끝냄, answer에 이름 추가 -2번 처음으로 stack에 [과목명, 남은 시간] 저장해서 현시간에 더한 것 vs 다음 과제 비교! import java.util.*; class Solution { public String[..
https://school.programmers.co.kr/learn/courses/30/lessons/142086 1. Map을 써서 새로운 알파벳이 나올 때마다 인덱스를 업데이트 해 준다 => 기존에 있던 알파벳일 경우 찾아서 현재 인덱스에서 마이너스 한 값을 result에 입력 없으면 걍 -1을 result 에 넣고, 현재 인덱스를 map에 넣어줌 -> 시간복잡도 O(N) 2. 이중 for 문 돌리기 ->O(N^2) 시간복잡도 적은 1번 사용 import java.util.*; class Solution { public int[] solution(String s) { int[] answer = new int[s.length()]; Map charMap = new HashMap(); for(int i..
https://school.programmers.co.kr/learn/courses/30/lessons/138476 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr https://blog.naver.com/khk990/222920087160 [Java] HashMap key, value 정렬 HashMap 정렬 key 정렬 value 정렬 오름차순 내림차순 역순 역순정렬 맵정렬 해시맵정렬 map정렬 blog.naver.com 이 글을 참조해서, value의 크기로 정렬한 key 값을 사용하였다 value의 크기가 큰 순으로 배열하여, k에서 차례대로 뺀 다..
https://school.programmers.co.kr/learn/courses/30/lessons/12973#qna import java.util.Stack; class Solution{ public int solution(String s){ Stack stack = new Stack(); int idx = 0; char[] chars = s.toCharArray(); while(idx
https://school.programmers.co.kr/learn/courses/30/lessons/12940 class Solution { public int[] solution(int n, int m) { int[] answer = new int[2]; answer[0]=gcd(n,m); answer[1]=m*n/answer[0]; return answer; } int gcd(int a, int b){ if(a%b==0) return b; return gcd(b,a%b); } }
https://school.programmers.co.kr/learn/courses/30/lessons/12909 import java.util.Stack; class Solution { boolean solution(String s){ Stack stack = new Stack(); char[] ch = s.toCharArray(); for(int i=0;i
