본문 바로가기

Algorithms

 (42)
[PS] 백준 #14500. 테트로미노 문제 정보 난이도: 골드 V 문제 주소: https://www.acmicpc.net/problem/14500 이 문제를 푼 이유: 알고리즘 스터디 - 브루트포스와 그리디 문제 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다. 테트로미노 하나를 적절히 ..
[PS] 백준 #19539. 사과나무 문제 정보 난이도: 실버 I 문제 주소: https://www.acmicpc.net/problem/19539 이 문제를 푼 이유: 알고리즘 스터디 - 브루트포스와 그리디 문제 이하는 최근 사과나무 씨앗을 구매하여 농장 뒷뜰에 일렬로 $1$번부터 $N$번까지 심었다. 이 나무들의 초기 높이는 모두 $0$이다. 사과나무를 무럭무럭 키우기 위해 이하는 물뿌리개 $2$개를 준비했다. 한 물뿌리개는 나무 하나를 $1$만큼 성장시키고, 다른 물뿌리개는 나무 하나를 $2$만큼 성장시킨다. 이 물뿌리개들은 동시에 사용해야 하며, 물뿌리개를 나무가 없는 토양에 사용할 수는 없다. 두 물뿌리개를 한 나무에 사용하여 $3$만큼 키울 수도 있다. 물뿌리개 관리 시스템을 전부 프로그래밍한 이하는 이제 사과나무를 키워보려고 했다..
[PS] 백준 #16937. 두 스티커 문제 정보 난이도: 실버 IV 문제 주소: https://www.acmicpc.net/problem/16937 이 문제를 푼 이유: 알고리즘 스터디 - 브루트포스와 그리디 문제 크기가 H×W인 모눈종이와 스티커 N개가 있다. i번째 스티커의 크기는 Ri×Ci이다. 모눈종이는 크기가 1×1인 칸으로 나누어져 있으며, 간격 1을 두고 선이 그어져 있다. 오늘은 모눈종이에 스티커 2개를 붙이려고 한다. 스티커의 변은 격자의 선과 일치하게 붙여야 하고, 두 스티커가 서로 겹치면 안 된다. 단, 스티커가 접하는 것은 가능하다. 스티커를 90도 회전시키는 것은 가능하다. 스티커가 모눈종이를 벗어나는 것은 불가능하다. 두 스티커가 붙여진 넓이의 최댓값을 구해보자. 나의 풀이 브루트포스로 모든 두 쌍의 스티커마다 붙일..
[PS] 백준 #20044. Project Teams 문제 정보 난이도: 실버 IV 문제 주소: https://www.acmicpc.net/problem/20044 이 문제를 푼 이유: 알고리즘 스터디 - 브루트포스와 그리디 문제 코딩 프로젝트 수업을 가르치는 수찬이는 프로젝트 팀을 가능하면 공정하게 구성하려고 한다. 프로젝트 팀 하나는 두 명의 학생으로 구성되는데, 각 학생들의 코딩 역량은 모두 다르다. 각 학생은 한 팀의 팀원이어야 한다. 공정성을 높이기 위해 수찬이는 팀원 코딩 역량의 합을 최대한 일정하게 유지하려고 한다. 학생들이 코딩 역량이 주어졌을 때 수찬이가 팀을 구성하는데 도움이 되는 프로그램을 작성하라. 문제를 간단하게 하기 위해, 학생 수는 2n이라 가정하자 (n은 양의 정수). 각 학생 si의 코딩 역량은 양의 정수 w(si)로 나타내면..
[PS] 백준 #1018. 체스판 다시 칠하기 문제 정보 난이도: 실버 V 문제 주소: https://www.acmicpc.net/problem/1018 이 문제를 푼 이유: 알고리즘 스터디 - 브루트포스와 그리디 문제 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은..
[알고개념] 2. Lowest Common Ancestor LCA는 스터디 발표 자료로 블로그 글을 대신합니다.
[알고개념] 1. Segment Tree 1. 알고리즘 개념 세그먼트 트리: 각 노드가 구간 정보를 가지고 있는 트리를 의미한다. 루트 노드는 전체 구간을 가지고, 리프 노드는 길이가 1인 구간들을 가진다. 리프 노드를 제외한 다른 모든 노드는 항상 2개의 자식을 가진다. -> 완전 이진 트리 꼴 리프 노드가 $N$개인 완전 이진 트리의 전체 노드의 개수는 $2N-1$이고, 높이는 $\lceil log\ N \rceil$ 이다. $N$이 2의 제곱꼴이 아닐 경우에는 남는 구간을 기본값으로 채워서 사용한다. 2. 알고리즘 구현 start == end : 리프 노드는 구간 길이가 1이므로 바로 값을 대입한다. node의 왼쪽 자식은 node*2이고, 오른쪽 자식은 node*2+1이다. node에 저장된 구간이 [start,end]라면, 왼쪽 자식은..
[PS] 백준 #2798. 블랙잭 문제 정보 난이도: 브론즈 II 문제 주소: https://www.acmicpc.net/problem/2798 이 문제를 푼 이유: 알고리즘 스터디 - 브루트포스와 그리디 문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다. 이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라..

티스토리툴바