본문 바로가기

Algorithm197

[백준 4179] 불! 4179번: 불! (acmicpc.net) 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 배운것 불, 지훈이에 대한 BFS를 각각 모두 돌려준 후 비교한다 정답코드 // Authored by : BaaaaaaaaaaarkingDog // Co-authored by : - // http://boj.kr/aed4ec552d844acd8853111179d5775d #include using namespace std; #define X first #define Y second string board[.. 2022. 8. 29.
[백준 1926] 그림 1926번: 그림 (acmicpc.net) 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 내 풀이 #include using namespace std; int n, m; int a[502][502]; bool check[502][502]; int dx[] = { 0, 0, 1, -1 }; int dy[] = { 1, -1, 0, 0 }; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (int i = 0; i < n; i++) { for .. 2022. 8. 19.
[백준 2504] 괄호의 값 2504번: 괄호의 값 (acmicpc.net) 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 배운 것 괄호만 있는 것이 아니라 숫자도 있어서 새로 stack을 만들어줘야 하나 고민했는데 그럴 필요 없이 sum이랑 num이란 변수를 만들어줘서 push시켜줄 때 num에 곱해줄 숫자 기록하면 됨 정답 코드 // Authored by : std-freejia // Co-authored by : BaaaaaaaaaaarkingDog // http://boj.kr/cbef82389d1048db80c9652d18b.. 2022. 8. 17.
[백준 10799] 쇠막대기 10799번: 쇠막대기 (acmicpc.net) 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 배운 것 괄호 문제에서는 케이스 분류가 중요한 듯 여기에서는 )가 레이저일 경우, 막대의 끝일 경우를 나눠서 생각한다 정답 코드 // Authored by : BueVonHun // Co-authored by : BaaaaaaaaaaarkingDog // http://boj.kr/0e7137cb9b634cbcad7683ad783d432c #include typedef long long ll; using namespace std.. 2022. 8. 17.
[실전 알고리즘] 스택의 활용(수식의 괄호 쌍) 수식의 괄호 쌍이란? 수식의 괄호 쌍: 주어진 괄호 문자열이 올바른지 판단하는 문제 문제 해결을 위한 관찰 문제 해결 방법 1. 여는 괄호가 나오면 스택에 추가 2. 닫는 괄호가 나왔을 경우, 2-1. 스택이 비어있으면 올바르지 않은 괄호쌍 2-2. 스택의 top이 짝이 맞지 않는 괄호일 경우 올바르지 않은 괄호 쌍 2-3. 스택의 top이 짝이 맞는 괄호일 경우 pop 3. 모든 과정을 끝낸 후 스택에 괄호가 남아있으면 올바르지 않은 괄호 쌍, 남아있지 않으면 올바른 괄호 쌍 연습문제 4949번: 균형잡힌 세상 (acmicpc.net) 정답 코드 #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); while(tr.. 2022. 8. 15.
[실전 알고리즘] 덱 정의와 성질 덱: 양쪽 끝에서 삽입과 삭제가 전부 가능한 자료구조 Double Ended Queue. 덱의 성질 1. 원소의 추가와 제거가 모두 O(1) 2. 제일 앞/뒤의 원소 확인이 O(1) 3. 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 기능과 구현 1. 배열로 구현 #include using namespace std; const int MX = 1000005; int dat[2*MX+1]; int head = MX, tail = MX; void push_front(int x){ dat[--head] = x; } void push_back(int x){ dat[tail++] = x; } void pop_front(){ head++; } void pop_back(){ tail--.. 2022. 8. 13.