본문 바로가기

알고리즘

 (63)
프로그래머스 최솟값 만들기(lv2, Python) https://school.programmers.co.kr/learn/courses/30/lessons/12941 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 분석 길이가 같은 두 배열의 원소를 하나씩 뽑아 곱하는 걸 배열 길이만큼 반복해 각각의 결과를 더함 더한 결과값이 최소가 되는 경우를 구하는 문제 아이디어 처음엔 탐색문제라 생각해서 모든 경우를 다 구해서 최솟값을 구하려했음...-> 구현 복잡하고 비효율적 다른 사람 풀이보니 두 배열을 오름차, 내림차순 정렬해서 각 인덱스끼리 곱했음-> 문제 원리 파악해서 구현 정답코드 def solutio..
프로그래머스 올바른 괄호(lv2, Python) https://school.programmers.co.kr/learn/courses/30/lessons/12909?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 접근 괄호가 문자열로 주어졌을 때 해당 괄호가 올바르게 되어있는지 판별하는 함수를 만드는 문제 아이디어 문자열을 하나씩 탐색하는데 여는괄호가 나오면 큐에 저장하고 닫는괄호가 나오면 하나씩 큐에서 제거하는 방식 -> 시간초과 문자열을 하나씩 탐색하는데 여는괄호가 나오면 스택에 저장하고 닫는괄호가 나오면 하나씩 스택에서 제거하는 방식 -> 성공? 큐를 활용한 풀이 ..
프로그래머스 - 소수찾기 (Python) https://school.programmers.co.kr/learn/courses/30/lessons/42839?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 접근 한자리 숫자가 적힌 카드들을 조합해서 만들 수 있는 소수의 개수를 구하는 문제 아이디어 주어진 카드로 수를 만들어 set에 저장하기(중복을 피하기 위함) set에 넣기전에 에라토스테네스(소수 판별 알고리즘)의 체를 활용해서 소수만 넣기 완성된 set의 개수 리턴하기 코드 myset = set() def solution(numbers): dfs('',numb..
프로그래머스 최소 직사각형(lv1, python) https://school.programmers.co.kr/learn/courses/30/lessons/86491 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 분석 주어진 크기의 명함들을 모두 수납할 수 있는 명함지갑의 최소 크기를 구하는 문제 일반적으로 생각하면 명함들의 가로세로 길이의 최대값을 곱해주면 되지만 명함은 회전이 가능하다. 아이디어 어차피 카드를 돌린다면 더 큰 쪽을 가로, 짧은 쪽을 세로라고 생각하였다. 두 리스트( maxW, maxH)를 만들어 주어진 명함들의 가로, 세로 중 큰 값을 maxW에 넣고, 작은 값을 maxH에 넣었다..
프로그래머스 lv2 괄호 회전하기(kotlin) https://school.programmers.co.kr/learn/courses/30/lessons/76502 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 접근 문자열을 회전시켜가며 괄호가 올바르게 되어있는지를 확인하는 문제 괄호가 올바르게 되어있는지를 확인하는 함수를 따로 만들어서 처리하였다. 다만 반례가 응근 많이나와서 반례가 안나올때까지 조건을 하나하나 추가해주었다.... 정답코드 class Solution { var list = mutableListOf() fun solution(s: String): Int { var answer: In..
백준 14501- 퇴사(kotlin) https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제 접근 주어진 날짜안에 상담을 진행하여 얻을 수 있는 최대 수익을 구하는 문제이다. 전체 날짜를 1일찍 상담을 할지말고 선택하는 dp문제인것 같다. 각 날짜에 상담을 진행할지말지를 선택할 수 있고 전체 날짜를 n이라 했을 때 시간 복잡도는 O(2^n)(1
백준 9095번 - 1, 2, 3 더하기 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 접근 주어진 정수를 1,2,3의 합으로 나타내는 경우의 수를 구하는 문제 주어진 정수를 1,2,3으로 쪼개는 경우의 수 :: 재귀를 통해 구현 재귀함수의 구성요소는 다음과 같다. 1. 다음 경우를 호출 2. 정답을 찾은 경우 return 3. 불가능한 경우 return(문제의 조건을 위배한 경우, 절대로 답을 구할 수 없는 경우) 정답 코드 import java.util.Scanner fun main(args: Array): Unit = with(Scanner(System.`in`)) { ..
재귀함수 매우 간단한 동작과정 재귀함수 코딩테스트를 위해 알고리즘 문제를 풀던중 DFS나 DP 분할 정복 등의 문제를 풀다보면 재귀함수가 자주 사용되는 것을 볼 수 있다. 기본적으로 재귀함수란 함수 내에서 자기 자신을 호출하는 함수인데, 일반적인 구현 등은 우리가 눈으로 따라가며 동작과정을 생각할 수 있지만 재귀함수가 나오는 순간 이게 어떤 순서로 컴파일 되는지를 몰랐었다. 재귀함수로 탐색시 고려사항 재귀함수를 작성할때는 다음의 조건들을 고려해야한다. 호출시에 수행할 작업을 작성 : 수행작업 호출시에 변경할 값을 작성 : 수행마다 변경해줄 값(상황따라 변경값이 없을 수도 있음) 원하는 답을 찾을 경우 함수를 종료 : 종료조건 조건을 벗어나서 원하는 답을 절대 찾지 못하는 경우 함수를 종료 : 종료조건 재귀함수 예시 매우 간단한 재귀함..

티스토리툴바