본문 바로가기

분류 전체보기

 (403)
백준 1941번 - 소문난 칠공주 (C++) https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 처음에는 dfs 백트레킹 완전 탐색으로 풀어내려 했다. 그러나 백트레킹 완전탐색은 ㅗ ㅏ ㅜ ㅓ 같은 모양은 나타낼 수 없다. 이러한 문제를 테트로미노 문제에선 길이가 4밖에 안되었으니 위 4개의 모양만 따로 관리하면 되었으나 이 문제는 길이가 7이기 때문에 따로 관리하는 것이 불가능하다. 풀이 방법은 다음과 같다. 1. 총 25명의 학생 중 7명을 뽑는다 -> 조합으로 0번~24번 중 7개를 뽑는다..
백준 1516번 게임 개발 (C++) https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 위상 정렬을 할 수 있으면 50퍼센트는 되는 문제. 건물을 미리 지어야하는데 미리 지은 건물들의 시간을 모두 더해야하는 문제이다. 위 사진은 기본 예제에서 4를 지을 조건에 2까지 추가한 것이다. 4를 짓기 위해서는 1,2,3을 지어야한다. 그렇다면, 2,3을 짓고 4를 지어야하는데 2번의 경우 20, 3번의 경우 14이다. 여기서 그냥 위상정렬대로 전입차수가 0이라고 더하면 24가될수..
Alias-Free Generative Adversarial Networks (StyleGAN3) - 논문 분석 Paper : Alias-Free Generative Adversarial Networks - Tero Karras, Miika Aittala, Samuli Laine, Erik Härkönen, Janne Hellsten, Jaakko Lehtinen, Timo Aila https://arxiv.org/abs/2106.12423 문제점 StyleGAN2의 texture sticking 이라는 문제를 가짐. 이미지를 구조적으로 학습하는 것이 아닌 고정된 픽셀 단위로 학습하고 있다. 목표 hiearchical한 이미지 학습을 위해 alias-free NetWork 제안하며 Traslation이나 rotation에 대해 equivariance 만족하는 것. equivariance란 어떤 요소가 이동하면 그에..
백준 1655번 가운데를 말해요 (C++) https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제 이해는 쉬운데 어떻게 해야할지 감이 안잡히는 문제이다. 게다가 제한시간이 무려 0.1초다. 무조건 O(N)으로 풀어내야한다. 아이디어는 다음과 같다. 1 2 3 4 5 가 있다고 하자 그렇다면 여기서 1,2,3 은 최대힙 4,5는 최소힙으로 구성한다. 그렇다면 언제나 최대힙의 top이 정답이된다. 이것이 가능하려면 여기서 규칙이 생긴다. 1. 최대힙의 개수는 언제나 최소힙과 ..
백준 9084번 동전(C++) https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 문제를 풀 때 dfs bfs 백트레킹 완전탐색으로 많이 풀다보니 TLE가 많이 발생한다는 느낌이 들었다. 이번 아레나에서도 아마 출력은 다 맞았을탠데 시간초과가 나서 문제를 풀지 못했다. DP라는 것도 알고 있었는데 못풀다니 기분이 너무 안좋았다. 그래서 DP를 열심히 풀어보고 있다. 그런데 DP는 구글링 안하면 풀수가… ㅠㅠㅠ 언젠가 온전히 내 힘으로 풀기를 고대한다. 이 문제는..
백준 6593번 상범 빌딩(C++) https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 기본적인 bfs + 이동 카운트 문제이다. 아마도 q에서 직접 지나온 칸 수를 갖고 있는 방법과 다른 배열을 선언해서 갖고 있는 방식이 될 것 같은데 나는 후자를 선택하였다. 3차원 bfs는 처음이었는데 2차원 bfs와 다를게 없었다. #include #include using namespace std; int L, R, C; char building[31][31][31]; int cnt[31][31]..
백준 1766번 문제집 (C++) https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 위상 정렬문제이다. 줄세우기 문제와 유사하지만 중요한 건 이번에는 이왕이면 더 작은 수 부터 해야하기 때문에 bfs 방식만을 사용해서 우선순위큐를 만들어줘야한다. 정답 코드 #include #include #include using namespace std; int N, M; vector graph[32001]; bool check[32001] = { false, }..
백준 2252번 줄세우기 (C++) https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 위상정렬의 예제 문제이다. 예제 1번을 보자. 3 → 2 1 → 3 2 → 3 위상정렬을 적용해보면 1번은 없고 2번은 3번이 3번은 1번과 2번이 먼저 와야한다. 그러므로 진입차수가 0인 1이 들어오고 진입차수가 다음으로 0이되는 2번이 오고 그다음 3번이 온다. 위상정렬의 특성상, 진입차수가 0인 것이 2개이면 dfs bfs 방법에 따라 순서가 바뀔 ..

티스토리툴바