알고리즘 문제풀이 반응형 썸네일형 리스트형 [Programmers] 프로그래머스 Lv.4 행렬과 연산 문제풀이(C++) - 2022 KAKAO TECH INTERNSHIP deque를 이용한 연산을 하는 것이 핵심이고, 내가 느낀 어려웠던 점은 1. 2*2 행렬에서 segmentation fault를 일으켰었는데, Rotate연산에서 mid값을 먼저 참조하지 않도록 해야 한다. 2. 7번 8번 테케에서 시간초과가 떴는데, mid를 deque로 설정해야 한다(복사연산으로 인한 시간초과 발생) 등이 있었다. 솔직히 문제 보면서 2시간 정도 고민했는데, 방법을 떠올리지 못했었다. 이후 풀이를 살짝 봤는데, deque라는 단어만 보고 다시 구현해보다가 위에 언급한 2개 문제 해결하면서 또 시간 어마어마하게 날려먹었다. Lv.4 앞으로 좀 많이 익숙해질 필요가 있겠다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 .. 더보기 [Programmers] 프로그래머스 Lv.3 등산코스 정하기 문제풀이(C++) - 2022 KAKAO TECH INTERNSHIP 다익스트라 알고리즘을 이용한 최단경로 변형 문제 -> 각 경로 가중치를 더하는 대신, intensity(경로 상 최대 가중치값)의 최솟값만 유지하면서 첫 산봉우리까지 도착하면 되는 문제였음 그리고, gates를 동시에 출발시켜도 된다는 의미를 이해하는데 오래걸렸는데, 이에 대한 설명이 필요할 듯 하다.(출입구 하나하나에서 일일히 다익스트라 쓰면 일부 테스트케이스에서 시간초과가 뜬다. -> 동시에 출발시켜야 함) gates를 동시에 출발시켜도 된다는 뜻은, 다익스트라를 시작하는 queue에 초기에 모든 gates를 다 때려넣어야 한다는 의미이다. 동시에 출발시키면 어떤 형태가 되는지 비교해서 알아보면, 하나의 정점을 넣고 다익스트라 -> max_dis[i] : 해당 정점에서 i번째 노드까지의 최소 inte.. 더보기 [Programmers] 프로그래머스 Lv.3 코딩 테스트 공부 문제풀이(C++) - 2022 KAKAO TECH INTERNSHIP 핵심 : DP 개념의 문제라는 느낌이 오는 것이 중요 -> 처음엔 반복문 생각했다가, 다음에 풀 문제를 반복문에서 실시간으로 적용할 수 없을 것이라 판단 -> 그러면 자연스레 흐름이 '재귀함수로 모든경우를 따져봐야하나?' 로 흘러갔고, -> 재귀하면 DP가 같이 떠오르고 시간초과도 해결 가능하겠다 싶어서 DP로 구체화하기로 함 DP 까지는 떠올렸으나, 이후 구체화방안 떠올리는 역량이 부족했음 dp[a][b] : 알고력 a, 코딩력 b 까지 도달하는데 걸리는 최소시간 -> 설정까지는 잘 했고 순차적으로 dp값을 채워나가는 과정이 어려웠음 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.. 더보기 [Programmers] 프로그래머스 Lv.2 n^2 배열 자르기 문제풀이(C++) - 월간 코드 챌린지 시즌3 수열의 규칙을 생각해내야 했던 문제 - 내 느낌상 Lv.3 였음ㅠ 처음에 그대로 구현하려다가 n 제한이 10^7인 것과 left, right가 long long으로 선언된거 보고 배열 구현은 절대 아니겠다는 생각이 들었고, 이후 떠오른게 규칙성임 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 #include #include using namespace std; /* n*n 2차원배열 i=1~n 반복 - O(n) (1, 1) ~ (i, i) 모든 '빈칸'을 i로 채움 - O(i^2) 1~n행 잘라내서 모두 이.. 더보기 [Programmers] 프로그래머스 Lv.3 부대복귀 문제풀이(C++) BFS 문제였지만, 최단거리에 꽂혀서 바로 다익스트라/벨만포드/플로이드워셜 3대장 떠올린게 최대실수ㅠ 처음에 벨만포드로 풀어보니 시간초과 나왔, 다시보니 목적지에서부터 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 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 #include #includ.. 더보기 [Programmers] 프로그래머스 Lv.2 혼자서 하는 틱택토 문제풀이(C++) 무난무난한 문제였음 / 경우를 잘 따져가면서 case를 나누는게 포인트 조금 코드가 더러운 느낌이 있지만, 문제를 푸는 당시엔 코드 깨끗이 정리하다가 시간 까먹을거 같아서 계속 진행시켰었음 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 using namespace std; /* 틱택토 게임정보를 담은 3*3 배열 주어질 때, 규칙을 지킨 상황인지 아닌지를 re.. 더보기 [Programmers] 프로그래머스 Lv.2 무인도 여행 문제풀이(C++) BFS를 통해 해결 - 바로 떠올랐지만, 구현하는데는 좀 걸렸음(struct 구조 정의, vector 인덱스 범위초과해결 등 때문에 오래걸림) 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 96 97 98 99 100 101 102 103 104 105 106 #i.. 더보기 [Programmers] 프로그래머스 Lv.3 연속 펄 부분 수열의 합 문제풀이(C++) 누적합 및 DP 개념 이용한 문제 / Lv.3정도까지의 난이도는 아닌거 같았음 처음에 시행착오 겪고 비교적으로 바로 해답이 떠올랐음 근데 dp[500001] 변수를 int로 선언해서 TC 3갠가 틀리면서 시간 엄청 까먹음....ㅠㅜ 변수선언 할 때 생각했나요? 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 #include #include using namespace std; /* 수열 sequence가 주어짐 이 열의 부분수열을 추출해서 거기 펄스수열 각 원소 곱했을 때.. 더보기 이전 1 2 3 4 5 6 7 ··· 9 다음
