전체 글
백준 1238 : 파티 / 플로이드 워셜 알고리즘
문제 문제 분석 노드간의 최단거리를 만들어 두고, 파티 노드 X로 오고 가는 거리의 최댓값을 구하는 문제였다. 즉, 모든 노드간의 거리가 최단거리라고 할 때 A -> X -> A의 최댓값을 구하는 문제였다. 모든 노드로 부터 모든 노드로의 최단거리 문제를 구하는 문제였으므로 Floyd-warshall 알고리즘을 적용시켜서 풀면 된다고 생각했다. 근데 ㅋㅋㅋㅋ 적용시키면 풀릴것같은데 구현을 까먹었어서 잠시 현타가 왔었다. 아직 내 지식이 아닌가보다 하고 다시 서치했다. 알고리즘의 핵심은 모든 경로에 대해서 모든 노드를 거쳐갈 때를 확인하는 것이다. 즉, 1->3이라는 경로가 존재할 때 1->(2,4....) ->3 와 같이 그 외의 모든 노드를 중간에 넣어보면서 그 노드가 들어갈 때 총 거리가 더 줄어드는..
백준 20543 번 : 폭탄 던지는 태영이 / 2D prefix-sum
문제 1 ≤ M ≤ N ≤ 2,000 (M은 홀수) -2,147,483,648 ≤ H[r][c] ≤ 0 문제 분석 정말 어려운 문제였다. 해결할 아이디어는 문제에서 나온 "폭탄의 폭발 범위가 밖을 넘어가지 않게 한다"라는 조건에서 비롯된 "모서리에 영향을 미치는 칸은 반드시 하나"라는 점이다. 만약에 그렇다면 모서리가 영향을 끼치는 만큼 ( M/2, M/2 )만큼 떨어진 칸에 그만큼의 폭탄이 존재할 것이다. 모서리를 처리하면, 모서리에 인접한 다른 테두리에 영향을 미치는 칸도 하나로 확정되므로 이를 바탕으로 차례대로 폭탄을 처리하면 된다는 것이다. i,j칸의 관점에서 영향을 줄 수 있었던 칸을 모두 처리한다면 칸 i,j에 영향을 미치는 칸은 (i + m/2, j + m/2) 뿐일 것이다. 하지만 이에 ..
ML Agent의 강화학습을 활용한 Unity AI학습
1. 강화학습의 기본 흐름 환경을 관찰하고, 그 환경을 바탕으로 결정을 하고, 그 결정을 바탕으로 행동을 한다. 취해진 행동으로 인해 변경된 상태는 보상과 새로운 환경을 갖는다. 이 새로운 환경을 관찰하는 것으로 다시 돌아와 이 과정을 반복하게 되는데 결과적으로 agent는 reward를 극대화 하는 방향으로 action을 취하도록 학습하게 될 것이다. 이 각 단계들을 어떻게 구현할까? 우선 이 모든것을 하는 주체인 Agent를 정의해주어야 한다. 2. Agent 정의 Unity.MLAgetns를 import한다음, 여기에 포함된 커스텀 Agent class를 정의해야한다. 여기서 Agent란 행동을 하는 객체이다 Agent라고 class를 정의하고 visual studio의 see definition을..
2020 카카오 인턴십 for Tech developers 코딩테스트 3번
문제 programmers.co.kr/learn/courses/30/lessons/67258# 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 문제 분석 접근법은 어렵지 않았던것 같다. 배열의 길이가 100,000 = 10^5이므로, n^2는 안되고 nlogn정도로 불어야 하기 때문에, 모든 인덱스를 기준으로 한칸씩 움직이며 모든 보석이 확인될 때 까지 순회를 하면 안된다. 대충 n^2이니까 그렇다면 배열을 한번만 돌아야 한다는게 키 포인트인데, 이를 위해서 현재 insert하는 인덱스와 pop하는 인덱스를 저장하고, 그 사이에 모든 원소가 들어간다면 out..
2020 카카오 인턴십 for Tech developers 코딩테스트 2번
문제 programmers.co.kr/learn/courses/30/lessons/67257 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr 문제 분석 개념은 어렵지 않았으나 1번과 같이 구현이 까다로웠던 문제였던것 같다. 잘못된 연산방식이 나오지 않고, 하나의 연산자는 두개의 수를 연산하는 작업을 하는 것이 조건으로써 주어졌으므로, 나는 수와 연산자 string을 하나하나씩 분리해서 vector에 집어넣고, 하나씩 꺼내면서 우선순위에 맞게 연산하였다. 3개의 연산자에 대해, 순열이므로 3! = 6이고, 전..