본문 바로가기

알고리즘

 (70)
프로그래머스 - 가장 큰 정사각형 찾기 https://programmers.co.kr/learn/courses/30/lessons/12905 코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr 가장 큰 정사각형 찾기 문제는 동적 프로그래밍(DP)을 활용하여 문제를 풀 수 있습니다. 동적 프로그래밍은 어려운 문제를 여러 개의 하위 문제로 쪼갠 후, 이 하위 문제들을 먼저 해결하여서 더 큰 문제를 푸는 방법입니다. 가장 큰 정사각형을 찾는 문제를 하위 문제로 쪼갠다면 가장 작은 정사각형을 찾음으로써 가장 큰 정사각형을 찾으면 되겠죠.. 문제 풀이 방식 1. 작은 정사각형을 찾기 위해 자신을 기준으로 왼쪽, 왼쪽 상단, 상단의 3방향의 숫자를 보고..
[정렬 뿌시기] - 선택정렬(Selection Sort) 선택 정렬(Selection Sort)란? 가장 작은 값을 찾아 맨 앞부터 순차적으로 정렬하는 방법 선택 정렬의 알고리즘은? (1) 1번과 2번 원소를 비교 (2) 1번과 3번 원소를 비교 (3) 1번과 4번 원소를 비교 (4) 1번과 5번 원소를 비교 (5) 1번과 2~5번 원소를 비교하여 가장 작은 값을 가진 원소의 인덱스를 기억하여 첫 번째 인덱스와 값을 변경한다. (6) 2번과 3번 원소를 비교 (7) 2번과 4번 원소를 비교 (8) 2번과 5번 원소를 비교 (9) 2번과 3~4번 원소를 비교하여 가장 작은 값을 가진 원소의 인덱스를 기억하여 두 번째 인덱스와 값을 변경한다.(자기 자신이 가장 작은 값일 경우 그대로 유지) 위와 같이 순차적으로 앞에서 부터 정렬시켜 나가는 방법을 선택 정렬이라 한..
프로그래머스 - 크레인 인형뽑기(2019 카카오 개발자 겨울 인턴십) https://programmers.co.kr/learn/courses/30/lessons/64061 코딩테스트 연습 - 크레인 인형뽑기 게임 [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]] [1,5,3,5,1,2,1,4] 4 programmers.co.kr 문제가 상당히 깁니다.. 문제의도는 Stack 자료구조를 사용할 수 있어?라고 생각했습니다. 크레인으로 뽑은 인형을 Stack에 넣으면서 상단의 2개의 인형이 같다면 지워주면 됩니다. 풀이 class Solution { int answer = 0; public int solution(int[][] board, int[] moves) { Stack stack = new Stack(); //..
프로그래머스 - 소수 찾기 (에라토테네스의 체) https://programmers.co.kr/learn/courses/30/lessons/12921 코딩테스트 연습 - 소수 찾기 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.) 제한 조건 n은 2이상 programmers.co.kr 소수란 1과 자기 자신으로만 나누어지는 숫자를 의미합니다. 소수를 찾는 문제이므로 2~N까지 순차적으로 순환하면서 소수를 찾는 소스 코드를 작성했습니다. 첫 번째 풀이 class Solution { public int solution(int n) { int answer = 0; for(int i=2; i
[정렬 뿌시기] - 버블정렬(Bubble Sort) 버블 정렬(Bubble Sort)란? 순차적으로 인접한 두개의 원소를 비교해나가면서 정렬하는 방법 버블 정렬의 알고리즘은? (1) 1번 원소와 2번 원소를 비교 후 변경 또는 유지 (2) 2번 원소와 3번 원소를 비교 후 변경 또는 유지 (3) 3번 원소와 4번 원소를 비교 후 변경 또는 유지 (4) 4번 원소와 5번 원소를 비교 후 변경 또는 유지 (5) 배열의 크기 -1 만큼의 비교 연산이 이루어진다면, 가장 큰 수가 마지막에 정렬될 것이다. (6) 다시 처음으로 돌아와 1번 원소와 2번 원소를 비교 후 변경 또는 유지 (7) 2번 원소와 3번 원소를 비교 후 변경 또는 유지 계속해서 순차적으로 인접 원소와 비교해 나가게 되고 빨간 상자로 표시 된 마지막 수는 모든 원소와 비교 후에 가장 큰 수로 판..
프로그래머스 - JadenCase 문자열 만들기 https://programmers.co.kr/learn/courses/30/lessons/12951#qna 코딩테스트 연습 - JadenCase 문자열 만들기 JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는 함수, solution을 완성해주세요. 제한 조건 programmers.co.kr 문제 설명 JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는 함수, solution을 완성해주세요. 제한 조건 s는 길이 1 이상인 문자열입니다. s는 알파벳과 공백문자(" "..
프로그래머스 - 단어변환(DFS) https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 프로그래머스 단어변환입니다. DFS를 활용하여 풀 수 있습니다. 1. 단어를 변환할 수 있는 모든 경우의 수만큼 탐색을 진행합니다. 2. DFS의 종료 조건을 설정 3. DFS가 종료 조건을 달성했을 때, 달성까지 걸린 재귀의 횟수를 카운트( 재귀하는 만큼 단어의 변환 작업이 이루어 난 것) 4. 카운트 한 수중에서 가..
프로그래머스 - 타겟넘버 (DFS, 조합 두가지 풀이) https://programmers.co.kr/learn/courses/30/lessons/43165?language=java 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 프로그래머스 타겟 넘버 문제입니다. 문제의 의도는 DFS를 활용한 풀이인것 같습니다. 그러나 처음에 연산자의 조합을 구해서 문제를 푸려고 시도했고 그 과정에서 많은 고민도 했네요.. 연산자의 조합을 이용한 풀이 조합의 경우 순서를 신경쓰지 않아도 되지만 이 풀이에서는 조합의 순서를 신..

티스토리툴바