전체 글 2071

[Programmers] 최적의 행렬 곱셈

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/12942 코딩테스트 연습 - 최적의 행렬 곱셈 크기가 a by b인 행렬과 크기가 b by c 인 행렬이 있을 때, 두 행렬을 곱하기 위해서는 총 a x b x c 번 곱셈해야합니다. 예를 들어서 크기가 5 by 3인 행렬과 크기가 3 by 2인 행렬을 곱할때는 총 5 x 3 x 2 = programmers.co.kr DP를 이용하면 풀 수 있는 문제였습니다. 알고리즘은 아래와 같습니다. 1. cache[i][j]: [i, j] 구간 내 행렬 최소 곱셈 연산 수를 저 2. 구간을 쪼개가며 현재 cache[i][j]와 비교하며 더 작은 연산 값을 저장 3. 2번을 진행한 후 cache[0][mat..

알고리즘/programmers 2022.06.25 (6)

[Programmers] 사라지는 발판

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/92345 코딩테스트 연습 - 사라지는 발판 [[1, 1, 1], [1, 1, 1], [1, 1, 1]] [1, 0] [1, 2] 5 [[1, 1, 1], [1, 0, 1], [1, 1, 1]] [1, 0] [1, 2] 4 programmers.co.kr 비트 마스킹을 연습하기 좋은 문제였습니다. 알고리즘은 아래와 같습니다. 1. 주어진 board 정보를 기반으로 boardBit을 생성합니다. -> ex) [[1, 1, 1], [1, 0, 1], [0, 1, 1]]이 주어졌을 경우 boardBit는 111101011을 십진수로 변환한 값 2. 재귀함수 func는 매개변수 {y, x}에 위치한 사람..

[Programmers] 불량 사용자

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/64064 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 programmers.co.kr 알고리즘은 아래와 같습니다. 1. 불량 사용자 아이디에 해당하는 유저 아이디의 인덱스들을 벡터 배열 v에 넣어줍니다. 2. func 재귀 함수를 통해 나올 수 있는 유저 아이디의 인덱스 조합들을 정렬한 상태로 set에 넣어줍니다. 3. 2번에서 구한 set의 크기를 반환해주면 끝 개발환경: Programmers IDE 지적, 조언, 질문 환영합..

[Programmers] 선입 선출 스케줄링

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/12920 코딩테스트 연습 - 선입 선출 스케줄링 처리해야 할 동일한 작업이 n 개가 있고, 이를 처리하기 위한 CPU가 있습니다. 이 CPU는 다음과 같은 특징이 있습니다. CPU에는 여러 개의 코어가 있고, 코어별로 한 작업을 처리하는 시간이 다릅니 programmers.co.kr 우선순위 큐를 이용하면 쉽게 풀 수 있을 것 같은 문제이지만 주어진 조건의 범위가 크기 때문에 힙을 이용할 경우 시간 초과가 발생하는 문제입니다. 해당 문제는 코어 당 작업을 처리하는 시간을 기준으로 최소 시간과 최대 시간을 구하여 해당 범위 내 파라메트릭 서치 기법을 이용하여 풀어야 시간제한 내 AC를 받을 수 있..

[Programmers] 최고의 집합

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/12938 코딩테스트 연습 - 최고의 집합 자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 "집합"으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다. 각 원소의 합이 S가 되는 수의 집합 위 조건을 만 programmers.co.kr 집합의 원소 간의 차가 최소일 때 각 원소 간의 곱이 최대가 되는 것은 자명합니다. 따라서, 알고리즘은 아래와 같습니다. 1. s를 n으로 나누었을 때 1보다 작을 경우 원소들의 합이 s가 될 수 없으므로 바로 -1을 반환해줍니다. 2. 우선, 벡터에 (s / n)을 n개 넣어줍니다. 2.1 여기서 (s / n)은 s를..

[Programmers] 야근 지수

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/12927 코딩테스트 연습 - 야근 지수 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도 programmers.co.kr 최대 힙을 이용하여 쉽게 풀 수 있는 문제였습니다. 1. 최대 힙을 선언하고 모든 작업을 넣어줍니다 2. 반복문을 n번 돌리면서 제일 오래 걸리는 작업을 꺼내 시간을 1 감소시키고 다시 넣어줍니다. 2.1 시간이 0 미만으로 내려갈 수 없다는 점을 주의해야 합니다. 3. 힙에 있는 작업들을 모두 제곱한 결과를 반환합니다. 개발환경..

[Programmers] 가장 긴 팰린드롬

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/12904 코딩테스트 연습 - 가장 긴 팰린드롬 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들 programmers.co.kr 세 단계로 나누어서 접근해야 하는 문제였습니다. 1. 모든 구간에 대해 길이가 1인 팰린드롬 존재하므로 모두 cache[i][i] 모두 1로 표시 2. 길이가 2인 팰린드롬 찾아 존재하면 answer를 2로 업데이트 3. 길이가 3 이상인 팰린드롬을 찾아 answer를 해당 길이로 업데이트 ..

[Programmers] N-Queen

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/12952 코딩테스트 연습 - N-Queen 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 programmers.co.kr n은 최대 12이기 때문에 모든 경우의 수에 대해 가지치기를 하며 진행하면 쉽게 풀 수 있는 문제였습니다. 똑같은 문제로 백준 9663번 N-Queen(https://jaimemin.tistory.com/813)이 있습니다. 백준 9663번 N-Queen 문제 링크입니다: https://www.acmicpc.net/problem/..

[Programmers] 숫자 블록

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/12923 코딩테스트 연습 - 숫자 블록 1 10 [0, 1, 1, 2, 1, 3, 1, 4, 3, 5] programmers.co.kr 해당 문제는 아래의 두 조건에 의해 브루트포스로 접근해도 되었습니다. end - begin의 값은 항상 10,000을 넘지 않습니다. 그렙시는 길이가 1e9인 도로에 1번 블록부터 시작하여 1e7 블록까지 위의 규칙으로 모두 놓았습니다. 개발환경: Programmers IDE 지적, 조언, 질문 환영합니다! 질문 남겨주세요~

[Programmers] 멀리 뛰기

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/12914 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2 programmers.co.kr 아래와 같이 규칙을 나열해보면 피보나치 수열인 것을 알 수 있습니다. n = 1 -> 1 n = 2 -> 2 n = 3 -> 3 n = 4 -> 5 n = 5 -> 8 ... 따라서, 주어진 n에 대한 피보나치 수열을 구해주면 되는 문제였습니다. 개발환경: Programmers IDE 지..