짱아의 개발 기록장

그리디+투포인터를 사용한 문제였다. 문제를 처음봤을 때 정확히 풀이가 떠오르지는 않았지만, 어차피 2명이 최대이고 limit이 주어져서 i, j 인덱스로 해결할 수 있을 것이라 생각했다. [메인 로직] 중요한 점은, i, j모두 전역변수로 선언해주어야 한다는 것!!!! people배열을 정렬하고 j는 맨뒤부터, i는 맨 앞부터 탐색하도록 했다. 그리고 i, j의 합이 limit이하면 두명이서 보트를 탈 수 있기 때문에 i++, answer++했고 limit을 초과하면 그냥 answer++하고 넘어간다. 이후, i==j인 경우는 answer++을 한 번 더 해준다. 첫 번째 풀이 for문을 사용해서 푸는 방법 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ..

그렇게 난이도가 높지는 않은 문자열 처리 문제였다. 2개씩 단위로 나누어서 다중집합(중복이 가능한)을 만들고 다중 집합들의 합집합과 교집합을 구하는 문제! 합집합, 교집합을 구하는 방법에는 여러가지가 있겠지만, c++ STL을 사용해서 풀었다. set_union => 합집합 set_intersection => 교집합 그리고! set_union, set_intersection을 사용할 때 중요한 점!!!!! 반드시 각각의 집합이 정렬되어있는 상태여야한다. 그래서 이전에 s1, s2를 sort를 해주었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 ..

배열 arr가 주어졌을 때, 배열에서 가장 작은 숫자를 제거한 배열을 리턴하는 문제였다. 예를 들어, [4, -1, 2, 3]이 주어지면 -1을 제외하고 [4, 2, 3] 을 반환하면 된다. 단, [10] 과 같이 원소가 하나만 있는 배열이 주어져서 제거한 후 원소가 아무것도 없으면, 배열에 -1을 넣어서 반환해준다. 12345678910111213141516171819202122232425262728293031#include #include #include #include using namespace std; vector solution(vector arr) { vector answer; int num = INT_MAX; int idx = 0; for(int i=0; i

40분 시간을 주고 2문제를 푸는 실력 체크 level 1을 풀었다. 생각보다 쉬워서 20분? 정도만에 2문제 모두 풀 수 있었다. 첫 번째 문제는 문자열을 숫자로 변환해주는 문제였다. 예를 들어, -1234 => -1234로, +1234 => 1234로, 1234 => 1234로 변환해주면 된다. 맨 앞에 부호(-, +)가 있을 수도 없을 수도 있다는 가정하에 풀어야 한다. 1234567891011121314151617181920212223242526272829303132333435#include #include using namespace std; int solution(string s) { int answer = 0; bool isMinus = false; bool isPlus = false; if..

1) DP+BFS BFS와 DP를 모두 활용해서 푸는 문제였다. 약간 백준에서 욕심쟁이 판다?와 비슷한 느낌? 하지만 이 문제가 훨~~씬 쉽다. [메인 로직] 일단, dp[y][x] = dp[y-1][x] + dp[y][x-1]이라는 공식은 문제를 읽어보면 쉽게 세울 수 있다. 이것을 응용해서 특정 칸에서 다음 칸으로 이동하게 되면, 다음 칸의 dp값에 현재 칸의 dp값을 무조건 더해주었다. 지나가는 길이기 때문에 경로추가! (dp[ny][nx] += dp[y][x]) 또한!!! 이미 방문한 곳은 큐에 절대로 넣어주지 않았다... 왜냐하면 수가 배가 되기 때문에....dp값은 방문했던 곳이여도 지나가는 길에 도달한 것이기 때문에 항상 더해주었지만, 이미 방문한 점은 다시 큐에 넣어주면 안된다! 1 2 3..

도저히.. 풀이가 생각이 나지 않아 다른 블로그의 아이디어만 참고해서 가닥을 잡을 수 있었다. [메인 로직] 모든 경우의 수 중에서 가장 최악의 시간이 나올 경우를 찾는다. ex) [7, 10], n = 6이면 최악의 시간은 10분이 걸리는 심사관에게 6명 모두가 입국심사를 받는 경우가 될 것이다. 그러면 최악의 시간은 총 60분이다. Start = 1, End = 60으로 하고 이분탐색을 시작하면 된다. mid = (Start+End)/2로 잡고 mid의 시간일 때 총 검사할 수 있는 인원의 수를 구한다. 30/7+30/10 = 7은 n=6의 값보다 크기 때문에 End = mid-1로 이분탐색을 쭉 진행하면 된다. 단! 조심해야하는 부분은 n값과 같은 값이 나왔다고 해서 바로 break로 빠져나오면 오..

아주 기본적인 BFS문제이다. 방문하지 않은 컴퓨터에 방문해서 연결된 모든 컴퓨터들을 하나의 네트워크로 연결해주는 작업을 bfs로 해주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include #include #include using namespace std; int solution(int n, vector computers) { int answer = 0; int visited[201] = {0, }; for(int j=0; j

[메인로직] 현재 시간(sec)이하의 요청 시간을 가지고 있는 작업들을 모두 최소 힙에 넣고 => 힙에 pair 형태로 저장했다. 그 중 가장 작은 작업 시간을 가지는 작업을 수행한다. 위의 로직을 모든 작업이 끝날때까지 반복하면 된다! 하지만!!!!! [[0 , 3], [4, 4], [5, 3], [4, 1]] 이 테스트케이스에서 오류가 발생했다..... 작업을 수행하면서 현재 시간을 sec += (작업의 소요시간) 으로 더해주었는데,,,,,, 위 케이스에서는 첫 번째 작업 수행 후, sec = 3이 되면 3이하의 요청시간을 가지는 작업이 하~~~나도 없기 때문에 의미없이 while문을 계속돌아서 TimeLimit이 발생한다. 따라서, 위와 같이 priority_queue에 아무것도 없을 경우에는 현재..