짱아의 개발 기록장

처음에는 Brute Force로 할까? 했지만... 문제를 읽어보니 전형적인 투포인터 문제라는 것을 알 수 있었다. [메인 로직] 만약 처음나온 문자가 나온다면, num++을 해주고 map에 해당 문자를 추가해주었고 End++해주었다. 하지만 이미 나왔던 문자가 나온다면 num--해주고 map에서 해당 문자를 제거한 후 Start++해주었다. Two Pointer 방식 시간복잡도 : O(n) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 // 투포인터 class Solution { public: int lengthOfLongestSubstring(string s) { int ans = 0; int Start=0, End = 0; map m; i..

위 문제는 다양한 방식으로 풀이가 가능하다. nums의 최대크기가 1000이기 때문에 브루트포스도 가능하지만 시간복잡도를 생각하면 O(n)방식으로 푸는 것이 가장 현명해보인다. 1. Brute Force방식 시간복잡도 : O(n^2) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public: vector twoSum(vector& nums, int target) { vector ans; bool check = false; for(int i=0; i

전체 치킨집을 vector에 넣고 "조합"을 사용하여 m만큼의 치킨집을 선택하여 도시의 치킨거리를 구하는 방식으로 구현했다. 자세한 부분은 코드를 보면 알 수 있다. 코드 첨부 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 68 69 70 71 // 치킨 배달 #include #include #include using namespace std; int n, m; int city[51][51] = {0, }; ve..

행과 열을 기준으로 각각 구현하면 된다. 행을 기준으로 설명을 해보겠다. 1) 열마다 탐색하며 높이의 차이가 1만큼 나는 곳에 L길이의 경사로를 설치할 수 있는지 확인한다. 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..

n의 크기가 크지 않아서 n^2으로 푸신 분들도 계시겠지만 글쓴이는 nlogn LIS 알고리즘을 사용하여 풀었습니다. 특히, 이 문제는 요소들을 구해야 하기 때문에 LIS 요소 역추적하는 부분도 구현했습니다. 블로그에 LIS 요소 역추적하는 방법에 대해서도 포스팅 했으니 참고바랍니다. jungahshin.tistory.com/7 [Algorithm] LIS 요소 역추적하기(backtracing) 실제 LIS 알고리즘을 통해 생성된 백터는 실제 LIS를 나타내지 않습니다. 그렇기 때문에 LIS를 이루는 원소들을 알아내기 위해서는 추가 과정이 필요합니다. 아래 문제가 LIS 요소 역추적을 연습하� jungahshin.tistory.com 코드 첨부 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ..

여러가지 풀이 방법이 있겠지만, 글쓴이는 조합을 활용해서 문제를 풀었다. 벡터에 사용되는 연산자의 개수만큼 해당 연산자의 idx값을 넣어주었다. ex) 1 1 0 1 -> [0, 1, 3] / 2 0 0 2 -> [0, 0, 3, 3] 그리고 조합(next_permuation사용)을 통해 계산을 하고 최소, 최대값을 갱신해주었다. 코드 첨부 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 #incl..

문제에서 구현하라는 순서대로 쭉 구현하면 되는 간단한 구현문제였다. 구현을 하다가 조건에 맞는 부분, 맞지 않는 부분이 나오면 끊고 다시 돌아가는 부분만 잘 확인하면 된다. 코드 첨부 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 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 // 로봇 청소기 #include ..

내가 생각한 구현 순서는 다음과 같다. 1) 빨간 공과 파란공을 한 방향으로 빈칸이나 탈출구를 만나면 쭉 밀어준다. 2) 그 후, 상태를 비교해본다. 3) 만약, 파란공이 탈출구로 빠진다면 바로 다른 방향으로 넘어간다. 4) 파란공과 빨간공이 같은 자리에 도착한다면? 빨간공이 움직인 거리와 파란공이 움직인 거리를 비교한 후 더 멀리 움직인 공이 더 안쪽?에 위치한다. 5) 빨간공이 탈출구를 만난다면 game over! 이렇게 순서대로 코드로 잘 구현해낸다면 성공이다^.^ 코드 첨부 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 ..