본문 바로가기

반응형

PS

[BOJ 2672] 여러 직사각형의 전체 면적 구하기 [문제] www.acmicpc.net/problem/2672 2672번: 여러 직사각형의 전체 면적 구하기 첫째 줄에 직사각형의 개수 N(1 ≤ N ≤ 30)이 주어지고 그 다음 N줄에는 각각의 직사각형에 대한 자료가 주어진다. 이 자료는 4개의 숫자로 표시되는데 첫째, 둘째 숫자는 직사각형의 왼쪽 아래 모 www.acmicpc.net [필요 개념] - 스위핑 (Sweeping) [난이도] - Gold 2 (solved.ac 20.10.29 기준) [풀이] N의 크기가 작아서 여러 풀이 방법이 가능하지만, 대체로 이런 유형은 '스위핑'으로 풀리는 경우가 많다. 우선, 주어지는 입력이 조금 특이한데 알고 보면 크게 다르지 않다. 각 사각형의 왼쪽 아래 꼭짓점의 좌표와 사각형의 폭, 높이가 소수로 주어진다...
완전 탐색 (Brute-Force Search / Exhaustive Search) 알고리즘 1. 완전 탐색이란? 컴퓨터의 빠른 계산 능력을 이용하여 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미한다. '무식하게 푼다'라는 의미인 Brute-Force (브루트 포스)라고도 부른다. 이름이 거창하게 지어져 있지만 사실 완전 탐색 자체로는 알고리즘이라고 부르긴 그렇고, 문제 푸는'방법'이라고 이해하면 편할 것 같다. 알고리즘을 모르는 사람이 프로그래밍 문제를 푼다면, 당연히 가능한 모든 경우들을 다 구해서 그중에 만족하는 답을 찾아낼 것이고 이 과정 자체가 완전 탐색이다. 대신에 이 방식은 절대 답을 못 구하는 경우는 없으므로 나름 강력한 방법이다. 예를 한번 들어보자. "10개의 정수 원소로 이루어진 수열이 있다. 이 수열에서 두 원소를 선택해서 구한 합의 최댓값을 구하시오. " 이..
SUAPC 2020 Div.1 참가 후기 SUAPC (신촌지역 대학생 프로그래밍 대회 동아리 연합 여름 대회) 2020 Div.1에 참가하였다. 팀명 : 처음보는사람들끼리신청마감1시간전에만든팀 팀원 : pjh6792(나) , dart , seastar105 신촌지역의 대학교(연세대, 서강대, 홍대, 이대, 숙대)들이 연합해서 개최한 대회이며, div1에는 총 29팀이 참여했다고 한다. 본격적으로 알고리즘을 공부한 지 약 4달째만에 처음으로 실전 대회를 참여하게 되었는데, 정말 열악한 환경 속에서 참가했다. 우선, 3명 다 모두 초면이었고 대회 신청 마감 직전에 팀을 모아서 신청하게 되었다. (팀 이름의 유래다...) 사실 원래는 어차피 서울에도 가지 못하고, 개인적인 테스트 겸 대회를 참가하려 해서 1 인팀으로 신청을 했었다. 물론 다들 ICP..