프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 설명 f(x): 양의 정수 x에 대해 x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수 예시)f(7) = 117: (0)1118: 1000 -> 4 (다른 비트 개수)9: 1001 -> 310: 1010 -> 311: 1011 -> 27보다 크고 비트가 다른 지점이 2개이하이면서 가장 작은 수는 11이다. 정수들이 담긴 배열 numbers가 주어지고 각 수들에 대해 f 값을 구하는 문제이다. 해결 방법비트 개수가 2개 이하로만 달라야 하기 때문에 마지막에 0이 나오는 위치(가장 오른쪽의..
https://school.programmers.co.kr/learn/courses/30/lessons/42898 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 설명m x n 크기의 격자모양으로 나타냈을 때 물에 잠긴 지역(puddles)을 피해 (1, 1)에서 (m, n)까지 갈 수 있는 최단 경로의 개수를 1,000,000,007로 나눈 나머지를 구하는 문제이다.이때 오른쪽과 아래쪽으로만 움직일 수 있다.⚠️ 다른 문제와 다르게 여기서 m이 열이고 n이 행을 나타낸다.입출력 예) 입력 - m: 4, n: 3, puddles: [[2, 2]] 출력 ..
https://www.acmicpc.net/problem/2325 2325번: 개코전쟁 “앙두레 강”이 개미와 코끼리 결혼식에서 기차를 아름답게 만드는 것을 실패했기 때문에 식장이 아수라장이 되고 결혼이 물거품이 되어버렸다. 급기야는 왕국 간에 분쟁으로 이어져 개미왕 www.acmicpc.net 문제 내용 1번 정점에서 N번 정점으로의 최단거리가 최대가 되도록 도로 하나를 파괴하도록 하자. (어떤 하나의 도로를 파괴하더라도 1번 정점에서 N번 정점으로 도달 가능하다) 해결 방법 모든 최단 경로를 구한 다음, 최단 경로에 포함된 간선들을 하나씩 제거해보며 다시 다익스트라를 호출하면 된다. 1. 다익스트라 알고리즘을 이용해 최단 경로를 계산한다. 2. BFS를 이용해 최단 경로에 포함된 모든 간선을 찾아 저..
https://www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 문제 내용 N개의 도시가 주어지고 그 사이 도로와 이 도로를 통과할 때 걸리는 시간이 주어졌을 때, 1번에서 N번까지 가는 데 최소 시간이 걸리도록 하는 K개의 이하의 도로를 포장하는 것이다. 도로는 이미 있는 도로만 포장할 수 있고, 포장하게 되면 도로를 지나는데 걸리는 시간이 0이 된다. 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(..
10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 내용 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. 해결 방법 ✔️ dp[i][j]: 길이가 i이고, j로 끝나는 계단수의 경우의 수 로 점화식을 생각할 수 있다. 우선 길이가 1인 계산수는1부터 9까지가 있다. 0으로 시작하는 수는 계단수가 아니기 때문에 dp[1][0]은 dp[1][1] 부터 dp[1][9]는 다 1이다. 이때 만약 길이가 i이고, j로 끝나는 계단수의 개수를 생각해보면 길이가 i-1이고 j..
18427번: 함께 블록 쌓기 첫째 줄에 자연수 N, M, H가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 10, 1 ≤ H ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 각 학생이 가진 블록들의 높이가 공백을 기준으로 구 www.acmicpc.net 문제 내용 1번부터 N번까지의 학생들은 각각 블록들을 가지고 있다. 학생마다 최대 M개의 블록을 가지고 있을 수 있으며, 한 명의 학생이 가지고 있는 모든 블록들의 높이는 서로 다르다. 이 때 1번부터 N번까지의 학생들이 가진 블록을 차례대로 사용하여 바닥에서부터 쌓아올려 하나의 탑을 만들고자 한다. 단, 어떤 학생의 블록은 사용하지 않아도 되며 한 학생당 최대 1개의 블록만을 사용할 수 있다. 1번부터 N번까지의 학생들이 ..
https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 문제 내용 어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다. 단, "VIP 회원"들은 반드시 자기 좌석에만 앉아야 한다. VIP 회원들의 좌석 번호들이 주어졌을 때, 사람들이 좌석에 앉는 서로 다른 방법의 가짓수..
https://www.acmicpc.net/problem/5214 5214번: 환승 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어 www.acmicpc.net 문제 내용 1번부터 N번역이 있고, 하이퍼튜브 하나는 역을 서로 연결해준다. 이때 1번역에서 N번역까지 방문하는 최소 역의 수를 구하는 문제이다. 첫째 줄에 역의 수 N, 하이퍼튜브가 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) M개의 줄에는 하이퍼튜브가 서로 연결하는 역의 번호 정보가 주어진다..
