본문 바로가기

Algorithm/Implementation

 (751)
(C++) - 백준(BOJ) 17608번 : 막대기 답 www.acmicpc.net/problem/17608 17608번: 막대기 아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 www.acmicpc.net 간단한 구현 문제였습니다. 풀이방법 오른쪽에서 봤을 때 가장 앞 원소는 오른쪽 끝에 있는 막대기고 이 막대기의 높이만큼 나머지 막대기를 볼 시야를 가리고 있습니다. 따라서 보이는 막대기의 수는 무조건 오른쪽 막대기부터 시작하여 높이를 확인해가면서 왼쪽 막대기를 보고, 오른쪽 막대기보다 왼쪽 막대기가 더 크다면 이 왼쪽 막대기는 보인다고 할 수 있습니다. 그렇다면 오른쪽 막대기부터 시작해 왼쪽 막대기로 순차적으로가며 ..
(C++) - 백준(BOJ) 5430번 : AC 답 www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net deque 자료구조를 사용해 푸는 문제였습니다. 풀이방법 1. 문자열로 부터 수를 적절히 parsing하여 deque에 저장 2. R이 짝수만큼 입력이라면 이후에 D가 나올 경우 좌측부터 우측순으로 지워지게 됨. 반대의 경우에는 우측에서 좌측순으로 지워짐. 그 방식으로 D가 나올때마다 순서에 맞게 지워나감. 지울 때 이미 deque의 size가 0이라면 error출력 3. D를 모두 수행했을 때 원소가 없으면 빈 배열인 []를 출력. Code #include #inc..
(C++) - 백준(BOJ) 1992번 : 쿼드트리 답 www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 www.acmicpc.net 재귀를 이용한 문제였습니다. 풀이방법 1.압축할 수 있으면 : ans+='(', 압축 진행, ans += ')' 2. 압축할 수 없으면 영역에 따라 0또는 1을 ans에 추가 Code #include #include using namespace std; int n; int video[64][64]; string tmpVideo[64]; string ans; bool haveToBePressed(in..
(C++) - 백준(BOJ) 18870번 : 좌표 압축 답 www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 구현을 해보는 문제였습니다. 문제의 조건이 수식으로 되어있어서 좀 헷갈렸던 것 같습니다. ㅋㅋㅋ 좌표를 압축한다 : 해당 좌표의 값을 그 값보다 작은 좌표값들의 개수로 대체한다의 의미입니다. 풀이방법 1. 매 좌표마다 값,index를 vector pair형태로 저장한다. 2. 값을 기준으로(vector.first) 오름차순 정렬 3. 오름차순 정렬된 상태에서 답..
(C++) - 백준(BOJ) 1780번 : 종이의 개수 답 www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net 9부분으로 나누어 종이의 개수를 파악할 때 반복되는 부분에 대해 재귀로 구현했습니다. 풀이방법 n = 9일 때 3*3짜리 정사각형 또는 1*1짜리 정사각형으로 종이를 나누어 볼 수 있습니다. 이럴 경우 가로를 3등분 세로를 3등 분하며 계속 종이를 세기 때문에 원래의 영역에서 9등분씩 나누어지게 됩니다. 따라서 이 9부분에 대해 종이인지 아닌지 판별한 후 종이가 아니라면 다시 현재 영역에 대해 9등분..
(C++) - 백준(BOJ) 2630번 : 색종이 만들기 답 www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 재귀를 이용해 푸는 문제였습니다. 풀이방법 면적이 다른 색인 색종이가 나오면 2로 계속 나누고 면적이 같다면 파란색인지 흰색인지 판별하여 답을 구하는 문제였습니다. Code #include using namespace std; int paper[130][130]; int n; int whiteNum; int blueNum; bool isSameColor(int i, int j, int..
(C++) - 백준(BOJ) 1927번 : 최소 힙 답 www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이� www.acmicpc.net 힙(heap)자료구조를 사용하는 우선순위 큐(priority queue)를 사용하는 문제였습니다. 풀이방법 default가 less(내림차순 정렬, top은 현재 heap 중 가장 큰 값 즉 max heap) 이므로 greater옵션을 주어 min heap으로 바꾸어준 뒤 조건에 맞게 출력해주면 됩니다. Code #include #include #define fastio ios_base::syn..
(C++) - 백준(BOJ) 1620번 : 나는야 포켓몬 마스터 이다솜 답 www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net map자료구조와 vector자료구조를 사용해보는 간단한 문제였습니다. 풀이방법 map자료구조에서 c++의 경우에는 value로부터 key를 추출하는 내장함수가 딱히 없어 vector자료구조를 이용했습니다. 1. 도감의 번호에 해당하는 포켓몬이름을 해당 자료구조에 저장했습니다. 2. 도감의 번호에 해당하는 포켓몬이름이 주어질 경우 map의 value를 출력하도록 했고 반대로 도감의 포..

티스토리툴바