🔗문제 보러가기 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N (1 ≤ N ≤ 1000)개가 주어진다. 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 정 www.acmicpc.net 👨‍💻풀이 과정 메이플스토리 개미굴이 생각나는 문제였습니다. 트라이(Trie) 자료구조를 활용해서 풀 수 있었는데, 트라이와 관련된 코드를 작성하는 게 익숙하지 않아 조금 오래 걸렸습니다. 같은 층에 여러 개의 방이 있을 경우에는 사전순으로 먹이 정보를 출력해야 하기에 map을 활용하여 트라이를 구현하였습니다. class Trie { public: Trie(int depth) : depth(depth) { } ~Trie(); vo..

🔗문제 보러가기 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 👨‍💻풀이 과정 2부터 N까지 소수를 구하는 "에라토스테네스의 체" 알고리즘 1번에서 구한 소수들의 누적합을 저장해 둔 배열 투 포인터를 사용하여 부분 구간을 이동해가며, N이 나오는 구간의 개수를 카운트 위 순서대로 저는 문제를 풀었습니다. 투 포인터와 관련된 소스 코드는 많이 작성해보지 않아서 그런지, 짜는 데에 조금 시간이 걸리네요. ✏️소스 코드 및 결과 #include #include using namespace std; #define FAST_IO ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL); ..

🔗문제 보러가기 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 👨‍💻풀이 과정 내부 공기와 외부 공기를 어떻게 구별할까 고민했습니다. 문득 떠오른 생각은 다각형 외부 내부 판별 알고리즘이었는데, 치즈가 다각형이 아닐 수도 있기 때문에 적용할 수가 없더라구요. 그래서 문제에서 주어진 정보인, "가장자리에는 치즈가 놓이지 않는다"라는 걸 활용해 가장자리에서부터 BFS를 통해 외부 공기를 만들어주기로 결정하였습니다. 이 로직을 위해, 입력 세팅을 할 때 조금 다르게 세팅해주었습니다. // 전역 변수들..

🔗문제 보러가기 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 👨‍💻풀이 과정 BFS로 코드를 작성했지만 17%에서 자꾸 틀렸는데, 반례를 도무지 모르겠어서 다른 분들 코드를 약간 참고했습니다. 참고해보니, 제가 간과한 사실들이 있었습니다. 고슴도치의 시작 위치는 여러 개일 수 있다. 매 분마다 주어진 물의 위치들을 모두 확장하지 않고, 하나만 확장했다. 이 부분들만 고쳐서 다시 제출하니 통과할 수 있었습니다. 다음에는 조금 더 신경써야겠네요. ✏️소스 코드 및 결과 #include #include #include #i..

🔗문제 보러가기 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 👨‍💻풀이 과정 세그먼트 트리(Segment Tree) 첫 입문 문제로 풀었습니다. 첫 시도고, 조금 변형된 문제인지라 결국 다른 분들의 풀이를 참고하여 풀었지만, 세그먼트 트리라는 개념과 어느정도 친숙해진 그런 계기가 아니었나 싶습니다. 백준 문제를 풀면서 느낀 거지만, 다양한 알고리즘 문제들을 접해볼 수 있다는 게 되게 좋은 것 같습니다. 아직 접해보고 풀어봐야 할 문제들이 많지만 하나씩 천천히 해봐야죠...

🔗문제 보러가기 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 👨‍💻풀이 과정 위상 정렬과 다이나믹 프로그래밍을 통해 풀었습니다. 처음에는 DFS로 풀 수 있을 것 같단 생각에 도전하려고 했는데, 중복되는 계산이 너무 많아 시간 초과가 날 것 같단 생각이 들어 그 풀이는 포기했습니다. 아무튼, 제가 어떻게 풀었는지 천천히 설명해 드리도록 하겠습니다. 1. 간선 정보 및 진입 차수 설정 하위 부품에서 상위 부품으로 간선이 가리키도록 방향을 설정하였고, 필요한 부품 개수 정보도 같이 ..