최선을다하는

이번 시간에는 힙에 관한 내용이었다. 저번 학기 알고리즘 수업 때 힙을 되게 많이 다루어서 힙에는 자신감이 있었다. 수업을 듣기 전에는 힙을 이름만 알고 잘 몰랐지만 학기 중에 여러 번 구현하면서 잘하는 줄 알았지만 아니었다! 수업 때 강의자료에 있는 adjust() 코드를 항상 옆에 참조해서 풀어서 그런가 보다. 수업 때 배운 adjust는 미리 수의 배열이 있고 마지막 부모 노드부터 자식 노드들을 확인하며 자신 아래의 트리가 힙의 원칙에 맞는지 판단하는 방식으로 O(n)의 시간이 걸렸고 heap에서 꺼내어 정렬하는데 O(nlogn)의 시간이 걸려 총 O(nlogn)의 시간이 걸린다. 이번 강에서 배운 내용은 숫자가 주어질 때 heap에 push와 pop을 하는 방법이었다. 처음에 adjust를 사용하..

https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 문제 남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지..

설날 연휴 기간에는 추가로 진도를 나가지 않아 그동안 풀지 않았던 문제들을 풀기로 하였다. 내 코드들은 깃허브에 커밋해두었다! https://github.com/Ho-hoho/SWEA/tree/main No3. 동아리실 관리하기 (SWEA 3316) 부원이 4명이기 때문에 비트마스킹으로 겹치는 사람들을 잘 확인하면 되는 문제였다. 처음엔 일일이 스위치문을 사용하여 ABCD 를 비트로 바꿨는데 다른 사람의 코드를 보니 1

https://www.acmicpc.net/problem/1027 1027번: 고층 건물 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작) www.acmicpc.net 문제 세준 시에는 고층 빌딩이 많다. 세준 시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작)은 (i,0)부터 (i, 높이)의 선분으로 나타낼 수 있다. 고층 빌딩 A에서 다른 고층 빌딩 B가 볼 수 있는 빌딩이 되려면, 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 ..

https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 문제 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙..

https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 문제 인터넷 방송 KOI(Korea Open Internet)의 음악 프로그램 PD인 남일이는 자기가 맡은 프로그램 '뮤직 KOI'에서 가수의 출연 순서를 정하는 일을 매우 골치 아파한다. 순서를 정하기 위해서는 많은 조건을 따져야 한다. 그래서 오늘 출연 예정인 여섯 팀의 가수에 대해서 남일이가 보조 PD 세 명에게 각자 담당한 가수의 출연 순서를 정해 오게 하였다. 보조 P..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. 입력 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에..

https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 문제 3 ×N 크기의 벽을 2 ×1, 1 × 2 크기의 타일로 채우는 경우의 수를 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 문제에서 주어진 힌트와 같이 2개 단위로 커질 때마다 그 타일을 이 전 타일들로 만들지 못하는 유일한 타일 배치가 2개씩 생기게 된다. 2개만 유일하게 3가지의 경우가 가능하다. 입력값으로 홀수가 주어지게 된다면 3*N 이 총홀수개의 단일 타일이 필요하게 되므로 만들 수 있는 경우의 수는 없다. 짝수가 들어올 경우 본인만의 ..

https://www.acmicpc.net/problem/18115 18115번: 카드 놓기 수현이는 카드 기술을 연습하고 있다. 수현이의 손에 들린 카드를 하나씩 내려놓아 바닥에 쌓으려고 한다. 수현이가 쓸 수 있는 기술은 다음 3가지다. 제일 위의 카드 1장을 바닥에 내려놓는다. www.acmicpc.net 문제 수현이는 카드 기술을 연습하고 있다. 수현이의 손에 들린 카드를 하나씩 내려놓아 바닥에 쌓으려고 한다. 수현이가 쓸 수 있는 기술은 다음 3가지다. 제일 위의 카드 1장을 바닥에 내려놓는다. 위에서 두 번째 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다. 제일 밑에 있는 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다. 수현이는 처음에 카드 N장을 들고 있다..

6번째 내용은 트리였다. 강의 내용은 역시 어려운 것은 없었고 순회 방식등에 대한 내용이었다. 그리고 4문제가 기본문제로 주어졌는데 처음 2문제는 어렵지 않게 풀 수 있었다. 3번째 문제는 SWEA 1232번 사칙연산 문제였다. 앞선 두문제와 다르게 한자리 숫자가 아닌 여러자리 숫자가 올 수 있었으며 인덱스가 N의 반이 넘어가도 리프노드가 아닐 수 있어 문자가 올지 숫자가 올지 모르는 경우였다. 그래서 사칙연산 자체는 쉬웠으나 입력값을 받는데 난항을 겪었다. char 형식으로 받으려다가 마지막에서야 string 으로 받은 다음에 숫자면은 int 로 변환을 하는 방법을 사용했다. string stream 을 사용했지만 그냥 stoi 를 사용하는게 더 편했을 것 같다. vector 나 queue를 사용하면서..