본문 바로가기
반응형

알고리즘

[BOJ 5821] 쌀 창고 [문제] www.acmicpc.net/problem/5821 5821번: 쌀 창고 첫째 줄에 R, L, B가 주어진다. 둘째 줄부터 R개 줄에는 X[i]가 주어진다. (1 ≤ R ≤ 100,000, 1 ≤ L ≤ 1,000,000,000, 0 ≤ B ≤ 2,000,000,000,000,000) www.acmicpc.net [난이도] - Platinum 4 (solved.ac 20.10.29 기준) [필요 개념] - 이분 탐색 (Binary Search) - 누적 합 (Prefix Sum) [풀이] 각 논들이 일직선상에 주어져 있고, 해당 논을 수확하기 위해서는 쌀 창고와의 거리만큼 비용이 필요하다. 지불할 수 있는 비용 한도가 정해져 있고, 한도 내에서 쌀 창고의 위치를 잘 정해줘서 수확할 수 있는 최대..
[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의 크기가 작아서 여러 풀이 방법이 가능하지만, 대체로 이런 유형은 '스위핑'으로 풀리는 경우가 많다. 우선, 주어지는 입력이 조금 특이한데 알고 보면 크게 다르지 않다. 각 사각형의 왼쪽 아래 꼭짓점의 좌표와 사각형의 폭, 높이가 소수로 주어진다...
비트마스크 (BitMask) 알고리즘 [목차] 1. 비트마스크(BitMask)란? 2. 비트마스크의 장점 3. 비트 연산자 4. 비트마스크를 이용한 집합 구현 * 종만북에 잘 설명되어 있어 기본적으로 종만북의 설명을 따릅니다. 1. 비트마스크(BitMask)란? - 비트마스크(BitMask)는 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 기법을 말한다. - 이진수는 0 또는 1을 이용하므로 하나의 비트(bit)가 표현할 수 있는 경우는 두 가지이다. - 보통 어떤 비트가 1이면 "켜져 있다"라고 말하며, 0이면 "꺼져 있다"라고 말한다. 2. 비트마스크의 장점 비트마스크는 크게 어려운 개념이 아니며, 이 개념을 알고 있다면 매우 유용한 경우가 꽤나 있다. 비트마스크의 장점들은 다음과 같다. 1. ..
완전 탐색 (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..
[BOJ 2336] 굉장한 학생 [문제] : https://www.acmicpc.net/problem/2336 2336번: 굉장한 학생 문제 N명의 학생이 참여하여 세 번의 시험을 치렀다. N명의 학생들은 세 번의 시험에 모두 응시하였다. 조교는 각각의 시험에서 같은 등수의 학생이 한 명도 없도록 성적을 매겼다. A라는 학생이 www.acmicpc.net [난이도] - Platinum 2 (2020.08.05 solved.ac 기준) [개념] - 세그먼트 트리 (Segment Tree) [풀이] 우선 https://jason9319.tistory.com/57 블로그의 설명을 참고하여 풀이를 하였다. 문제를 요약하자면, 각 학생이 세 번의 시험에 참여하였고, 학생 A보다 세 과목이 모두 더 높은 등수인 사람이 없다면 A를 '굉장하다'라고..
[BOJ 2517] 달리기 출처 : https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 선수부터 제시한 것이다. 각 정수는 1 이상 1,000,000,000 이하이다. 단, 참가한 선수들의 평소 실력은 모두 다르다. www.acmicpc.net 세그먼트 트리(Segment Tree)를 이용한 문제이다. 각 선수마다 자기보다 앞에 달리고 있는 선수들 중에서 자신보다 실력이 높은 사람의 수 + 1이 자신의 최선의 등수가 된다. 각 선수들의 실력을 정수로 나타내었고, 실력의 범위가 1~10억이다. 여기..
[BOJ 2568] 전깃줄 - 2 문제 출처 : https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500,000 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다. www.acmicpc.net LIS (Longest Increasing Subsequence, 최장 증가 부분 수열) 유형의 문제이다. 전깃줄이 순서없이 입력되기 때문에 A 또는 B를 기준으로 정렬을 해주어야 한다. A를 기준으로 정렬한다면, 정렬된 후의 B 수열을 가지고..

티스토리툴바