본문 바로가기

전체 글

 (37)
백준 11057 - 오르막수(C++/동적계획법/DP/Dynamic Programming) https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 문제 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. 접근법 일단 MOD(출력..
백준 1783번 - 병든 나이트(C++/Greedy/그리디 알고리즘/ 경우의수 분석) https://www.acmicpc.net/problem/1783 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다. 2칸 위로, 1칸 오른쪽 1칸 위로, 2칸 오른쪽 1칸 아래로, 2칸 오른쪽 2칸 아래로, 1칸 오른쪽 병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다. 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4번보..
백준 2110 번 - 공유기설치 (C++/이분탐색/ 추후 다시풀어보기) 문제 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. 접근법 그리디 알고리즘인줄 알고 접근했지만, 비교횟수가 너무 많아 이분탐색으로 풀어야 한 문제다. 정해진 공유기 개수로, 공유기의 간격을 최대로 하고싶다는것은, 공유기를 최대한 공평하게 설치하고 싶..
백준 10844 번 - 쉬운계단수 (C++/DP/동적계획법/Dynamic Programming) 문제 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. 접근법 동적계획법으로 접근해야 하는 문제이다. 여러가지 예시를 보며 문제부터 파악했다. 자리수를 Y, 맨 뒤 index에 따른 개수를 X로 두고, 2차원 배열을 만들면 cnt[101][10]; 정도로 크기를 두며 이전 값을 참고해 채워나가면 될거같다. 자리수는 2인 것 끝자리 0 -> 10 끝자리 1-> 21 끝자리 2->32,12 끝자리 3->23,43 끝자리 4->34,54 . . . 끝자리 8->78,98 끝자리 9->89 맨 앞자리는 0이 올수 없으므로 위 17가지가 계단수이다. 자리..
백준 1707 - 이분그래프(C++/DFS/BFS/그래프) https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 문제 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 ..
백준 10610번 - 30 (C++/greedy(그리디)알고리즘) 문제 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다. 미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라. 접근법 이 문제는 문제 예시를 보고 풀이법을 유추해낸 특이한 경우이다. 가장 큰 힌트를 얻었던 것은 30으로 나누어 떨어지는 숫자들은 모두 해당 숫자를 내림차순으로 내린것과 같다는 것이 보였다. 그럼 만약 30으로 나누어 떨어지면 내림차순으로 정렬해주면 되겠다 생각을 했고, 30으로 나누어 떨어지는 조건만 찾으면 됐다. 1. 모든자리의 수의 합이 3이 되어야 한다. (3의 배수 조건) 2. 끝자리는 0으로 끝나야 한다. (10의 배수..
언리얼 퀵셀 브릿지(unreal quixel bridge, 퀵셀 브리지) 언리얼에서 여러 에셋들을 찾아보다가 퀵셀 브리지라는 것을 알게되었다. 실제 고퀄리티 게임인 배틀필드V, 데스트니 가디언즈 등에서 사용한다. 즉 수 많은 스캔데이터 기반 3D 에셋과 2D 텍스쳐를 무료로 제공해주는 기능이다(언리얼 사용 한정 무료, 원래는 구독제인거같다). https://www.youtube.com/@quixeltools/videos Quixel Quixel ecosystem of tools enables high-quality 3D experiences by simplifying world creation. Makers of Megascans, Bridge, and Mixer | Part of the Epic Games family. Whether you work in films, gam..
백준 11662번 - 민호와 강호(C++/삼분탐색) https://www.acmicpc.net/problem/11662 11662번: 민호와 강호 민호와 강호가 2차원 좌표 평면 위에 있다. 민호는 점 A(Ax, Ay)에서 점 B(Bx, By)를 향해 걸어가고 있고, 강호는 점 C(Cx, Cy)에서 점 D(Dx, Dy)를 향해 걸어가고 있다. 민호와 강호는 동시에 출발하고, 민 www.acmicpc.net 문제 민호와 강호가 2차원 좌표 평면 위에 있다. 민호는 점 A(Ax, Ay)에서 점 B(Bx, By)를 향해 걸어가고 있고, 강호는 점 C(Cx, Cy)에서 점 D(Dx, Dy)를 향해 걸어가고 있다. 민호와 강호는 동시에 출발하고, 민호가 점 B에 도착하는 순간 강호도 점 D에 도착한다.또, 두 사람은 항상 일정한 속도로 걸어간다. 두 사람의 거리가..
728x90
반응형

티스토리툴바