고양멍멍이

[문제링크] 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 0. 단순한 구현 문제 - 2-b 수행하기 전 2-c,d먼저 조건 체크/수행해야한다 1. 현재 위치를 청소하며 clean 수치를 1씩 증가시킨다 2. 2-c,d 조건 체크를 위해 4방향 탐색 3. 4방향 다 벽/청소가 끝났다면 현 위치의 뒤를 확인하여 벽이라면 종료한다 (2-d) 4. 벽이 아니라면, 뒤로 물러난다 (2-c) 5. 왼쪽에 빈공간이 있다면, 회전 후 1칸 진행한다 (2-a) 4. 없다면, 회전한다 (2-b) import java.io...

[문제링크] 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 0. N세대 드래곤 커브란? N-1세대 드래곤 커브를 끝 점 기준 90도 회전시켜 N-1세대의 끝 점에 붙인 것 - 한 세대마다 2배씩 증가하지만, 세대가 최대 10이므로 최대 pow(2,10), 1024개의 지점으로 구성된다 1. N세대 드래곤 커브를 만들기 위해선? - N-1세대의 끝 점에서 시작해, N-1세대 커브의 구성을 역순으로 90도 회전시켜서 적용한다 - 예를들어, 위 2세대 커브는 →↑←↑ 순서로 이루어져 0,..

※ 2024. 09. 01 추가사항  파판 14 7.0 패치에 파판 9 관련 오마주가 많을 예정이라 그런지, 살짝 파판9 유저가 늘어난 느낌이더라구요 마침 모그리모드도 9.0으로 버전업되고, UnityEx 버전도 여러번 변경되어 관련 내용 최신화를 진행할 필요를 느꼈습니다 이에 기본 파판 9 게임에서 모그리모드와 한글패치까지 진행하는 과정을 영상 + 설명 자막으로 만들었습니다 아래 내용들은 24.09 이전 작성된 내용으로, 현 시점에서 다르게 진행되는 경우가 있습니다.참고용으로 내용은 유지하지만, 영상 위주로 진행 바랍니다.  ※ 모그리 모드란?HD 배경, 텍스쳐 지원 (핵심)다양한 버그 수정화면 비율 조정 및 폰트변경전투 속도 조정  등 다양한 기능을 제공해주는 파판 9 모드입니다.   ※ 기존 파판9..

[문제링크] 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 0. 기초적인 MST 문제 (MST란?) 1. PRIM 알고리즘 사용, 최소 거리로 갈수있는 & 미방문한 노드 순서로 방문한다 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import java.util.StringTokenizer; public class Main{ public static void main(String[] args)throws Exception { Buff..

[문제링크] 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 0. 집 사이의 연결을 유지하며 길을 제거하고, 최소 비용의 길들을 사용해 전체를 연결하기 == 최소 신장 트리(MST) 1. 최소 신장 트리를 구하면 최소 거리의 길들로 모든 마을을 연결할 수 있다 2. 완성된 MST의 간선들 중 하나를 제거하면 2개의 tree가 생성된다 - 마을을 2개로 분리할 수 있다 3. 길의 유지비의 합은 항상 최소를 유지해야하므로, MST를 이루는 간선들 중 가중치가 가장 큰 간선 하..

[문제링크] 1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net 0. 모든 경우의 수에 대해 계산하는 브루트-포스 방식 1. 벡터는 두 점 A, B가 있을때 A-B / B-A 같은 식으로 만들 수 있다 - 한 점은 +, 한 점은 - 하게 된다 2. 즉, 2N개의 점으로 N개의 벡터를 만들었을때 그 벡터들의 합은 N개의 점을 +, 나머지 N개는 - 한 값이다 3. 점이 최대 20개인데, 20개 중 10개를 뽑는 조합의 경우의 수 20C10은 184756으로 산술 시간안에 충분히 해결 가능하다 4. 10개의..

[게시글링크] 글 읽기 - ✅ (수정) solved.ac 1주년 (2021년 6월 5일) 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net solved.ac 1주년 기념으로 뱃지 / 프로필 배경을 증정한다고 합니다 참여방법 : 이전에 푼 적 없는 문제 1문제 해결 참여기간 : 5/31 ~ 6/7 뱃지와 프로필 배경은 프로필 - 프로필 편집에서 추가/변경 가능합니다

1. 신장 트리(Spanning Tree) 그래프의 모든 정점을 최소한 적은 간선만 사용해 연결하는 트리를 말한다 정점이 N개라면 N-1개의 간선만 사용해 모든 정점을 연결한 형태를 이루게 된다 신장 트리는 그 구조상 사이클을 포함하지 않는다 만드는 방법 : 한 정점을 기준으로 DFS/BFS를 실행할 때, 탐색한 간선들이 곧 하나의 신장 트리가 된다 2. 최소 신장 트리(Minimum Spanning Tree, MST) 최소 신장 트리란, 가중치 있는 그래프에서, 신장트리를 이루는 간선의 가중치 총합이 최소가 되는 신장트리를 말한다 모든 정점들을 최소 비용으로 연결하는 것 3. 최소 신장 트리 구현 크루스칼(KRUSKAL) 알고리즘 (간선 기반) Greedy하게 간선을 선택하여 최소 신장 트리를 완성한다..

1. Graph 자료구조 Graph란, 정점(node, vertex)과 정점 사이를 잇는 간선(edge, link)으로 구성된 자료구조이다 객체와 객체 사이의 관계를 나타내는데 좋은 자료구조로, 지하철 노선도, 비행기의 항로, 도로 등 다양하게 응용 가능하다 2. Graph의 구성 정점 : Graph에 속한 객체 (노선도의 경우 각 역) 간선 : 정점 사이의 관계를 나타내는 선 (두 역 사이에 지하철이 다니면 선이 존재하지만, 다니지 않으면 존재하지 않는다) 차수 : 정점에 연결된 간선의 갯수 (신촌역은 차수가 2이지만, 왕십리역은 차수가 6이다) 입력 차수(진입 차수) : 방향 그래프의 경우, 정점으로 들어오는 간선의 갯수 출력 차수(진출 차수) : 방향 그래프의 경우, 정점에서 나가는 간선의 갯수 사..

그래프부터 알아보기 1. 너비 우선 탐색 (BFS) 현재 탐색 정점과 인접한 노드들을 우선 탐색한다 A정점에서 시작했다면, A-B를 탐색한 후 B의 인접노드인 D/E가 아닌 C를 우선 탐색한다 시작 노드로부터 거리가 1인 모든 정점 탐색 - 거리가 2인 모든 정점 탐색 - 거리가 3인.... 최단거리 찾기, A-B 사이 거리 찾기 등에 활용 가능하다 FIFO 자료구조인 큐를 사용하여 구현한다 A탐색 - B/C를 offer - B pop, 탐색 - D/E를 offer - C pop, 탐색 - ..... 2. 깊이 우선 탐색 (DFS) 더 이상 깊이 갈수 없을때까지 우선 탐색하며, 탐색할 노드가 없으면 부모 노드로 돌아온다 A정점에서 시작했다면, A-B를 탐색한 후 B의 인접노드인 D - D의 인접노드인 H..