본문 바로가기

CS/알고리즘&문제풀이

 (19)
[프로그래머스] 숫자 변환하기 https://school.programmers.co.kr/learn/courses/30/lessons/154538 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 숫자 x가 주어졌을 때, x에 2 또는 3을 곱하거나 n을 더해 y를 만들 수 있는 경우의 수 중 최소 연산 횟수를 구하는 문제이다. 뭔가 동적 계획법을 적용하면 좋을 것처럼 보인다. 하향식 방법 맨 처음에는 하향식 동적 계획법을 적용, 주어진 각각의 연산이 숫자에 대해 수행 가능한 경우, 해당 값들 중 최소값을 선택하여 캐시에 기록하며 처리하는 방식을 고려했다. function solution..
[프로그래머스] 방문 길이 https://school.programmers.co.kr/learn/courses/30/lessons/49994 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr x, y 각각 최소 -5, 최대 5의 좌표를 가지는 좌표 공간에 대해 4 방향(L, R, U, D)으로 움직일 수 있다. 경계를 넘어가는 입력은 무시하며, 이동한 "경로"의 길이를 구하는 것이 이번 문제에서 원하는 답이다. 문제를 풀 때 작성해야 하는 코드는 크게 2가지로 나뉠 것 같다. 격자에서 좌표의 이동을 계산하는 알고리즘 이동한 경로를 기록하는 알고리즘 1번의 경우 단순히 아래와 같이 나타..
[백준] 4948, 베르트랑 공준 https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net N 초과 2N 이하 범위의 소수를 선택하는 알고리즘을 작성하는 문제다. n의 범위는 [ 1, 123456 ] 이므로 현재 문제에서 나타나는 숫자의 범위는 1 ~ 246912 ( 2N )으로 한정된다. 브루트 포스 가장 큰 숫자인 246912 기준 제곱근을 씌우면 소수 판별을 위해 496번의 연산을 필요로 한다. 이 수치가 상당히 작다고 생각해서 맨 처음에는 N이 들어올 때마다 각각 연산하여..
[프로그래머스] 마법의 엘리베이터 https://school.programmers.co.kr/learn/courses/30/lessons/148653 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 마법의 엘리베이터는 0층 이상의 값을 가지며, 한번에 10c (c >= 0) 층(1, 10, 100 ... 위 아래 다 가능)씩 움직일 수 있다. 한번 움직이는데 마법의 돌 하나가 필요할 때 최소 개수로 0층까지 이동하는 것이 이번 문제의 목표다. 1 600 -(4)> 1000 -(1)> 0이기 때문이다. 이때 매 순간마다 10c 자리만 생각해보자. 각 자리에서 올림 등 로직을 전부 처리하고 나..
[프로그래머스] 뒤에 있는 큰 수 찾기 https://school.programmers.co.kr/learn/courses/30/lessons/154539 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 배열의 각 원소에 대해 자기보다 1) 뒤에 있고 2) 크면서 3) 가장 가까운 숫자를 "뒷 큰 수"라고 정의한다. 현재 문제는 배열이 주어졌을 때 뒷 큰 수를 구하는 문제다. 단순히 생각해서 특정 인덱스에서 자기보다 인덱스가 높은 모든 배열 원소와 값을 비교한다면 결과를 구할 수 있다. 예를 들어 인덱스가 1이라면, 인덱스 2 ~ n-1의 원소를 모두 비교하다 보면 언젠가 답이 나오는 것이다. ..
[프로그래머스] 숫자 블록 https://school.programmers.co.kr/learn/courses/30/lessons/12923# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 길이가 1,000,000,000(10억) 인 블록 각각에 숫자를 부여하되, 다음 조건을 만족한다. 숫자의 범위는 1 ~ 10,000,000(1천만) 이다. 숫자 N은 2 * N, 3 * N ... 블록에 부여될 수 있으며, 작은 숫자에서 큰 숫자 순서로 블록을 덮어쓸 수 있다. 예를 들어 4번째 블록에 숫자 1이 부여되더라도, 이후 숫자 블록 2에 의해 갱신될 수 있다. 즉, 조건을 만족하는 경..
[백준] 랜선 자르기 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 발상에 도움이 된 영상: https://www.youtube.com/watch?v=94RC-DsGMLo 문제 설명 기존에 있던 랜선 K개를 동일한 양의 정수 길이 L 단위로 잘라 N개 이상의 동일한 랜선을 얻을 때, L의 최대값을 구하는 문제다. 일단 L의 후보 L'을 찾으면 ∑ ( Ki // L' ) >= N인지 판단할 수 있는데, 해당 조건을 만족하는 경우 L'을 ..
[백준] 계단 오르기 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 최근에 동적 계획법 문제를 접했는데 개인적으로 너무 어렵다고 느꼈다. 다만 계속 삽질하면서 얻은 경험적 지식 중 하나는 특정 동적 계획법 문제들은 뒤에서 앞 방향으로 식을 반대로 생각하면 쉬울 수 있다는 것이다. 현재 문제는 이러한 경우 중 하나로, 도착지 입장에서 점화식을 전개하는 방식으로 식을 작성했다. N번째 계단에 도달할 수 있는 경우는 크게 2가지가 존재할 수 있다. N-1번째 계단을 밟는 경우 N-..

티스토리툴바