함께 스터디7 [PS스터디 심화반] 4주차 백준 로봇 청소기 개요 이번 문제도 삼성의 기출문제라고 합니다. https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 리뷰와 피드백 구현을 요구하는 문제였기에 크게 특별한 발상을 요구하지는 않았지만 현재 봐라보는 방향에서의 회전 위치를 배열에 담고 해당 배열을 문제조건에 맞게 구현하는 식을 찾아내는게 조금 특별한 발상이였다고 생각합니다. 다른 부분은 크게 특별한 것 없이 문제에서 요구하는 사항을 따라 작성하였고 다른 분들의 코드도 크게 다르지 않았습니다만 문제에서 .. 2022. 8. 1. [PS스터디 심화반] 4주차 백준 감시 개요 삼성 역량테스트의 기출 문제이며, 취준을 앞둔 입장으로 도움이 될 것 같아 선정하였습니다 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 리뷰와 피드백 큰 아이디어가 필요하다니 보단 단순 구현을 요구하는 문제 였습니다. 다만 그 범위가 넓으며, 요구하는 사항들 사이에 언듯 비슷한 부분이 많아 어떻게 모듈화하여 줄일 수 없을까란 생각에 빠지게되어 문제의 난이도가 더 높게 느껴진 문제입니다. 저는 해당 문제를 vector 컨테이너를.. 2022. 8. 1. [PS스터디 심화반] 3주차 백준 외판원 순회 개요 저희 스터디에 폭풍을 불어온 문제입니다. 개인적으로는 저희 스터디의 분기점이 된 문제라고 생각드네요. https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 리뷰와 피드백 DP문제의 난이도에 있어서 명성 익히 알며, 외판원 순회 문제가 어떠한 문제인 줄도 들어봤습니다. 저희 스터디의 한 두 명을 제외하곤 혼자서 푸는 것을 포기하였습니다. 외판원 순회 문제는 비트마스킹과 DP를 사용하는 어느정도 템플릿 같은 형.. 2022. 8. 1. [PS스터디 심화반] 3주차 백준 소수의 연속합 개요 소수를 이용하며 연속적인 합을 구하는 문제입니다. https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 리뷰와 피드백 이번 문제에서는 소수를 구하는 부분과 연속적인 합을 구하는 부분 두 가지로 나눌 수 있었습니다. 먼저 처음 소수를 구하는 부분에서의 방법이 두 가지로 나눠졌었는데, 루트N의 시간복잡도로 각 소수들을 구하려하니 주어진 시간 제한 안에 들어올꺼란 확신이 들지 않았습니다. 그래서 에라스토테네스의 체를 이용해 NlglgN의 시간복잡도에 소수들을 구하였습니다. ( 전자의 방식으로도 통과되었습니다. 하지만 후자가 훨씬 빨랐네요 ) 이후 각 소수들의 연속적인 .. 2022. 8. 1. [PS스터디 심화반] 2주차 백준 보석도둑 개요 적지 않은 사람들이 갈려나간 문제입니다. 저번 문제에서도 나온 이야기지만 문제를 해석하고 제대로 이해하는 것이 PS를 함에 있어서 정말 중요한 것이라는 것을 다시 한 번 느낄 수 있었습니다. https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 리뷰와 피드백 이번 문제는 문제의 특성 상 그리디적인 접근과 우선순위 큐를 활용하는 문제였습니다. 주어진 시간을 고려하였을 떄 거의 이 방식을.. 2022. 8. 1. [PS스터디 심화반] 1주차 백준 거짓말 개요 이번 문제는 백준의 거짓말 문제입니다. https://www.acmicpc.net/problem/1043 리뷰와 피드백 문제 자체를 이해함에 있어서 다들 해매었습니다. 뒤에 나온 파티의 내용이 먼저 나온 파티에 영향을 끼치기 때문에 이러한 부분을 잡아내지 못하는 경우가 있었습니다. 다들 각자만의 방법으로 구현을 하였고 서로의 코드에 다른 부분은 있었지만, 성능 상이나 가독성적인 부분에서도 큰 문제는 없어 문제를 풀어보았다는 부분에 의의를 두었습니다. 개선 전 / 후 코드 전문 #include #include using namespace std; int n, m, known; int main() { cin >> n >> m >> known; vector partys(m); // 파티 별 참가인원을 저.. 2022. 8. 1. [PS스터디 심화반] 1주차 백준 멀티탭 스케줄링 개요 나흘 전 스터디원들은 멀티탭 스케줄링 문제를 나흘 뒤 오늘까지 (새벽에 작성 중이라 어제가 맞습니다) 문제를 해결하고 서로의 코드를 보며 리뷰하기러 하였습니다. https://www.acmicpc.net/problem/1700 리뷰와 피드백 해당 문제를 해결하는 과정에서 큰 줄기는 비슷하지만 잦은 잎에서는 조금씩 차이가 있었습니다. 스터디원 중에서는 큐를 사용하여 인접 전자기기들을 다룬 경우도 있고 제가 쓴 코드와는 다르게 멀티탭 초기화부와 이후에 순서를 진행할 반복문을 결합시킨 경우도 있었습니다. 그리고 스터디활동에 따라 서로에게 코드를 보여주고 설명해야하니 자세한 주석이나 스타일 등에 신경을 써야할 것 같다는 이야기가 나왔습니다. 개선안 아무래도 저는 입력을 받는 부분과 멀티탭 초기화 부분을 같.. 2022. 7. 8. 이전 1 다음