bard_story의 등록된 링크

키자드에 등록된 총 53개의 포스트를 확인하실 수 있습니다.

Naver Blog

숫자 타자 대회

문제 설명 레벨 3 https://school.programmers.co.kr/learn/courses/30/lessons/136797 위와 같은 모양으로 배열된 숫자 자판이 있습니다. 숫자 타자 대회는 이 동일한 자판을 사용하여 숫자로만 이루어진 긴 문자열을 누가 가장 빠르게 타이핑하는지 겨루는 대회입니다. 대회에 참가하려는 민희는 두 엄지손가락을 이용하여 타이핑을 합니다. 민희는 항상 왼손 엄지를 4 위에, 오른손 엄지를 6 위에 두고 타이핑을 시작합니다. 엄지손가락을 움직여 다음 숫자를 누르는 데에는 일정 시간이 듭니다. 민희는 어떤 두 숫자를 연속으로 입력하는 시간 비용을 몇몇 가중치로 분류하였습니다. 이동하지 않고 제자리에서 다시 누르는 것은 가중치가 1입니다. 상하좌우로 인접한 숫자로 이동하여 누르는 것은 가중치가 2입니다. 대각선으로 인접한 숫자로 이동하여 누르는 것은 가중치가 3입니다. 같지 않고 인접하지 않은 숫자를 누를 때는 위 규칙에 따라 가중치 합이 최소가 되는

원문보기 내부링크
Naver Blog

Unity Action Builder 1

개요요 Action Builder 개발 일지 지난 번에 만든 Stat Controller에서 더 나아가, 그걸 활용할 수 있는 Action Builder를 만들고 있다. 발동과 취소, 일시정지 재개의 큰 흐름을 다루는 객체인 Action와 파티클 재생이나 사운드 재생 및 스탯 조정 등의 서브 흐름을 다루는 Effect로 구성했다. 항상 유니티로 개발하면서 느꼈던 것인데, 스킬과 공격, 회피, 점프 등의 액션이라 부를 수 있는 동작들과 그 동작들로부터 발동되는 어떤 이벤트를 쉽게 관리할 수 있는 시스템이 필요하다고 생각했다. 처음엔 에셋스토어에서 판매 중인 프레임워크 사거나, 오픈 소스를 확장해서 쓰려고 했지만 이것도 경험인듯 싶어서 직접 만들어보기로 결정했다. 그리고 처음에 Action Builder는 Stat System과는 별도의 에디터프로젝트로 다룰 생각이었으나, 저 동작들은 대게 엔티티의 수치를 기반으로 하는 기능들이라서 스탯과 함께 다루고자 프로젝트를 합쳤다. 액션과 이펙트

원문보기 내부링크
Naver Blog

가장 높은 탑 쌓기

문제 설명 밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래에서 위로 쌓으면서 만들어 간다. 아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프 로그램을 작성하시오. 조건들) 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다. 밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다. 벽돌들의 높이는 같을 수도 있다. 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다. 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다. 입력 설명 입력 파일의 첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 벽돌의 밑면의 넓이, 벽돌의 높이, 무게가 차례대로 자연수로 주어진다. 각, 벽돌은 입력되는 순서대로 1부터 연속적인 번호를 가진다. 출력 설명 첫 번째 줄에 가장 높이 쌓을 수 있는 탑의 높이를 출력한다 입력 예제 5 25

원문보기 내부링크
Naver Blog

알리바바와 40인의 도둑

목차 문제 설명 풀이 (Botton-up) 풀이 (Top-down) 문제 설명 알리바바는 40인의 도둑으로부터 금화를 훔쳐 도망치고 있습니다. 알리바바는 도망치는 길에 평소에 잘 가지 않던 계곡의 돌다리로 도망가고자 한다. 계곡의 돌다리는 N × N 개의 돌들로 구성되어 있다. 각 돌다리들은 높이가 서로 다릅니다. 해당 돌다리를 건널 때 돌의 높이만큼 에너지가 소비됩니다. 이동은 최단거리 이동을 합니다. 즉, 현재 지점에서 오른쪽 또는 아래쪽으로만 이동해야 합니다. N*N의 계곡의 돌다리 격자 정보가 주어지면 (1, 1) 격자에서 (N, N)까지 가는데 드는 에너지의 최소량을 구하는 프로그램을 작성하세요. (1, 1) 좌표에서 (3, 3) 좌표까지 가는데 드는 최소 에너지는 3+2+3+4+2=14이다. 입력 예제 5 3 7 2 1 9 5 8 3 9 2 5 3 1 2 3 5 4 3 2 1 1 7 5 2 4 출력 예제 25 풀이 코드 (Botton-up) 위 동영상 2:37초부터 비슷한

원문보기 내부링크
Naver Blog

가방 문제

최고 17kg의 무게를 저장할 수 있는 가방이 있다. 그리고 각각 3kg, 4kg, 7kg, 8kg, 9kg의 무게를 가진 5종류의 보석이 있다. 이 보석들의 가치는 각각 4, 5, 10, 11, 13이다. 이 보석을 가방에 담는데, 17kg를 넘지 않으면서 최대의 가치가 되도록 하려면 어떻게 담아야 할까요? 또 한 각각의 종류별 보석의 개수는 무한히 많아서 여러 번 가방에 담을 수 있다. 입력 예제 4 11 5 12 3 8 6 14 4 8 출력 예제 28 풀이 방식 무게가 5이고 가치가 12인 첫 번째 보석들 기준으로 설명하겠습니다. 먼저 DP 테이블은 각각의 무게에 대응하는 최대 가치를 저장하는 테이블이다. 예를 들어 문제에서 제시하는 가방의 가용 용량이 5라면, DP 테이블은 0부터 5까지인 길이 6의 배열을 갖는다. 현재 보석을 토대로 DP 테이블을 채우면 사진처럼 현재 무게 대비 가치가 쭉 채워진다. 가방의 가용 무게가 5 ~ 9라면 가방이 가질 수 있는 각각의 최대 가치는

원문보기 내부링크
Naver Blog

평범한 배낭

문제 https://www.acmicpc.net/problem/12865 풀이 코드 가방 문제 최고 17kg의 무게를 저장할 수 있는 가방이 있다. 그리고 각각 3kg, 4kg, 7kg, 8kg, 9kg의 무게를 가진 5종... blog.naver.com 위 글에서 정리해놓은 방법 그대로 풀었다. 다만 이 문제는 가방에 넣을 물건의 중복을 허용하지 않기 때문에 역순으로 탐색하도록 구현했다. #include <bits/stdc++.h> using namespace std; struct jewelry { int w, v; }; int n, m, mx = -2e9; int main(int argc, char** argv) { ios::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; vector<int> dp(m+1, 0); vector<jewelry> js(n); for (int i=0; i<n; ++i) { cin >> js[i].w >>

원문보기 내부링크
Naver Blog

동전교환

다음과 같이 여러 단위의 동전들이 주어져 있을 때, 거스름돈을 가장 적은 수량의 동전으로 준다면 그 동전의 수는 몇 개인지 구하는 프로그램을 작성하시오. 각 단위의 동전은 무한정 쓸 수 있다. 입력 예제 3 1 2 5 15 출력 예제 3 풀이 코드 가방 문제 최고 17kg의 무게를 저장할 수 있는 가방이 있다. 그리고 각각 3kg, 4kg, 7kg, 8kg, 9kg의 무게를 가진 5종... blog.naver.com 위 글에 적어놓은 풀이 방법과 거의 유사하나, 한 가지 다른 점은 동전의 수량을 DP 테이블로 풀이했다. 0 ~ M은 입력 동전 값에 대응하며, 각각의 방은, 값에 대응하는 최소 동전 수량을 의미한다. 이 문제의 입력 예제를 기준으로 하면 배열의 크기는 M+1 (16). 그리고 16개에 달하는 각각의 배열 방은 돈 대비, 거슬러줄 동전의 최소 수량을 나타낸다. 핵심은 거슬러 줄 금액의 최소 동전 수량 = (더 작은 금액의 최소 수량을 만든 최선의 방법) + (동전 1개

원문보기 내부링크
Naver Blog

최대점수 구하기

문제 설명 이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩 니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.) 입력 예제 5 20 10 5 25 12 15 8 6 3 7 4 출력 예제 41 풀이 코드 1차원 풀이 방식 평범한 배낭 문제 풀이 코드 위 글에서 정리해놓은 방법 그대로 풀었다. 다만 이 문제는 가방에 넣을 물건의 중복을 허... blog.naver.com 위 문제 유형과 완전히 똑같은 논리로 풀 수 있는 문제였다. 중복을 허용하지 않기 때문에 Dp 테이블을 역순회하며, 갱신하면 됨. t : 해당 문제를 푸는데 걸리는 시간. s : 해당 문제를 풀었을 때 받는 점수. #include <bits/stdc++.h> using name

원문보기 내부링크
Naver Blog

Unity Action Builder 2

목차 타임라인 뷰 구현. 템플릿 스크립트 구현. 스탯 시스템 삭제. 앞으로 구현할 목록. 타임라인 뷰 구현 지난 글에서 애니메이션에 동기화되는 TimelineBasedAction을 만들겠다고 했는데 일단 Timeline View는 실기능 제외하고 뷰만 대략적으로 구현이 되었다. 이펙트도 등록도 가능하고 재생시간과 딜레이 조정도 가능하다. UI Toolkit이 아니라 IMGUI로 만들었기에 구조상 하드코딩이 적지 않았다. Task Streamer를 만들 땐, GraphView라도 있었는데 Timeline은 딱히 그런 에디터 클래스가 없는 것 같다. 내가 못 찾은 걸 수도 있는데, 오픈소스나 에셋스토어 에셋도 하드코딩으로 구현한 대다수라 머리 좀 아팠다. (까보면 거의 다 Handles와 Rect 그리고 매직넘버의 조합으로 도배되어 있음, 물론 이제 본인도 거기에 참가) 템플릿 스크립트 구현 Unity 스크립트 템플릿 만들기 스크립트 템플릿이란 유니티 프로젝트 뷰에서 새로운 MonoBe

원문보기 내부링크
Naver Blog

플로이드 와샬 (Floyd-Warshall)

서론 https://commons.wikimedia.org/wiki/Category:Floyd-Warshall_algorithm?uselang=ko 자주 다익스트라와 함께 언급되는 알고리즘으로, 모든 정점에서 다른 모든 정점까지의 최단 거리를 구할 때 쓴다. 다이나믹 프로그래밍 기법을 사용하기 때문에 그래프를 인접 행렬 방식으로 다룬다. 시간 복잡도는 모든 최단 거리를 구하기 때문에 O(V3). 다익스트라나, 벨만 포드에 비하면 큰 편이다. 다익스트라 플로이드 와샬 벨만 포드 가중치가 양의 정수일 때만 가능. 가중치가 음의 정수일 때도 가능. 가중치가 음의 정수일 때도 가능. (단, 음의 사이클이 없어야 한다.) 우선순위 큐 사용 시, O(E log V) 3중 For 문이라 O(V^3) O(VE) V는 Vertex (정점), E는 Edge (간선)를 의미함 설명 가중치 인접 행렬에서 distance[i][j]는 i 번째 노드와 j 번째 노드 사이의 직속 거리를 말한다. 가중치 인접

원문보기 내부링크
Naver Blog

회장 뽑기

문제 설명 풀이 코드 플로이드 와샬 알고리즘의 개념과 동작 방식만 이해했다면 쉽게 접근할 수 있는 문제인 듯하다. 플로이드 와샬 (Floyd-Warshall) 서론 자주 다익스트라와 함께 언급되는 알고리즘으로, 모든 정점에서 다른 모든 정점까지의 최단 거리를 구... blog.naver.com 해당 알고리즘은 모든 정점에서 다른 모든 정점까지의 거리를 구하는 알고리즘이다. 그리고 이 문제는 친구의 친구의 ··· 친구, 연관 거리가 적은 사람을 찾아 회장 후보로 올리는 문제이다. 예를 들어 위 사진에서 1과 5랑 연관된 노드는 2, 3나 2, 4, 3로 연관 거리는 5를 포함한 3이나 4이다. 그리고 문제에서 찾는 것은 이러한 연관거리가 제일 적은 사람이므로, 플로이드 와샬을 통해 모든 회원에서 회원으로 이어지는 최소 연관 거리를 찾아내면 된다. for (int k=1; k<=n; ++k) for (int i=1; i<=n; ++i) for (int j=1; j<=n; ++j) fri

원문보기 내부링크
Naver Blog

위상 정렬 (Topological Sort)

목차 위상 정렬 소스 코드 Kahn 알고리즘. DFS 방식. 동작 방식 정리 위상 정렬 (Topological Sort) 位(자리 위): 자리, 위치, 지위 相(서로 상): 서로 관계, 모습, 상태 위상 정렬이란, B는 A 다음에 실행되어야 한다 같은 선행 조건 (의존 관계)이 성립하는 순서로 정렬한다. 한마디로 선행 조건이 있는 작업들을 작업 순서대로 정렬하는 것이다. 예를 들어 게임을 개발하기 위해서 반드시 거쳐야 되는 과정들이 있다. 가장 먼저 핵심 아이디어, 그리고 이를 구체화한 뒤, 개발에 착수해서 테스트 후 게임 출시. 아니면 게임 개발을 외주하여 A부터 Z까지 맡기고, 그렇게 개발이 된 게임을 출시. 어떤 흐름이든, 핵심 아이디어 발상, 또는 게임 기획이 선행 작업으로 존재한다. 위상 정렬은 이러한 흐름을 순차적으로 만드는 알고리즘이다. 이러한 위상 정렬에는 방향성 비순환 그래프 (DAG)라는 조건이 있다. 한마디로 설명하면 그냥 순환하지 않는 그래프만 위상 정렬이 가능

원문보기 내부링크
Naver Blog

공백으로 구분하기 1, 2

문제 설명 둘 다 레벨 0 우측 1, 좌측 2 풀이 코드 istringstream은 문자열을 입력 스트림으로 취급하는 클래스. 문자열에서 데이터를 읽어내기 쉽게 제공하는 객체. getline은 스트림에서 한 줄(한 라인)을 읽어오는 함수. 공백을 포함한 전체 라인을 읽을 수 있고, 구별자를 인자로 보내 한 줄을 끊어서 받을 수 있다. 구별자로 구분된 문자열은 string 객체이자, getline의 2번째 인자인 buffer에 담긴다. 즉, 입력으로 받은 문자열을 가공하기 쉽게 문자열 스트림에 담고, 구별자를 통해 각각의 문자를 분리. 그리고 버퍼에 담긴 구분된 문자가 없다면 무시하고 있다면 결과로 반환할 리스트에 담는다. #include <bits/stdc++.h> using namespace std; void split(string str, vector<string>& list) { istringstream ss(str); string buffer; while(getline(ss,

원문보기 내부링크
Naver Blog

토마토 1

문제 설명 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다. 토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다. https://www.acmicpc.net/problem/7576 솔루션 익은 사과와 상하좌우로 인접한 안 익은 사

원문보기 내부링크
Naver Blog

토마토 2

문제 설명 솔루션 토마토 1번과 같은 풀이로 풀었다. 다른 점은 문제 자체가 3차원을 기준으로 하다 보니 탐색에 필요한 배열도 3차원 배열로 하여 간단하게 풀었다. 3차원 배열을 평소에 쓸 일 자체가 거의 없다 보니 입력받을 때, 살짝 뇌 정지가 온 것 말곤 어려운 건 없었다. #include <iostream> #include <vector> #include <queue> using namespace std; struct info { int y; int x; int f; //floor int day; }; struct cell { int state; bool visit; }; int m, n, h; int dir[6][3] = { {1, 0, 0}, {0, 1, 0}, {-1, 0, 0}, {0, -1, 0}, {0, 0, 1}, {0, 0,-1} }; vector<vector<vector<cell> > > box; queue<info> q; int BFS() { int currD

원문보기 내부링크
Naver Blog

Unity PropertyBag

개요 PropertyBag, 일명 속성 가방. 번역기를 돌리면 부동산 가방이라고도 나온다. 유니티 내부적으로 동작하는 리플렉션을 통해 직렬화된 객체들에 접근할 수 있도록 해주는 유니티 API이다. 영상에서 나오듯, UI Toolkit의 데이터 바인딩 과정에서도 PropertyBag가 사용된다고 하며, 유니티 6부터 제공되는 Behavior Tree도 Json 직렬화에 Unity.Properties를 사용한다. Unity.Properties Namespace Unity.Properties | Properties | 2.1.0-exp.7 Namespace Unity.Properties Classes AOT Helper class to preserve generic methods for AOT platforms. AOT.DictionaryPropertyGenerator<TContainer, TDictionary, TKey, TValue> Helper class to preserve dic

원문보기 내부링크
Naver Blog

Unity Debug 최적화

개요 Unity의 Debug.Log 같은 함수는 System.object 타입을 매개변수로 받는다. 문제는 object 타입에 값 타입이 만나면 boxing 이 발생하기 때문에 성능상 좋지 않으며 Debug.Log류는 기본적으로 문자열 연산이기 때문에 쉽게 가비지가 발생한다. 이것뿐이 아니라, 그 외에도 외부 CPP 함수에서 여러 연산을 한다고 안다. 그래서 유니티 최적화 관련 글을 보면 경험상 대부분, Debug.Log 류 함수는 빌드할때 지우라고 한다. 때문에 System.Diagnostics.Conditional 어트리뷰트를 위주로 Debug 클래스를 랩핑해서 쓴다. (빌드 프로파일에 Conditional 어트리뷰트 옵션에 따라 특정 함수를 빌드에서 제외하는 옵션이 있다) 에디터에서 로그를 끌 생각이 없다면 굳이 추가로 심볼을 만들지 않고 기본 제공되는 UNITY_EIDTOR 만으로 충분하다. [Conditional("UNITY_EDITOR")] //기본적으로 정의되어 있는 심

원문보기 내부링크
Naver Blog

유니티 Task Streamer 개발

작업 중개자 (Task Streamer) 유니티에서 Behavior Tree와 Finite State Machine을 병합한 그래프 프레임워크를 만들고 있다. 간간히 개발 중인 프로젝트로, Behavior System라는 이름에서 Task Streamer로 새롭게 변경했다. 사실 1.0 베타 버전으로는 거의 만든 수준이다. 런타임에도 정상적으로 잘 작동하고, 만들고 싶다고 생각해뒀던 기능들은 얼추 다 만들었다. Gif 용량을 줄이는 과정에 흑백이 되었다. FSM Graph View에선 Transition도 구현했다. Blackboard의 Variable도 할당이 가능한. 하지만 개선할 부분도 어느 정도 남아있고, 아직 기존 문서 수정과 새 기능들 문서 작성은 시작도 못 했다. 기능 문서로 처음엔 노션이나, README 도배를 생각했지만 이번에 처음으로 Docfx를 사용해 볼 것 같다. (국내 자료는 별로 없지만, 오픈소스 이기하고, 마이크로소프트 프로그램답게 문서화도 잘 되어 있는

원문보기 내부링크
Naver Blog

라이언 킹 심바

문제 설명 새끼 사자 주제에 엄청 치밀하다. 문제 조건 1. 어린 사자 심바와 토끼는 모두 몸 크기를 가지고 있고, 이 크기는 자연수. 2. 가장 처음, 어린 사자 심바의 크기는 2. 3. 심바는 인접한 상하좌우 격자칸으로 이동할 수 있다. 4. 심바는 자신보다 작은 토끼만 잡아먹을 수 있으며 크기가 같은 토끼는 먹을 수는 없지만, 그 칸은 지날 수 있다. 5. 심바는 한 번에 한 마리만 샤냥할 수 있다. 6. 동일한 거리의 토끼가 많으면, 그 중 가장 위쪽에 있는 토끼, 그래도 여러 마리라면, 가장 왼쪽에 있는 토끼. 7. 심바가 격자칸 하나를 이동하는데 1초가 걸리고 토끼를 먹는데 걸리는 시간은 없음. 8. 자신의 몸 크기와 같은 마리수를 잡아먹으면 몸의 크기가 1증가한다. (3이라면 3마리 먹은 후, 4가 됨) 풀이 코드 심바는 특정한 거리, 체급 조건에 부합하는 토끼를 찾았을 때에만 샤낭하러 움직인다. 거리는 BFS를 사용하여 심바로부터 각 토끼의 칸까지의 거리를 구하면 된다

원문보기 내부링크
Naver Blog

아기상어

문제 설명 https://www.acmicpc.net/problem/16236 라이언킹 심바와 같은 문제이다. 라이언 킹 심바 문제 설명 새끼 사자 주제에 엄청 치밀하다. 문제 요약 1. 어린 사자 심바와 토끼는 모두 몸 크기를 가지고... blog.naver.com 풀이 코드 CPP 좀 간만에 만져보는 탓에, 구조체 위주로 구성해서 풀어보았다. 특히 우선순위 큐 비교를 위한 구조체는 정말 오랜만에 써보아서, 구글링하면서 작성했다. 라이언킹 심바와 똑같은 로직으로 풀었다. 다만, 우선순위 큐를 안 쓰고 BFS만으로도 풀 순 있어 보인다. #include <iostream> #include <vector> #include <queue> #define SHARK 9 #define MAX 2e9 using namespace std; struct POINT { int x, y; }; struct fish { POINT p; //position int d; //distance fish(POI

원문보기 내부링크
Naver Blog

TaskStreamer를 콤보에 적용

서론 맨 처음 TaskStreamer를 구상하게 된 이유가 위 Gif처럼 FSM으로 캐릭터의 전체적인 행동을 제어하고, 콤보와 같은 일련의 행동은 BT를 통해 순차적·선택적·조건 분기적으로 실행하기 위함이었다. . 핵심 아이디어 상위 레벨: FSM으로 상태 관리 (Idle, Attack, Jump 등) 하위 레벨: BT로 각 상태 내 행동 시퀀스 관리 (콤보 패턴 등) 아이디어와 문제 하지만 막상 개발해서 적용시켜보니 콤보 BT는 생각만큼 좋은 방식은 아닌 것 같다. 이벤트 기반 패스 방식 처음에는 다이어그램처럼 관련 이벤트를 받아야 다음 노드로 넘어가는 절차적 방식으로 구상했다. 1. 이벤트 A 대기 2. Node 2 (데미지 판정) 3. 이벤트 B 대기 4. Node 3 (이펙트) 5. 이벤트 C 대기 6. Node 4 (입력 대기) 즉, 입력 이벤트로 콤보 공격 BT이 시작되면, BT의 각 노드가 애니메이션 이벤트 프로세서 역할을 하는 것. 근데 애니메이션 이벤트는 다음과 같은

원문보기 내부링크
Naver Blog

최대 부분 증가수열

문제 설명 N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라. 예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어 길 이가 5인 최대 부분 증가수열을 만들 수 있다. 입력 설명 첫째 줄은 입력되는 데이터의 수 N(1≤N≤1,000, 자연수)를 의미, 둘째 줄은 N개의 입력데이터들이 주어진다. 출력 설명 첫 번째 줄에 부분증가수열의 최대 길이를 출력한다. 예제 입력 8 5 3 7 8 6 2 9 4 출력 입력 4 첫 번째 풀이 시도 DP임을 알고 시도한 문제였는데, 어떻게 접근해야될지 몰라서 일단 완전 탐색으로 접근해보았다. 자리수가 최대 1000자리까지 나옴에도 불구하고 일단은 모든 경우의 조합을 구하고, 그 안에서 부분 증가 수열의 최대 길이를 측정하는 방식으로 시도해보았다. 당연히 시간

원문보기 내부링크
Naver Blog

최대 선 연결하기

문제 설명 왼쪽의 번호와 오른쪽의 번호가 있는 그림에서 같은 번호끼리 선으로 연결하려고 합니다. 왼쪽 번호는 무조건 위에서부터 차례로 1부터 N까지 오름차순으로 나열되어 있습니다. 오른쪽의 번호 정보가 위부터 아래 순서로 주어지만 서로 선이 겹치지 않고 최대 몇 개의 선 을 연결할 수 있는지 구하는 프로그램을 작성하세요. 위의 그림은 오른쪽 번호 정보가 4 1 2 3 9 7 5 6 10 8로 입력되었을 때, 선이 서로 겹치지 않고 연결할 수 있는 최대 선을 개수 6을 구한 경우입니다. 입력 설명 첫 줄에 자연수 N(1<=N<=100)이 주어집니다. 두 번째 줄에 1부터 N까지의 자연수 N 개의 오른쪽 번호 정보가 주어집니다. 순서는 위쪽 번호부터 아래쪽 번호 순으로입니다. 출력 설명 첫 줄에 겹치지 않고 그을 수 있는 최대 선의 개수를 출력합니다. 입력 예제 10 4 1 2 3 9 7 5 6 10 8 출력 예제 6 풀이 코드 고민 좀 많이 했는데, 최대 부분 증가수열과 완전히 똑같은

원문보기 내부링크
Naver Blog

Unity 스탯 컨트롤러

Stat Controller 개요 게임을 개발하다 보면 한 번쯤은 스탯 시스템에 대해 고민해야 할 순간이 찾아온다. 특히나 캐릭터의 움직임이나 아이템, 성장이 있는 게임이라면 더더욱 많이. 이 시스템은 의미론적 수치를 개별 데이터로서 가공하기 쉽도록 관리할 수 있어야 되며, 장르나, 기획에 따라, 엔티티의 개별 스과 공통적으로 소유하는 스탯을 구분해야 되고, 버프 / 디버프 등으로 각 스탯별 증가나, 감소, 고정 등의 복잡한 상황도 고려해야 된다. 스탯을 개별 객체로 다룰 것인지, 아니면 통합 객체로 다룰 것인지도 생각해 봐야 된다. (이 경우 대부분의 경우 전자가 확장하기 유리하긴 하다) 마침 버프를 구현할 일이 생겨서 이참에 한 번 만들어보자는 생각으로 스탯 컨트롤러를 구현해 보았다. 개발을 다 끝내진 않았지만, 일단 오픈소스로 올려둡니다. GitHub - Stellar-F0X/Stat-Controller Contribute to Stellar-F0X/Stat-Controller

원문보기 내부링크
Naver Blog

순열 구하기

문제 설명 자연수 N과 R이 주어지면 서로 다른 N개의 자연수 중 R개를 뽑아 일렬로 나열하는 프로그램 을 작성하세요. 입력설명 첫 번째 줄에 자연수 N(1<=N<=15)과 R(0<=R<=15)이 주어진다. 단, (N>=R) 두 번째 줄에 N개의 서로 다른 자연수가 오름차순으로 주어진다. 출력설명 순열의 각 경우를 아래와 같이 오름차순으로 출력한다. 마지막 줄에 총 개수도 출력한다. 입력예제 4 3 1 3 6 7 출력예제 1 3 6 1 3 7 1 6 3 1 6 7 1 7 3 1 7 6 3 1 6 3 1 7 3 6 1 3 6 7 3 7 1 3 7 6 6 1 3 6 1 7 6 3 1 6 3 7 6 7 1 6 7 3 7 1 3 7 1 6 7 3 1 7 3 6 7 6 1 7 6 3 24 소스 코드 재귀적 호출로 인해 직전에 방문한 노드가 Block되고, 현재 스택에서 벗어날 때, Block이 해제된다. 아래 사진을 보면 초록색 노드는 현재 방문 중인 노드라 방문이 Block되어 있어, 다른

원문보기 내부링크
Naver Blog

복면산 SEND+MORE=MONEY

문제 설명 SEND+MORE=MONEY 라는 유명한 복면산이 있습니다. 이 복면산을 구하여 A + B = C 형태로 출력하는 프로그램을 작성 하세요. 출력 예제 9567 + 1085 = 10652 소스 코드 보자마자 방정식이 떠올라서 자리에 따른 10의 제곱수와 미지수의 조합으로 표현하니, 접근하기 쉬웠다. 여기서 브루트 포스를 돌리면 되는데, 복면산의 규칙상 앞 자리는 0이 되면 안된다는 암묵적인 기본 규칙이 있음. 때문에 S와 M이 0이 되는 경우를 if문으로 배제해주고 위 방정식이 성립되지 않는 값들도 배제해준다. 결과적으로 10652라는 값만 나오게 된다. #include <iostream> #include <vector> using namespace std; enum ABC { S, E, N, D, M, O, R, Y }; vector<int> res(8); vector<bool> vis(10); void DFS(int depth) { if (depth == 8) { if

원문보기 내부링크
Naver Blog

휴가

문제 설명 상담사 현수는 휴가를 떠나기 전에 가능한 많은 상담을 하여 최대한 많은 돈을 벌려고 한다. 각 상담은 소요 기간(T)과 상담료(P)가 정해져 있다. 상담은 매일 하나씩 서로 다른 사람으로 예약되어 있고, 한 번에 한 가지 상담만 가능하다. 상담이 진행되는 동안 다른 상담은 할 수 없다. N+1일에 휴가를 가기 때문에 그 전날까지만 상담을 할 수 있다. 구분 1일 2일 3일 4일 5일 6일 7일 T(상담기간) 4 2 3 3 2 2 1 P(상담료) 20 10 15 20 30 20 10 상담사가 얻을 수 있는 최대 수익은 1일(20), 5일(30), 7일(10)의 상담을 하는 것이며, 총 60이 된다. 목표는 상담사가 N일 동안 얻을 수 있는 최대 수익을 계산하는 프로그램을 작성하는 것이다. 입력예제 7 4 20 2 10 3 15 3 20 2 30 2 20 1 10 출력예제 60 구현 코드 특정 일정에 있는 상담을 수락한 경우와 그렇지 못한 경우를 나누어 탐색한다. 수락하기 전

원문보기 내부링크
Naver Blog

수식 만들기

문제 설명 길이가 N인 자연수로 이루어진 수열과 수열의 각 항 사이에 끼워 넣을 N-1개의 사칙연산자가 주어집니다. 수열의 순서는 그대로 유지한 채 각각의 수 사이에 N-1개의 연산자를 적절히 배치하면 다양한 수식이 나옵니다. 수열이 1 2 3 4 5이고 덧셈 1개, 뺄셈 1개, 곱셈 1개, 나눗셈 1개일 때, 1+2*3-4/5라는 수식을 만들었다 가정. 이때 연산자 우선순위를 따지지 않고 맨 앞쪽부터 계산한다면 결과는 1이 나옵니다. 길이 N 수열과 N-1개의 연산자가 주어졌을 때, 만든 수식들 중에서 구한 최대, 최소를 출력하는 프로그램을 작성. 입력 예제 3 5 3 8 1 0 1 0 출력 예제제 64 //(5+3*8) 23 //(5*3+8) 풀이 코드 숫자 수열은 변하지 않는 것을 보고, 연산자 수열을 구하는 부분과 총 결과를 구하는 부분으로 나누고 단계를 구성. 1. 숫자 수열을 변하지 않고 연산자의 수열만 바뀜. (즉, 여러 경우의 연산자 수열을 만드는 것이 핵심) 2. 만

원문보기 내부링크
Naver Blog

피자 배달 거리

문제 설명 도시는 N × N 크기의 격자로 구성되어 있고, 각 칸은 빈칸(0), 집(1), 피자집(2) 중 하나로 표시된다. 각 집은 피자를 받을 때 도시에 존재하는 피자집 중 가장 가까운 피자집 한 곳에서만 받게 되며, 이때의 거리를 그 집의 “피자 배달 거리”라고 한다. 하지만 최근 불경기로 인해 모든 피자집을 유지할 수는 없게 되었다. 그래서 시장은 M 개의 피자집만 선택해서 유지하고 나머지 피자집은 폐업시키려 한다. 이때 M 개의 피자집을 어떻게 고르느냐에 따라 각 집이 가장 가까운 피자집까지 가는 거리도 달라지게 된다. 전체 피자집들 중 M 개를 선택하여, 각 집에서 가장 가까운 피자집까지의 거리와 그 거리들의 총합을 최소화하라. 각 격자칸은 좌표(행 번호, 열 번호)로 표현된다. 거리 계산은 맨해튼 거리로, 두 위치 (x1, y1), (x2, y2)의 거리는 |x1 - x2| + |y1 - y2|로 구한다. 예를 들어 아래 사진에서 (1, 2)에 있는 집과 (2, 3)에

원문보기 내부링크
Naver Blog

여행가자

문제 설명 풀이 코드 문제 극초반에 배열 초기화와 연산을 동시에 한 부분에서 특정 조건시 배열 인덱스 초과가 발생할 수 있다는 것을 간과해서 시간이 좀 걸렸다. #include <iostream> #include <vector> using namespace std; int n, m; vector<int> uniSet; vector<int> travasal; int Find(int idx) { if (idx == uniSet[idx]) return idx; return uniSet[idx] = Find(uniSet[idx]); } void Union(int x, int y) { int a = Find(x); int b = Find(y); uniSet[b] = a; } int main(int argc, char** argv) { ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0); int tmp; cin >> n >> m; uniSet

원문보기 내부링크
Naver Blog

유니티 Behavior Tree 에디터 개발

목차 구현한 기능 발생한 문제와 해결 조건적 실행 노드 중단 병렬 실행 노드 중단 제로 가비지 구현 후기 개요 5월 말부터 1년 만에 다시 만들기 시작했다. 유니티에서 직접 만든 Behavior Tree 에디터 GitHub - Stellar-F0X/Unity-Behaviour-System Contribute to Stellar-F0X/Unity-Behaviour-System development by creating an account on GitHub. github.com Behavior Tree에 대한 자세한 설명은 구글이나 다른 자료에서 충분히 찾아볼 수 있으므로 여기서는 간략히만 소개한다. 행동 트리는 노드 기반으로 AI의 행동을 계층적으로 구성하여, 순차적, 선택적으로 조건 분기 및 실행 순서를 제어하는 구조이다. 게임 AI 구현 시 Finite State Machine(FSM)과 함께 사용되거나, FSM을 대체하는 방식으로 자주 활용된다. 구현 기능 직접 노드를 구성하고

원문보기 내부링크
Naver Blog

유니티 BT + FSM 에디터

상위 노드에서 서브 그래프(BT / FSM) 노드를 호출하면 서브 그래프의 Root / Enter 노드에서 호출되는 식이다. 에디터 형태는 완성이 됐다. + 수정 Task Streamer 라는 이름으로 기능 자체는 완성했다. 유니티 Task Streamer 개발 작업 중개자 (Task Streamer) 유니티에서 Behavior Tree와 Finite State Machine을 병합한 그래프 ... m.blog.naver.com 문제 발생 스크립터블 오브젝트(SO)는 그대로 사용한다면 싱글톤을 사용하는 것과 같다. 노드와 그래프, 블랙보드는 스크립터블을 상속받았고 따라서 플레이 모드 진입할 때, 인스턴스로 만들어줘야 된다. 문제는 새롭게 만들어진 노드의 필드에 등록된 블랙보드 변수 (Blackboard Variable)에 있다. Behavior Tree의 Action 노드 중 하나인 CrossFade 노드의 필드 사진을 보면 필드 BlackboardVariable 객체가 있는데, 이

원문보기 내부링크
Naver Blog

Unity 직렬화 가능한 GUID

개요 유니티에서 직렬화 가능한 GUID를 만들었다. 요즘 만들고 있는 그래프 에디터에서 사용되는 Guid로 사진의 3번째 프로퍼티처럼 그려진다. Unity serializable GUID Unity serializable GUID. GitHub Gist: instantly share code, notes, and snippets. gist.github.com GUID Globally Unique Identifier 라는 의미로 프로그램에서 객체나 데이터 식별을 위해 사용되는 고유한 식별자. 보통 16Byte로 구현하며, 겹칠 확률이 1/2^128 이기 때문에 생성 시에 별도의 중복 검사는 하지 않는다고 한다. 참고로 2^128은 340282366920938463463374607431768211456로 정신 나간 수임을 알 수 있으며 만약 데이터나 객체 간에 Guid가 겹쳐 프로그램에서 오류가 발생한다면 개발을 멈추고 당장 로또를 사러 가자. UUID가 겹치면 어쩌지? 이 글은 kor

원문보기 내부링크
Naver Blog

Unity 스크립트 템플릿 만들기

스크립트 템플릿이란 Unity 6 유니티 프로젝트 뷰에서 새로운 MonoBehaviour 스크립트를 생성하면 기본적으로 적혀있는 코드가 있다. 이렇게 기본적으로 제공되는 코드가 포함되는 형태를 스크립트 템플릿이라고 하는데 보통 규칙적인 클래스를 반복 생성해야 되는 경우와 코드 제너레이터를 쓰기 애매할 경우에 쓰기 좋다. using UnityEngine; public class NewMonoBehaviourScript : MonoBehaviour { //주석 어쩌구 void Start() { } //주석 저쩌구 void Update() { } } 이렇게 제공되는 기본 스크립트는 수정할 수도 있고 새롭게 추가할 수도 있다. 기본으로 제공되는 템플릿을 수정하려면 에디터가 깔려있는 폴더에서 다음 경로로 들어가면 볼 수 있다. __에디터_버전__\Editor\Data\Resources\ScriptTemplates 스크립트 템플릿 만들기 템플릿을 만드는 방법은 여러 가지가 있지만 해당 포스팅에

원문보기 내부링크
Naver Blog

섬나라 아일랜드

문제 설명 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다. 각 섬은 1로 표시되어 상하좌우와 대 각선으로 연결되어 있으며, 0은 바다입니다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요. 입력예제 7 1 1 0 0 0 1 0 0 1 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 1 1 1 1 0 1 1 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 출력예제 5 풀이 코드 문제의 핵심은 섬을 어떻게 카운팅 하냐 였는데 개발하느라 간만에 풀어서 머리 좀 아픈 문제였다. 솔루션은 간단하게 처음 진입하는 칸이 섬이라면 카운트를 하나 증가시킨 후 섬 전체를 마킹해버린다. 그리고 이후 방문했을 때 그 칸이 마킹되어 있으면 그냥 나가면 된다. 결과적으로 마킹되지 않았으면 그 섬은 처음 방문한다는 의미가 됨. 왜냐하면 첫 방문때 그 섬 전체를 마킹해버리기 때문이다. 거기에 조금 더 효율성을 챙기기 위해 섬을 이루는 칸의 인덱스를 저장해놓고 그

원문보기 내부링크
Naver Blog

최소 비용

문제 설명 가중치 방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 최소비용을 출력하는 프로그램을 작성하세요. 입력 예제 5 8 1 2 12 1 3 6 1 4 10 2 3 2 2 5 2 3 4 3 4 2 2 4 5 5 출력 예제 13 소스코드 가중치가 있는 방향 그래프이지만 인접 리스트를 활용한 DFS로 풀어보았다. #include <iostream> #include <vector> using namespace std; struct node { int des; int wei; }; int n, m, mi=1e9; vector<vector<node> > map; vector<bool> v; void DFS(int idx, int sum) { if (idx == n) { mi = min(mi, sum); return; } for (int i=0; i<map[idx].size(); ++i) { node nd = map[idx][i]; if (v[nd.des]) continue; v[

원문보기 내부링크
Naver Blog

송아지 찾기

문제 설명 현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치 추적기가 달려 있다. 현수의 위치와 송아 지의 위치가 직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다. 현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요. 입력 예제 5 14 출력 예제 3 문제 풀이 계속 틀리다고 나와서 다시 생각해 보니 송아지가 현수보다 뒤에 있을 경우를 고려하지 못했다. 이를 고려해서 다시 제출하니 시간 초과가 나와서 if 문으로 경우를 나눠줬더니 풀이에 성공했다. #include <iostream> #include <utility> #include <queue> #include <vector> using namespace std; queue<pair<int,int>> q; vector<bool> visite

원문보기 내부링크
Naver Blog

요세푸스 문제

문제 설명 문제 풀이 큐를 사용해서 k번째 사람이라면 내보내고 아니라면 큐에 다시 삽입한다. 입력 순서와 상관없이 k번째가 아닌 사람들은 다시 순서대로 쌓아지는데, 이때 쌓아진 사람들 중에서 다시 k번째에 위치한 사람을 내보내는 것을 반복한다. #include <iostream> #include <queue> using namespace std; queue<int> q; int main(int argc, char** argv) { int n, k; cin >> n >> k; for (int i=0; i<n; ++i){ q.push(i + 1); } printf("<"); while (!q.empty()) { for (int i=0; i<k-1; ++i) { q.push(q.front()); q.pop(); } printf("%d", q.front()); q.pop(); if (!q.empty()) { printf(", "); } } printf(">"); return 0; }

원문보기 내부링크
Naver Blog

미로 탐색

문제 설명 소스코드 넓이 우선 탐색 (BFS)를 사용해서 각 칸 별, Weight를 더해가며 탐색한다. 탐색을 종료해야 될 조건에 해당된다면 큐에 이동할 칸을 쌓지 않고 넘어간다. 만약 현재 위치가 문제에서 요구하는 칸의 위치와 일치한다면 그 동안 쌓아왔던 Weight를 반환한다. BFS는 인접칸을 균일하게 탐색하기 때문에 가장 먼저 도달한 경우가 가장 가까운 탐색 거리이므로 이러한 풀이가 성립됨. #include <iostream> #include <vector> #include <queue> using namespace std; struct vertex { int x; int y; int bx; //previous x int by; //previous y }; queue<vertex> vertices; vector<vector<int> > visited; vector<vector<int> > map; char buff[101]; int n, m, res; //m: x, n: y

원문보기 내부링크
Naver Blog

최대 수입 스케줄

문제 설명 현수는 유명한 강연자이다. N 개의 기업에서 강연 요청을 해왔다. 각 기업은 D 일 안에 와서 강 연을 해 주면 M 만큼의 강연료를 주기로 했다. 각 기업이 요청한 D와 M를 바탕으로 가장 많을 돈을 벌 수 있도록 강연 스케줄을 짜야 한다. 단 강연의 특성상 현수는 하루에 하나의 기업에서만 강연을 할 수 있다. 입력 예제 6 50 2 20 1 40 2 60 3 30 3 30 1 출력 예제 150 소스코드 #include <iostream> #include <vector> #include <queue> using namespace std; int main(int argc, char** argv) { int n, mxd=0, sum=0; cin >> n; vector<vector<int> > v(n+1); priority_queue<int> q; for (int i=0; i<n; ++i) { int m, d; cin >> m >> d; v[d].push_back(m); mxd

원문보기 내부링크
Naver Blog

이항 계수 1

문제 설명 소스 코드 #include <iostream> #include <vector> using namespace std; int mem[21][21] {0}; int DFS(int n, int r) { if (mem[n][r]) return mem[n][r]; if (n == r || !r) return 1; return mem[n][r] = DFS(n-1, r-1)+DFS(n-1, r); } int main(int argc, char** argv) { int n, r; cin >> n >> r; cout << DFS(n, r) << endl; return 0; }

원문보기 내부링크
Naver Blog

이항 계수 2

문제 설명 소스 코드 #include <iostream> using namespace std; int mem[1001][1001] = {0}; int DFS(int n, int r) { if (mem[n][r]) return mem[n][r]; if (n == r || r == 0) return mem[n][r] = 1; return mem[n][r] = (DFS(n-1, r-1) + DFS(n-1, r)) % 10007; } int main() { int n, r; cin >> n >> r; cout << DFS(n, r) << endl; return 0; }

원문보기 내부링크
Naver Blog

친구인가 (Union & Find 응용)

문제 설명 오늘은 새 학기 새로운 반에서 처음 시작하는 날이다. 현수네 반 학생은 N명이다. 현수는 각 학생들의 친구관계를 알고 싶다. 모든 학생은 1부터 N까지 번호가 부여되어 있고, 현수에게는 각각 두 명의 학생은 친구 관계 가 번호로 표현된 숫자쌍이 주어진다. 만약 (1, 2), (2, 3), (3, 4)의 숫자쌍이 주어지면 1번 학 생과 2번 학생이 친구이고, 2번 학생과 3번 학생이 친구, 3번 학생과 4번 학생이 친구이다. 그리고 1번 학생과 4번 학생은 2번과 3번을 통해서 친구관계가 된다. 학생의 친구관계를 나타내는 숫자쌍이 주어지면 특정 두 명이 친구인지를 판별하는 프로그램 을 작성하세요. 두 학생이 친구이면 “YES"이고, 아니면 ”NO"를 출력한다. 입력 예제 9 7 1 2 2 3 3 4 4 5 6 7 7 8 8 9 3 8 출력 예제 NO 소스 코드 풀이1 DFS 친구의 수 N(1<=N<=1,000)과 숫자쌍의 개수인 M(1<=M<=3,000)이라 반복문으로 DF

원문보기 내부링크
Naver Blog

원더랜드 (쿠르스칼 알고리즘 응용)

문제 설명 원더랜드에 문제가 생겼다. 원더랜드의 각 도로를 유지보수하는 재정이 바닥난 것이다. 원더랜드는 모든 도시를 서로 연결하면서 최소의 유지비용이 들도록 도로를 선택하고 나머지 도로는 폐쇄하려고 한다. 어떤 도로는 도로를 유지보수하면 재정에 도움이 되는 도로도 존재 한다. 재정에 도움이 되는 도로는 비용을 음수로 표현했다. 아래의 그림은 그 한 예를 설명하는 그림이다. 위의 지도는 각 도시가 1부터 9로 표현되었고, 지도의 오른쪽은 최소비용 196으로 모든 도시 를 연결하는 방법을 찾아낸 것이다. 첫째 줄에 도시의 개수 V(1≤V≤100)와 도로의 개수 E(1≤E≤1,000)가 주어진다. 다음 E개의 줄에는 각 도로에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 도시와 B번 도시가 유지비용이 C인 도로로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다. 입력 예제 9 12 1 2 12 1 9 25 2 3 10

원문보기 내부링크
Naver Blog

원더랜드 (Prim 알고리즘 응용)

개요 어제 풀었던 문제와 같은 문제로 그땐 쿠르스칼 알고리즘으로 최소 신장 트리를 구현했지만 이번엔 우선순위 큐와 그래프 탐색 방법 중 하나인 DFS를 통해 Prim 알고리즘을 응용해보았다. 원더랜드 문제 설명 원더랜드에 문제가 생겼다. 원더랜드의 각 도로를 유지보수하는 재정이 바닥난 것이다. 원더랜드... blog.naver.com 소스 코드 프림 알고리즘 개요. 출처: https://toastfactory.tistory.com/184 그래프를 순회하기 때문에 여타 그래프 탐색 알고리즘처럼 Visited로 정점에 재방문을 방지해줘야 된다. #include <iostream> #include <algorithm> #include <queue> #include <vector> using namespace std; struct way { int to; int dis; bool operator()(way& a, way& b) { return a.dis > b.dis; } }; vector

원문보기 내부링크
Naver Blog

다익스트라 (Dijkstra)

개요 최소 이동 비용을 구하는 머리 아픈 알고리즘으로 특정 노드에서 연결된 다른 노드로 이동하며 비용을 구한다 네트워크에서 라우터나 게임에서 길 찾기 알고리즘 등, 여러 곳에서 사용되는 유명한 알고리즘이다. 에츠허르 다익스트라가 고안했다. 개인적인 생각이지만 막상 구현해 보면 BFS를 통해 각 정점까지의 거리를 구하는 것과 크게 다를 것 없는 것 같다. 아무래도 그래프를 기반으로 하니 그런 것 같고, 가장 큰 차이는 비용을 갱신한다는 점이다. 알고리즘 자체는 이중 배열로도 구현 가능하지만, 효율성을 우선하여 웬만하면 우선순위 큐를 함께 사용한다. 코드 구현 간선 (Edge)를 구조체로 구현하고 우선순위 큐를 사용하기 위해 연산자 오버 로딩도 함께 구현해 줬다. struct way { int idx; int dis; bool operator()(way& a, way& b) { return a.dis > b.dis; } }; 각 정점별로 비용을 저장할 int 배열, cost와 그래프를

원문보기 내부링크
Naver Blog

도시간 이동 비용 (벨만 포드 응용)

문제 설명 N개의 도시가 주어지고, 각 도시들을 연결하는 도로와 해당 도로를 통행하는 비용이 주어질 때 한 도시에서 다른 도시로 이동하는데 쓰이는 비용의 최소값을 구하는 프로그램을 작성하세요. 첫 줄에 도시의 수N(N<=100)과 도로수 M(M<=200)가 주어지고, M줄에 걸쳐 도로정보와 비용이 주어진다. 만약 1번 도시와 2번도시가 연결되고 그 비용이 13이면 “1 2 13”으로 주어진다. 그 다음 마지막 줄에 출발도시와 도착도시가 주어진다. 입력예제 5 7 1 2 5 1 3 4 2 3 -3 2 5 13 3 4 5 4 2 3 4 5 7 1 5 출력예제 14 소스 코드 아래 영상을 참고하여 구현해보았다. #include <iostream> #include <vector> using namespace std; struct Edge { int from; int to; int dis; }; vector<Edge> map; vector<int> dist; int n, m; //Relax는

원문보기 내부링크
Naver Blog

타임머신

문제 설명 https://www.acmicpc.net/problem/11657 소스 코드 #include <iostream> #include <vector> #define INF 10000000000 using namespace std; long long int typedef lli; struct edge { int from; int to; lli dis; }; vector<edge> map; vector<lli> dist; int n, m; bool canRelax(const int i) { int f = map[i].from; int t = map[i].to; return dist[f] != INF && (dist[f] + map[i].dis) < dist[t]; } bool bellmanFord(const int start) { dist[start] = 0; for (int i=1; i<n; ++i) { for (int j=1; j<=m; ++j) { if (canRelax(j

원문보기 내부링크
Naver Blog

부분합

문제 설명 https://www.acmicpc.net/problem/1806 소스 코드 O(N)에 풀면 되므로 투 포인터 알고리즘을 통해 입력과 동시에 수행. #include <iostream> #include <vector> using namespace std; int main(int argc, char** argv) { ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, s, p1=0, p2=0, sum=0, m=1e9; cin >> n >> s; vector<int> v(n); while(p2 < n || sum >= s) { if (sum < s) { cin >> v[p2]; sum += v[p2++]; } else if (p1 < p2) { m = min(m, p2-p1); sum -= v[p1++]; } } cout << (m == 1e9 ? "0" : m) << endl; return 0; }

원문보기 내부링크
Naver Blog

설탕배달

문제 설명 https://www.acmicpc.net/problem/2839 문제 풀이 #include <iostream> #include <vector> using namespace std; int main(int argc, char** argv) { ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; for (int p3=0; p3 <= 1670; ++p3) { int r = n - p3 * 3; if (r % 5 == 0) { cout << p3 + r / 5; return 0; } else if (r < 0) { cout << "-1" << endl; return 0; } } return 0; }

원문보기 내부링크
Naver Blog

미로 길 찾기

문제 설명 7*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성하세요. 출발점은 격 자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 통로이다. 격 자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면 아래의 지도에서 출발점에서 도착점까지 갈 수 있는 방법의 수는 8가지이다 입력설명 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 0 0 0 1 1 0 1 0 1 1 1 1 0 0 0 0 1 1 1 0 1 1 0 0 1 0 0 0 0 0 0 출력예제 8 문제 풀이 이전 문제와 크게 다를 것 없는 것 같다. 그래프는 경로가 정해져있는 반면 미로는 직접 길을 찾아야 된다 정도. search 함수에서 종료 조건을 체크하고나서, 현재 길로 이동 금지를 설정 후 4방을 탐색하는 것이 핵심. 갈 수 있는 길들을 4방향으로 탐색하며 길이 막힐 경우, 백트랙킹으로 나와서 재귀를 통해 다른 길을 찾는다. #includ

원문보기 내부링크
Naver Blog

[C++] 그래프 경로 출력

별거 아니지만 오랜만에 해보려고 하면 헷갈릴 때가 많아서 블로그에 정리. 전위: 노드를 탐색하기 직전에 경로에 기록 후위: 자식 노드 탐색이 끝난 후 경로에서 제거 출력: 목적지 도달 시점에서 경로 전체 출력 void DFS(int i, int depth) { if (i == n) { recorder.push_back(i); for (int c=0; c<recorder.size(); ++c) { printf("%d ", recorder[c]); } recorder.pop_back(); putchar('\n'); } if (depth == n) return; for (int j=0; j<map[i].size(); ++j) { if (vis[map[i][j]]) continue; vis[i] = true; recorder.push_back(i); DFS(map[i][j], depth+1); recorder.pop_back(); vis[i] = false; } }

원문보기 내부링크
1