본문 바로가기

전체 글

 (328)
[백준] 5676번 : 음주코딩 5676번: 음주 코딩 5676번: 음주 코딩 각 테스트 케이스마다 곱셈 명령의 결과를 한 줄에 모두 출력하면 된다. 출력하는 i번째 문자는 i번째 곱셈 명령의 결과이다. 양수인 경우에는 +, 음수인 경우에는 -, 영인 경우에는 0을 출력한다. www.acmicpc.net 📄 문제개요 구간곱을 구하는 문제로 쿼리의 개수가 10^5개로 N의 개수가 매우 크다면, 일반적인 쿼리로 문제를 해결 할 수 없습니다. “팬윅트리” 혹은 **“세그먼트 트리”**를 이용하여 문제를 해결 할 수 있습니다. 수열이 주어졌을때, 해당 곱이 “양수”인지 “음수”인지 “0”인지 판별해야합니다. 🤔 문제분석 세그먼트 트리로 문제 풀기. 세그먼트 트리로 문제를 풀경우 메모리는 최소 2^(log(N)+1), 최대 4N의 배열이 필요합..
[백준] 18500번 : 미네랄 2 18500번: 미네랄 2 18500번: 미네랄 2 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 📄 문제개요 창영이와 상근이는 양쪽에서 화살을 날려 미네랄를 부순다. 미네랄을 부수면 땅과 연결되지 않는 클러스터는 모양을 유지한 상태로 땅이나, 다른 미네랄 혹은 클러스터에 떨어진다. 주어진 창을 던지는 횟수와 높이가 주어졌을때, 최후의 미네랄의 모양을 출력하라. 🤔 문제분석 R, C, N 이 100 이하 이기때문에 정확한 문제 분석과 알고리즘 작성이 문제의 Key Point 라고 생각한다. 주어진 창의 횟수가 높이가 주어졌을때 미네랄을 부수는..
[백준] 2637번 : 장난감조립 2637번: 장난감 조립 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 📄 문제개요 장난감을 조립하기위하여 장난감의 의존성을 정의되어있는 테이블이 주어진다. 장난감은 N개의 기본부품과 중간부품으로 나누어 지는데 마지막 N번째의 부품의 기본부품의 개수를 구하는 문제이다. 기본부품은 다른 부품으로 조립 할 수 없는 부품이고, 중간부품은 아래와 같이 구성 될 수 있다. 중간부품 + 기본부품 기본부품 + 기본부품 중간부품 + 중간부품 🤔 문제분석 해당문제는 만약 5번부품의 기본부품의 개수..
[백준] 19238번 : 스타트 택시 19238번: 스타트 택시 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 📄 문제개요 택시와 손님이 존재할때, 택시의기름으로 손님을 목적지까지 운송합니다. 운송할때에 기름이 바닥나면 게임이 종료되고, 기름이 바닥나지않고 손님을 목적지까지 운송을 완료하면 택시의 기름은 손님을 운송할때 쓰인 기름 비용의 2배가 됩니다. 모든 손님을 옮긴뒤에, 택시의 기름양을 출력한다. ( 만약, 모든 손님을 이동 할 수 없다면 -1을 출력한다. ) 🤔 문제분석 손님은 집합자료형 자료구조로 ..
[백준] 16235번 : 나무 재테크 16235번: 나무 재테크 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 📄 문제개요 봄 : 나무의 나이가 가장 작은 순서부터, 자신의 나이만큼 양분을 먹는다. 양분을 먹은 나무는 나이가 1 증가한다. 양분을 먹을 수 없는 나무는 즉시 죽는다. 여름 : 죽은 나무가 양분으로 변한다. 죽은 나무마다 나이를 2로 나눈값이 나무가 있던 칸에 양분으로 추가된다. 가을 : 나무가 번식한다. 번식하는 나무는 나이가 5의 배수이며, 인접한 8개의 칸에 나이가 1인 나무가 생긴다. 겨울 : 양분을 추가한다...
[백준] 11054번 : 가장 긴 바이토닉 부분 수열 11054번: 가장 긴 바이토닉 부분 수열 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 📄 문제개요 연속된 가장 긴 바이토닉 수열을 구하는 문제이다. 🤔 문제분석 다이나믹 프로그래밍 문제로, 현재 인덱스로부터 증가하는 가장 긴 값을 갱신한다. 처음부터 끝까지 순회하면서, 현재 인덱스로부터 가장 증가하는 긴 값을 dp 배열에 넣는다. 뒤집어서 한번더 증가하닌 긴 값을 dp 배열에 넣는다. 📝 의사코드 수열을 순회하면서, 증가하는 수열의 정보를 갱신한다. 수열을 반대로 뒤집어, 증가하는 수열의 정보를 갱신한다. 2개의 dp 테이블..
[백준] 17472번 : 다리만들기 2 17472번: 다리 만들기 2 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 📄 문제개요 섬과 바다가 주어지고, 주어진 조건에따라서 섬을 연결 할 수 있다고 할 때, 섬을 연결 할 수 있는 최소 길이를 구하여라, 연결하지 못한다면 -1을 출력하여라. 🤔 문제분석 탐색과 그래프 문제입니다. BFS 탐색으로 섬을 그룹핑 한다. 해당 그룹에서 또다른 그룹 까지의 거리를 구한다. 해당그룹에서 또다른그룹까지의 거리를 가장 짧은 거리순으로 연결해본다 ( 최소신장트리 ) 📝 의사코드 BFS 탐색으로 ..
[백준] 1035번 : 조각움직이기 1035번: 조각 움직이기 1035번: 조각 움직이기 최대 5개의 조각이 있는 5×5 크기의 보드가 있다. 김지민은 조각을 적절히 움직여서 모든 조각이 연결 요소를 이루게 하려고 한다. 즉 상하좌우로 인접한 조각을 모두 연결했을 때, 모든 쌍의 조 www.acmicpc.net 📄 문제개요 5x5 크기의 보드가 주어졌을때, 모든 조각을 움직여서 연결 요소를 만드려고 한다. 조각을 최소로 움직여서 연결요소를 만들 수 있는 값을 구하시오. 🤔 문제분석 문제의 범위가 5x5이니, 완전탐색으로 문제를 접근해야한다. 우선은 연결요소가 될 수 있는 모든 경우의 수를 구한다. 연결요소를 순열로 현재 peice와 거리 계산을 하여 최소값을 갱신한다. 📝 의사코드 별의 개수로 만들 수 있는 모든 조합의 경우의 수를 구한다..

티스토리툴바