thisisuser's study

문제 링크 https://www.acmicpc.net/problem/17081 17081번: RPG Extreme 요즘 택희는 RPG 게임을 하고 있다. 던전을 헤쳐나가며 몬스터를 물리치고, 아이템을 모으고, 레벨 업을 하여 보스 몬스터를 물리치는 전형적인 RPG 게임이다. 이 게임은 N×M 2차원 그리드 위에서 www.acmicpc.net 문제 선정 과정 별다른 알고리즘 없이, 문제에서 지시하는 내용들을 그대로 구현하면 되는 문제로 보였습니다. 다만 구현량이 꽤 많아 보이기 때문에, 객체 지향 프로그래밍을 지향하며 코드를 짜는 문제로 보였습니다. 문제 풀이 전략 객체 지향 프로그래밍 (Object-Oriented Programming, OOP)이란 컴퓨터 프로그래밍 패러다임의 일종으로, 프로그램을 수많..

문제 링크https://www.acmicpc.net/problem/16404 16404번: 주식회사 승범이네첫 번째 줄에 승범이를 포함한 판매원들의 수 N(1 ≤ N ≤ 100,000), 명령의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 판매원들은 1번부터 N번까지 번호가 매겨지며, 승범이는 항상 1번이다. 두 번째 줄에 판www.acmicpc.net 문제 선정 과정서브트리 전체의 값에 업데이트를 해야 하는데, 제한을 보니 이를 $logN$에 끝내야 하는 것으로 보였습니다.그냥 배열로도 단순히 풀면 나오지 않는 시간 복잡도인데 이를 트리에서 시행해야 한다는 점에서 꽤나 어려운 문제라 생각했습니다. 문제 풀이 전략문제를 모델링하면 다음과 같습니다.정점이 N개인 트리에 다음 두 가지 쿼리가 주어집니다..

문제 링크 https://www.acmicpc.net/problem/3830 3830번: 교수님은 기다리지 않는다 교수님의 질문 (? a b)이 입력으로 들어올 때 마다, 지금까지 측정한 결과를 바탕으로 a와 b의 무게 차이를 계산할 수 있다면, b가 a보다 얼마나 무거운지를 출력한다. 무게의 차이의 절댓값이 1,000, www.acmicpc.net 문제 선정 과정 그래프 기반 문제로, 온라인 쿼리로 간선이 추가되며 두 정점 사이의 거리를 구해야 하는 문제로 보였습니다. 난이도도 적당해 보이기 때문에 이 문제를 풀기로 하였습니다. 문제 풀이 전략 문제를 모델링하면 다음과 같습니다. $N$개의 정점에 대하여 두 가지의 쿼리가 주어집니다. 쿼리 1: 가중치가 있는 방향 간선이 추가됩니다. 쿼리 2: 두 정점..

문제 링크 Codeup: 5313 잔디밭의 개미굴 고등3) KOI 공원의 잔디밭에는 여러 개미가 모여 사는 개미굴이 있다. 개미굴은 $N$ 개의 방으로 구성되어 있으며, 서로 다른 두 개미굴을 직접 잇는 $N - 1$ 개의 통로가 있고, 임의의 서로 다른 두 codeup.kr Baekjoon: 28328 28328번: 잔디밭의 개미굴 KOI 공원의 잔디밭에는 여러 개미가 모여 사는 개미굴이 있다. 개미굴은 $N$ 개의 방으로 구성되어 있으며, 서로 다른 두 개미굴을 직접 잇는 $N - 1$ 개의 통로가 있고, 임의의 서로 다른 두 개미굴 www.acmicpc.net 문제 선정 과정 먼저 문제가 굉장히 길었다. 대략적으로 요약하면 다음과 같다. 트리 구조의 그래프가 주어지고, 각 노드는 0 또는 1의 데이..