본문 바로가기

알고리즘

 (305)
[프로그래머스] 2023 Kakao Blind Recuiment : 표현 가능한 이진트리 https://school.programmers.co.kr/learn/courses/30/lessons/150367 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📄 문제개요 특정 숫자가 주어질때 해당숫자를 이진수로 만들고, 이진수를 만든뒤, 포화 이진트리를 만든다. 예를들어 포화 이진트리는 아래와 같다. 루트노드가 1이면 자식노드는 0또는 1을 갖는다. 루트노드가 0이면 자식노드들도 0이 되어야한다. 🤔 문제분석 특정숫자를 이진수로 만든뒤 포화 이진트리로 만들어야한다. 높이가 n일때, 포화 이진트리는 노드의 개수가 2^n -1 를 갖는다. 숫자에 왼쪽에..
[프로그래머스] 2023 Kakao Blind Recuiment 택배 배달 수거하기 https://school.programmers.co.kr/learn/courses/30/lessons/150369 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📄 문제개요 배달해야할 택배와, 수거해야할 재활용 박스가 각 집에 주어졌을때, 트럭이 Cap크기만큼 박스를 트럭에 실을 수 있고, 트럭이 택배를 전달하고, 재활용 박스를 수거하는 최단경로를 구하시오. 🤔 문제분석 택배는 항상 Cap 크기만큼 전달한다. 재활용박스는 항상 Cap크기만큼 수거한다. 택배는 항상 맨 끝에있는 재활용박스를 거두어야할 집 혹은 배달해야할 집으로 이동해야한다. 스택 자료구조..
[백준] 11066번 : 파일 합치기 11066번: 파일 합치기 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 📄 문제개요 두개의 파일을 합칠때 필요한 비용이 주어질때, 한개의 파일을 완성하는데 필요한 비용의 총 합을 계산하여라. 최소비용으로 계산하는 프로그램을 작성하여라. 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고 라는 조건으로 우선순위 큐로 풀 수 없다. 🤔 문제분석 우선순위 큐 해당문제는 우선순위 큐로 문제를 해결 할 수 있습니다. 최소비용을 갖으려면 항상 작은값을 합쳐야합니다. 따라서 우선순위큐로 항상 작은값 2개를 선택..
[백준] 1106번 : 호텔 1106번: 호텔 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net 📄 문제개요 형택이가 홍보를 할 수 있는 도시가 주어지고, 각 도시별로 홍보를 하는데 드는 비용과, 그 때 몇명의 호텔 고객이 늘어나는지에 대한 정보가 있다. 단, 9원들 들여서 홍보하면 고객이 3명 늘어나는 조건에서 → 3원을 들여서 1명의 고객, 12원을 들려서 4명의 고객을 늘어나게 할수 없다. (9원 3명, 18원 6명, 27원 9명) 가능 호텔에 고객을 적어도 C명 늘리기 위해, 형택이가 투자해야 하는 돈의 최소값을 구하는 프로그램..
[백준] 2629번 : 양팔저울 2629번: 양팔저울 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 📄 문제개요 양팔 저울과 몇개의 추가 주어졌을때, 이를 이용하여 입력으로 주어진 무게의 구슬을 확인 할 수 있는지 결정하고자 한다. 제한된 추의 개수가 주어지고 ( 30개 이하 ), 추의 무게는 500g 이하이며, 구슬의 개수는 7개 이하이다. 각 구슬의 무게에 대하여 확인이 가능하면 Y 아니면 N을 출력한다. 양팔 저울에는 추를 둘다 놓을 수 있다. 🤔 문제분석 다이나믹 프로그래밍 현재의 추를 왼쪽으로 둔경우와, 오른쪽에 둔 경우 모두 갱신..
[이것이코딩테스트다] 1로 만들기 📄 문제개요 정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지 이다. X가 5로 나누어 떨어지면 5로 나눈다. X가 3으로 나누어 떨어지면 3으로 나눈다. X가 2로 나누어 떨어지면 2로 나눈다. X에서 1을 뺀다. 정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만드려고 한다. 연산을 사용하는 횟수의 최소값을 출력하시오. 🤔 문제분석 다이나믹 프로그래밍 문제이다. 특정 숫자에서 5로 나누었을때, 3으로 나누었을때, 2로 나누었을때, 1을 뺏을때 중 최적의 경로가 정답이 된다. X의 숫자가 주어지고, 탑다운 방식으로 5로 나누었을때, 3으로 나누었을때, 2로 나누었을때, 1로 뺐을때 중 으로 분기시켜, X가 1이 되었을때, 가장 연산이 작은 것을 골라서 정답을 도출 할..
[백준] 2866번 : 문자열 잘라내기 2866번: 문자열 잘라내기 2866번: 문자열 잘라내기 첫 번째 줄에는 테이블의 행의 개수와 열의 개수인 R과 C가 주어진다. (2 ≤ R, C ≤ 1000) 이후 R줄에 걸쳐서 C개의 알파벳 소문자가 주어진다. 가장 처음에 주어지는 테이블에는 열을 읽어서 문자 www.acmicpc.net 📄 문제개요 R개의 행과 C개의 열로 주어진 테이블이 입력으로 주어진다. 이 테이블의 원소는 알파벳 소문자이다. 각테이블의 열을 위에서 아래로 읽어서 하나의 문자열로 만들 수 있다. 2 ≤ R, C ≤ 1000 🤔 문제분석 문자는 최대 1000개와 문자의 길이는 1000을 갖을 수 있다. 완전탐색의 경우 최악의 경우 O($N^3$)이다. 최악의 경우 1000번 반복하는데, 모든 문자의 중복을 확인( 1000 * 10..
[백준] 1920번 : 수 찾기 1920번: 수 찾기 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 📄 문제개요 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. M개의 쿼리가 주어졌을때 해당 쿼리가 존재하면 1 존재하지 않으면 0을 출력하시오. 1≤ N ≤ 100,000, 1 ≤ M ≤ 100,000 -2^31 ≤ A[i] ≤ 2^31 🤔 문제분석 O(N*M)으로 완전탐색으로 해당값이 있는지 탐색 할 수 있다..

티스토리툴바