https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으 www.acmicpc.net d[i][j] = (1,1)에서 (i,j)까지 이동했을 때 얻을 수 있는 사탕의 개수의 최대값 d[i][j] = a[i][j]+max..
https://www.acmicpc.net/problem/9536 9536번: 여우는 어떻게 울지? 문제 고대 미스테리로 전해지는 여우의 울음소리를 밝혀내기 위해 한신이는 고성능 녹음기로 무장하고 숲으로 들어갔다. 하지만 숲에는 동물들이 가득해, 녹음된 음성에는 다른 동물들의 울음소리가 섞여 있다. 그러나 한신이는 철저한 준비를 해 왔기 때문에 다른 동물들이 어떤 울음소리를 내는지 정확히 알고 있다. 그러므로 그 소리를 모두 걸러내면 남은 잡음은 분명히 여우의 울음소리일 것이다. 입력 첫 번째 줄에는 테스트케이스의 개수 T가 입력된다. 각 테스트케이스는 www.acmicpc.net 123456789101112131415161718192021222324252627282930313233343536373839..
https://leetcode.com/problems/two-sum/ 일반적으로는 for문 2번 도는 O(N^2) 방법을 생각한다. 이때 해시를 이용해서 a+b=c이라고 할때 a를 해시에 넣기 전에 먼저 b(c-a)가 있는지 확인한다. 이 방법으로 O(N)으로 해결가능하다. 12345678910111213141516171819class Solution {public: vector twoSum(vector& nums, int target) { map hash; vector ret(2); int len=nums.size(); for(int i=0;isecond; return ret; } hash.insert({nums[i],i}); } }};Colored by Color Scriptercs