본문 바로가기

PS(Problem Solving)/백준_BOJ201

[백준] 11365번 - !밀비 급일 (C++) 문제 및 풀이 문제) 백준 - 문자열 - !밀비 급일 https://www.acmicpc.net/problem/11365 11365번: !밀비 급일 당신은 길을 가다가 이상한 쪽지를 발견했다. 그 쪽지에는 암호가 적혀 있었는데, 똑똑한 당신은 암호가 뒤집으면 해독된다는 것을 발견했다. 이 암호를 해독하는 프로그램을 작성하시오. www.acmicpc.net 문자열을 차례대로 입력 받아 역순으로 출력합니다. C++ 소스 코드) 2022. 2. 3.
[백준] 7511번 - 소셜 네트워킹 어플리케이션 (C++) 문제 및 풀이 문제) 백준 - 분리 집합 - 소셜 네트워킹 어플리케이션 https://www.acmicpc.net/problem/7511 7511번: 소셜 네트워킹 어플리케이션 각 테스트 케이스마다 "Scenario i:"를 출력한다. i는 테스트 케이스 번호이며, 1부터 시작한다. 그 다음, 각각의 쌍마다 두 사람을 연결하는 경로가 있으면 1, 없으면 0을 출력한다. 각 테스트 케이스 www.acmicpc.net 친구 두 명이 주어질 때, 서로 친구인지 확인해야 됩니다. 쿼리 최대 개수가 10만이기에 각 쿼리를 O(1)의 시간 복잡도로 해결할 수 있는 분리 집합(Union-Find)을 활용하여 해결했습니다. Merge(Union)와 Find는 O(N)이므로 N이 100만이여도 해결할 수 있습니다. C++ 소스코드) .. 2022. 1. 30.
[백준] 16507번 - 어두운 건 무서워 (C++) 문제 및 풀이 문제) 백준 - 누적 합 - 어두운 건 무서워 https://www.acmicpc.net/problem/16507 16507번: 어두운 건 무서워 첫 번째 줄에는 사진의 크기를 의미하는 정수 R, C (1 ≤ R, C ≤ 1,000)와 사진 일부분의 밝기 평균을 알아볼 개수를 의미하는 정수 Q (1 ≤ Q ≤ 10,000)가 주어진다. 다음 R개의 줄에 걸쳐 R×C 크기의 사 www.acmicpc.net 쿼리(Q)의 최대 개수가 10000이고 R과 C의 최대가 1000이기에 매번 합을 탐색하면 O(Q*R*C)의 시간 복잡도로 해결할 수 없습니다. 따라서, 사진의 크기의 합을 미리 저장해 좌표가 주어지면 O(1) 안에 쿼리를 처리할 수 있는 누적합을 이용해 해결해야 했습니다. C++ 소스코드) Full C.. 2022. 1. 29.
[백준] 14467 - 소가 길을 건너간 이유 1 (C++) 문제 및 풀이 문제) 백준 - 구현 - 소가 길을 건너간 이유 1 https://www.acmicpc.net/problem/14467 14467번: 소가 길을 건너간 이유 1 3번 소는 위치 1, 0, 1에서 관찰되었으므로 길을 최소 두 번 건넜음을 확인할 수 있다. 4번 소도 길을 한 번 건넜으며, 나머지 소는 길을 건넌 기록이 확인되지 않는다. www.acmicpc.net 간단한 구현 문제였습니다. cows배열을 -1(관측 X)로 초기화 후에 어떤 소가 관측이 되면 0 또는 1을 저장합니다. 그 후, 관측이 될 시에 cows배열을 갱신하고 ans++을 합니다. C++ 소스코드) 2022. 1. 29.
[백준] 22942번 - 데이터 체커 (C++) 문제 및 풀이 문제) 백준 - 자료 구조 - 데이터 체커 https://www.acmicpc.net/problem/22942 22942번: 데이터 체커 데이터가 조건에 맞는다면 YES, 조건에 만족하지 않는다면 NO를 출력한다. www.acmicpc.net N의 최댓값이 20만이기 때문에 완전 탐색 시 TLE로 틀려서, 한참 고민했습니다. 쉬운 방법이 도저히 안 떠올라 SegTree로 구현하려다 알고리즘 분류를 보니, 자료구조임을 보고 올바른 괄호 문제의 아이디어가 떠올라 그것을 활용해 해결했습니다. 원의 x좌표(val), 원의 오른쪽/왼쪽 판별(isOpen), 인덱스(idx)를 변수로 가지는 구조체를 활용하여 x좌표를 기준으로 정렬 후 스택을 이용해 원의 교점을 확인합니다. C++ 소스코드) 2022. 1. 29.
[백준] 17128번 - 소가 정보섬에 올라온 이유 (C++) 문제 및 풀이 문제) 백준 - 수학 - 소가 정보섬에 올라온 이유 https://www.acmicpc.net/problem/17128 17128번: 소가 정보섬에 올라온 이유 첫째 줄에 소의 수를 나타내는 N과 욱제가 장난칠 횟수 Q가 주어진다. (4 ≤ N ≤ 200,000, 1 ≤ Q ≤ 200,000) 둘째 줄에 N마리 소들의 품질 점수 Ai가 순서대로 주어진다. (1 ≤ |Ai| ≤ 10) 셋째 줄에 www.acmicpc.net Brute Force(완전 탐색)으로 해결할 시, N이 최대 20만이기 때문에 TLE로 틀립니다. parSum[idx] : idx부터 4마리 소들의 품질 점수의 곱 idx(i) : 인덱스 처리 함수 ans : 쿼리 후 품질 점수 부분합을 저장하여 쿼리로 소의 품질점수가 Update될때마.. 2022. 1. 28.
[백준] 11256번 - 사탕 (C++) 문제 및 풀이 문제) 백준 - 그리디 알고리즘 - 사탕 https://www.acmicpc.net/problem/11256 11256번: 사탕 당신은 사탕 공장의 주인이다. 날마다, 당신은 J개의 사탕을 가게에 보내기 위해 상자에 포장해야 한다. 당신은 크기가 다른 상자 N개를 가지고 있다. 당신은 편리를 위해 상자를 최소한으로 쓰 www.acmicpc.net 상자의 최소 개수를 구하는 문제였습니다. 상자의 용량을 기준으로 내림차순으로 정렬합니다. J개의 사탕을 상자에 채우면서 상자의 개수를 세어줍니다. C++ 소스코드) 2022. 1. 26.
[백준] 17829번 - 222-풀링 (C++) 문제 및 풀이 문제) 백준 - 분할 정복 - 222-풀링 https://www.acmicpc.net/problem/17829 17829번: 222-풀링 조기 졸업을 꿈꾸는 종욱이는 요즘 핫한 딥러닝을 공부하던 중, 이미지 처리에 흔히 쓰이는 합성곱 신경망(Convolutional Neural Network, CNN)의 풀링 연산에 영감을 받아 자신만의 풀링을 만들고 이를 22 www.acmicpc.net solve 함수의 분할 정복을 통해 해결했습니다. solve(int sr, int er, int sc, int ec)의 역할은 행 sr부터 er, 열 sc부터 ec까지의 숫자 중에서 2번째로 큰 수를 뽑아내는 역할을 합니다. 인덱스 범위에서 4등분을 한 후, res벡터에 넣은 후 정렬을 통해 2번째로 큰 수를 반환합니.. 2022. 1. 25.
[백준] 1474번 - 밑 줄 (C++) 문제 및 풀이 문제) 백준 - 그리디 알고리즘 - 밑 줄 https://www.acmicpc.net/problem/1474 1474번: 밑 줄 세준이는 N개의 영어 단어를 이용해 길이가 M인 새로운 단어를 만들려고 한다. 새로운 단어는 N개의 단어를 순서대로 이어 붙이고, 각 단어의 사이에 _을 넣어서 만든다. 이렇게 만든 새로운 단어 www.acmicpc.net 사전 순으로 가장 빠른 것을 출력하기 위해 알파벳과 밑 줄의 우선순위를 이해해야 합니다. 밑 줄의 순서가 'A' < 'B' < 'C' < ... < 'Z' < '_' < 'a' < 'b' < 'c' < ... < 'z' 이므로 소문자보다는 밑 줄이 먼저 와야 합니다. 따라서 단어 사이에 균등하게 넣을 밑 줄을 계산하고, 남은 빈칸(redBlank)이 0 이상.. 2022. 1. 25.
반응형

티스토리툴바