나 요리학원 출신임

그리디로 풀 수있는 문제다 내가 움직일 수 있는 거리는 (손님 방문시간 - 현재시간)만큼이다 그럼 우린 시간순으로 정렬을하고 내가 움직일 수 있는 범위를 가지고 다니면서 만약 그 범위안에 손님이 만족하는 온도가 없다면 NO 가능하다면 YES를 출력해 줄 수 있따! 그리고 만족한다면 시간을 바꿔주고 왼쪽 오른쪽 범위는 각각 포함할 수 있는 최대, 최소의 거리로 해줘야한다 처음에는 만족하는 범위를 찾으려고 하다가 거꾸로 해야 쉽겠다 싶어서 주석처리하고 반대의 경우를 찾았다! 앞으로도 쉬운것좀 생각하자.. 어려운 방법말고..!! 소스코드 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 3..

주어지는 문자열들을 통해 만들수 있는 가장 긴 팰린드롬의 길이와 팰린드롬을 출력한다! 나는 map과 set을 이용해서 풀었다 먼저 set에 담는데 뒤집어서 같은 문자열이 있다며 팰린드롬의 짝이 된다 그래서 만약 뒤집어서 있다면 뒤집은 문자열의 카운트만 증가시켜주고 없다면 set에 넣어준다 그리고 set을 돌아보면서 각 문자열의 /2만큼은 기본적으로 붙일 수 있으므로 답에 추가하자! 그리고 만약 개수가 1인것중에 팰린드롬인것이 있다면 그것을 답의 중간에 붙여주자! 소스코드 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 42 #include using ..

이분탐색을 통해 값을 찾으려고했는데 계속 실패했다! 한번 생각해보자.. 이 문제에서는 인접한 수의 차를 최소로 하고싶고 그때의 k를 구하고싶다 그럴때는..! -1과 인접한 숫자들 중 최소와 최대의 평군이 최적이된다 문제를 풀면서는 생각못했는데 -1 옆에없는 수는 무시하는게 맞다 -1 옆에 있을때만 의미가 있으니까 근처에 있는 수를 찾아서 평균값을 구하고 대체해준다 그리고 n만큼 보면서 가장 큰 diff값을 찾으면 된다! ㅠㅠ 소스코드 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 #include using namespace std; #define ll long long const int SIZE = 1e5+5; int..

dfs를 이용한 cycle 체크 문제 응용 만약 cycle이 있다면 NO이다 하지만 몇가지 조건이 더 있다 먼저 각 정점마다 최대 2개의 간선을 가지므로 indgree가 2보다 크면 fail 또한 cycle을 확인할 때 set을 통해 이미 본 간선은 지워준다고 생각하고 푼다 출력하는건 indgree가 낮은곳부터 쭉 dfs를 통해 출력하고 남은걸 출력하면 된다 소스코드 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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67..

이분탐색으로 해결할 수 있는 문제다 mid일만큼 본다고 하면 mid/(g+b)만큼 g or b를 볼 수 있다 그럼 g*(mid/(g+b))만큼 좋은 날을 볼 수 있고 그 다음 볼수있는 날도 최대 g만큼 좋은날이다 결국 답은 g*(mid/(g+b))+min(mid/(g+b),g)로 나온다!! 근데 문제를 잘 보면 전체 도로를 어쨌든 공사는 해야하므로 최소 n일은 봐야한다 소스코드 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 #include #include using namespace std; #define ll long long ll n, g, b; bool solve(ll mid) {..

문제를 요약하자면예를 들어 배열 [1,5,4,1,3]이 있을 때 우리는 a가 먼저 나오고 b가 나중에 나오는 순서쌍 (a,b)에 수를 찾으면 된다무슨 말이냐면 순서쌍 (1,3)은 1이 앞에 3이 뒤에 이므로 가능하다근데 (3,1) 같은 경우는 3보다 1이 앞에 있으므로 교차하게 되어 불가능하다즉 맨 앞과 맨 뒤에서 출발했을 때 교차하지 않는 순서쌍의 수를 찾으면 된다!+ 중복불가 문제는 set과 map을 사용해 풀었다map에는 각 숫자의 수를 저장했고 set은 내가 갈 수 있는 수를 의미한다그럼 맨 앞부터 수를 보면서 set의 size만큼을 더해주면 된다이 때 내가 볼 때마다 map에서 수를 1씩 줄여준다 그리고 0이 되면 set에서 사라지게 해준다추가로 used배열을 사용했는데 used는 이미 본 숫자..

정점과 간선이 n,m(

3개의 증가수열을 고르고 그 때의 비용이 최소를 찾는 문제다N^2 DP로 풀었다 d[pos][cnt]로 테이블을 잡고 pos까지 봤고 cnt개 더 고를 수있을 때로 문제를 풀었다 문제 풀고 틀려서 보니 메모이제이션을 안했다 ㅎㅎ소스 잘 봐야겠따..! 소스코드1234567891011121314151617181920212223242526272829303132333435363738394041424344#include #include #include #include #include #include #include #include #include #include #define ll long long#define inf 1e17using namespace std;ll arr[3030], cost[3030];int ..

하하하 알고리즘 하나도 기억이 안나서 오늘부터 글을 쓰면서 강제로 기억해야겠다. 쉬운것부터 차근차근 다시 해야지..! 이 문제는 Cycle을 찾는 문제이다. 조건은 처음시작한 정점으로 마지막에 다시 돌아오는 것인데 중간에 다른 정점으로 빠지는 간선이 존재하면 안된다..! 이 사진중에 (15, 5, 11, 9) / (7, 10, 16) 만이 조건을 만족하는 Cycle이다! 처음에 dfs를 돌리고 (정점*2 == 간선) 했다가 18번째 테케에서 틀렸다 ㅎ 솔루션은 1. 각 정점의 degree를 구한다 2. dfs를 돌리며 방문한점을 벡터에 넣어준다. 3. dfs가 끝난 후 벡터에 들어있는 정점들이 모두 2의 degree를 갖는다면 문제에서 원하는 cycle이다! 이렇게 찾아주면 된다! 소스코드12345678..