본문 바로가기

Algorithm

 (2139)
(C++) - 프로그래머스(고득점 kit - 동적계획법(DP)) : 등굣길 programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr top down dp를 이용해 풀었습니다. 풀이방법 동그라미 표시된 지점으로 가는 방법은 1, 2번 방법 뿐입니다. 따라서, 현재 i,j지점으로 올 수 있는 경우의 수 = (i-1,j로 올 수 있는 경우의 수) + (i,j-1로 올 수 있는 경우의수)가 됩니다. 이를 점화식으로 옮겨볼 수 있습니다. 점화식으로 옮긴다면 다음과 같습니다. d[i][j] = d[i-1]..
(C++) - 백준(BOJ) 11000번 : 강의실 배정 답 www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 풀이방법 1. 강의 시작시간이 빠른 것이 우선, 만약 강의 시작시간이 같다면 끝나는 시간이 먼저 오도록 정렬해줍니다. 2. min heap pq(끝나는 시간이 빠른 것이 위로 가도록)를 사용해 강의실을 배정합니다. 우선순위 큐의 원소에는 강의 끝나는 시간이 들어갑니다. top()이 강의 시작시간 이하라면 이 강의는 한 강의실에서 이어받으면 되므로 pop 합니다. 이 후 해당 강의의 끝나는 시간을 넣어줍니다. Code #include using namespac..
(C++) - 백준(BOJ) 1449번 : 수리공 항승 답 www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net greedy문제였습니다. 풀이방법 1. 물이 세는 위치를 저장할 배열을 선언하고 입력받습니다. 오름차순 입력 보장이 안되므로 입력 후에는 오름차순으로 정렬해줍니다. 2. 테이프가 칠해지지 않은 곳을 발견하면 그 위치부터 + l까지 1000을 안넘는 공간에 한해 테이프를 붙입니다. 그 후 테이프의 개수를 저장하는 변수 ans를 1더해 줍니다. Code #include using namespace ..
(C++) - 백준(BOJ) 4796번 : 캠핑 답 www.acmicpc.net/problem/4796 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net greedy문제였습니다. 풀이방법 1. v/p*l일 수 만큼 캠핑을 먼저 갑니다. 2. 나머지 갈 수 있는 캠핑 일 수를 더해줍니다. v%p > l >> p >> v; if(!l && !p && !v) break; caseCnt++; int ans = v/p*l; if(v%p
(C++) - 프로그래머스(고득점 kit - 동적계획법(DP)) : 정수 삼각형 답 programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 간단한 dp문제였습니다. 풀이방법 1. d배열을 정의합니다 현재 i층의 j번째 원소가 최적의 방법으로 선택했을 때의 최대값 : max(i-1번째 층 j-1원소, i-1 번째 층 j원소) + 삼각형 i층 j번째 원소의 값 2. 마지막 층의 d의 원소들 중 최대값을 반환합니다. Code #include using namespace std; int solution(vector triangle) { int size = triangle.size(); int a..
(C++) - 백준(BOJ) 2503번 : 숫자야구 www.acmicpc.net/problem/2503 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net brute force로 푼 문제였습니다. 풀이방법 1. 111부터 999까지 loop를 돕니다. 같은 숫자인 경우나 0을 포함하는 경우는 건너뜁니다. 2. 질문에 나온 수로 ball과 strike의 개수를 세줍니다. 한 질문에 대한 ball이나 strike개수가 다르다면 답이 될 수 없으므로 flag를 세워줍니다. 3. 모든 질문에 대한 ball과 strike개수가 같다면(if(!flag)) 답입니다. 4. 조..
(C++) - 백준(BOJ) 10448번 : 유레카 이론 www.acmicpc.net/problem/10448 10448번: 유레카 이론 프로그램은 표준입력을 사용한다. 테스트케이스의 개수는 입력의 첫 번째 줄에 주어진다. 각 테스트케이스는 한 줄에 자연수 K (3 ≤ K ≤ 1,000)가 하나씩 포함되어있는 T개의 라인으로 구성되어 www.acmicpc.net brute force로 푼 문제였습니다. 풀이방법 1. 누적합을 1000까지 구해줍니다. 2. 누적합이 1000을 넘는 구간은 45번째 수부터이므로 3개 수들 합이 찾으려는 수와 같은지 3개의 for문을 이용해 찾아줍니다. Code #include #define ll long long using namespace std; int triangleNum[1001]; int t; bool ck(int num..
(C++) - 프로그래머스(고득점 kit - 스택) : 기능개발 programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr stack에 분류되어있지만 그렇게 풀지 않았습니다. 풀이방법 1. 앞 기능을 pivot으로 잡고 이보다 큰 남은 일 수가 있다면 pivot을 해당 인덱스로 옮겨줍니다. 그리고 셌던 기능 개수를 answer에 push 해줍니다. 2. 작거나 같다면 같은날에 배포되므로 cnt를 1씩 증가시켜줍니다. Code #include using namespace std; vector..

티스토리툴바