짱아의 개발 기록장

Greedy?라고 하기에는 적당한 구현문제라고 생각된다. 키포인트는! lost한 학생이 reverse에도 속해있을 수 있기 때문에 그 부분을 잘 처리해주면 문제없다. 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 #include #include #include using namespace std; bool check[31]; bool check2[31]; int solution(int n, vector lost, vector reserve) { int answer = n; for(int i=0; i

문자열 처리 그 자체인 문제..!! 일단, 이렇게 시분초밀리초로 나누어져 있는 문제는 무조건! 밀리초 기준으로 변환해주고 작업하는 것이 편하다는 것을 알고있어야 한다. 그래서 문자열 파싱을 한 후에 밀리초 단위로 모두 변환해서 요청 시작 시간과 끝시간을 구해주었다. 중요한 점은! 초당 최대 처리량은 요청의 응답 완료 여부에 관계없이 임의 시간부터 1초(=1,000밀리초)간 처리하는 요청의 최대 개수를 의미한다. 라고 문제에 나와있기 때문에 시작 시간과 끝시간 안에서만 요청이 유효한 것이 아니라 시작시간-999 ~ 끝시간 까지가 유효한 범위라는 것을 캐치하는 것이 중요하다. 왜냐하면, 말 그대로 1000밀리초 간에 처리하는 요청의 최대 개수를 구하는 것이기 때문에 어느 부분이던간에 1000밀리초의 범위에 ..

그냥 완탐으로 하기에는,,, 시간제약도 있을 것 같고 애초에 Greedy를 연습하려고 선택한 문제이기에 Greedy로 풀기 위해 노력했다. 하지만,,,아이디어가 도저히 떠오르지 않아 아이디어만 다른 블로그를 참고했다. 핵심 아이디어 #1924를 예로 들어보겠습니다. 1. k값이 2이므로 4-2 = 2글자가 출력됩니다. 2. 그렇다면 앞에서 (0, 1, 2)2까지 검사를해서 큰 수를 찾으면 됩니다. 1924에서 앞에서 2까지인 부분은 192 입니다. 이중에서 가장 큰 숫자는 9가 됩니다. 3. 9를 사용했으므로 검사는 9의 뒤부터 탐색하게됩니다. 한 번 뽑았으므로 뒤에 검사하는 부분을 하나 증가시킵니다. 24가 남게되고 이중에서 가장 큰 숫자는 4입니다. 4. 따라서 정답은 94가 됩니다. 이런식으로 범위..

[메인 로직] words벡터에 있는 단어들과 비교대상이 되는 단어를 비교하여 한 개의 알파벳만 차이가 나는 지 확인한다. => check함수 그리고 이미 방문했던 단어들은 제외시킨다. => visited배열 이렇게 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 #include #include #include #include using namespace std; int visited[51] = {0, }; int an..

처음에는 어떻게 풀어야할지 도통 감이 오지 않아서,,, 결국 질문하기 탭에서 힌트를 얻었다. 플로이드 와샬을 통해 풀수 있었다. 일반적으로 플로이드 와샬은 최단 경로를 구하기 위해 사용하지만 이 문제에서는 단지, 이기는지 지는지의 관계에 초점을 맞추어서 플로이드 와샬을 적용시켰다. 만약, dp[a][b]=1이라면 a가 b를 이기는 관계이고 dp[a][b] = -1이라면 a가 b에게 지는 관계이다. 그리고 문제에 따라, a가 b를 이기고 b가 c를 이긴다면? a가 c를 이기는 것이 성립한다는 것을 알 수 있다. 위의 논리대로 플로이드와샬을 활용해 로직을 구현하면 된다. 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..

[핵심 요소] 계속 테케, 4번이 틀려서 봤더니.... 왠걸 같은 항공편이 2번 있어도 괜찮기 때문에 from->to로 가는 항공편을 한 번 갔다고 해서 못가게 하면 안되는 것이었다.....즉, ["ICN", "A"], ["ICN", "A] 똑같은 항공편이 2개 있을 수도 있다는 것! 그래서 visited[][] 2차 배열을 사용해서 visited[from][to]의 항공편 개수를 저장해주었고 방문할때마다 -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 43 44 45 46 47 48 49 50 51 52 53 54 55 56 ..

유니온파인드를 사용하는 대표적 문제이다. 문제는....cin, cout이 진짜 느리다는 것을 실감한 문제^^ cin, cout을 쓰니까 맞왜틀이어서 질문 검색란을 찾아보니 똑같은 문제에 시달리시는 분들이 계셔서 ㅋㅋㅋ ios::sync_with_stdio(0); cin.tie(0); 써서 해결했다. 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 // 집합의 표현(1717번) #include #include using namespace std; int n, m, a, b, c; int connect[1000002] = {0, }; in..

잘못된 테케를 넣는 바람에 괜히 시간을 날렸던 문제....^^ 그냥 원래 짰던 코드가 맞았던 건데 테케를 잘못 넣어서 괜히 시간 낭비를 해버렸다....으이ㅏ아아아 [메인 로직] 디딤돌에 적혀있는 숫자들 중 가장 작은 수와 큰 수를 기준값으로 정하고 이분탐색을 시작했다. mid값을 각 디딤돌에 적힌 수에서 빼고 돌다리를 건널 수 있는 지 여부를 판단했다. 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 #include #include #include using namespace std; int solution(vector stones, ..