본문 바로가기

(●'◡'●) Categories 🐅387

프로그래머스 (단어 변환, 깊이/너비 우선 탐색(DFS/BFS)) C++ DFS가 아니라 BFS 인것 같긴한데 일단 함수명은 이렇게 dfs로 해버렸다. 아닌가... 아직 개념이 확실히 잡히진 않은듯.. 아무튼 DFS와 BFS를 할 때 파라미터로 하나씩 바뀌어서 넘겨지게 되는 것에 Focus를 맞춘다. 그리고 visited가 가장 중요!! 그리고 이 문제의 경우 방문하지 않은 경우의 node를 queue에 모두 넣고 살피는 것이 아니기 때문에 dfs 재귀를 탈출하게 되면 이중 for문 중 nested된 for문에서 visited 한 노드의 visited를 0으로 만들어야 한다는 것이 포인트 #include #include #include using namespace std; int answer = 100; string value; vector visited(50,0); void.. 2021. 12. 30.
프로그래머스 (네트워크, 깊이/너비 우선 탐색(DFS/BFS)) C++ 초반에 문제 Setting 할 때 시간이 많이 걸렸고 묶인 것이 몇 개인지 파악하는 것에서도 많이 시간을 썼다. 하다보니까 visited 하지 않은 것을 시작할 때가 네트워크가 달라지는 순간이었다. #include #include #include #include using namespace std; int solution(int n, vector computers) { int answer = 0; vector adj(n+1); vector visited(n+1, 0); queue queue; // Diagonal Matrix 이므로 Upper에 해당하는 것만 취해서 adjacent list 만들기 for(int i = 0 ; i < n ; i++) { for(int j = i+1 ; j < n ; j++.. 2021. 12. 30.
프로그래머스 (가장 먼 노드, 그래프) C++ 그래프와 DFS의 느낌이 풍긴다면 이중 벡터를 이용해서 Adjacent List를 만들고 visited 벡터를 이용해서 BFS를 iterative하게 구성한다. 그리고 BFS의 경우 시작 노드와 얼마나 떨어져 있는지는 새로운 배열을 하나 만들어줘서 알고리즘을 작성하면 된다. while 문 안의 for 문의 경우 하나의 node를 설정해놓고 그 주변 연결된 node만을 탐색하는 것이기에 queue에서 front로 참조한 node는 변하지 않는다는 성질을 이용하여 level을 체크해주면 된다. #include #include #include #include #include using namespace std; int solution(int n, vector edge) { int answer = 0; vect.. 2021. 12. 29.
프로그래머스 (타겟 넘버, 깊이/너비 우선 탐색(DFS/BFS)) C++ 약간 음.... 이런 분위기의 문제가 있다. 딱 하나 정도 차이나는 +와 - / 인접한 주변의 것들을 비교하고 등등 이게 바로 dfs 재귀함수를 하라는 것이다. 카카오 컬러링북 문제랑 비슷하다. 느낌을 유지하자. #include #include using namespace std; int answer = 0; void recur(vector numbers, int target, int sum, int count) { // count도 계속적으로 새서 count가 numbers 배열의 크기와 같아진 경우에 // sum 또한 원하는 합 target과 동일하다면 answer를 증가시키고 return;으로 돌아간다. if(count == numbers.size()) { if(sum == target) answe.. 2021. 12. 29.
프로그래머스 (없는 숫자 더하기, 월간 코드 챌린지 시즌3) C++ 그냥 무난한 코딩. 전체 덧셈에서 해당하는 숫자를 빼는 것도 하나의 방법이라고 한다. #include #include #include using namespace std; int solution(vector numbers) { int answer = 0; vector arr(10); // arr 라는 벡터를 만들어 주어진 번호에 해당하는 index의 값을 증가시킨다. for(int i =0 ; i < numbers.size() ; i++) { arr[numbers[i]]++; } // 다시 arr 벡터를 돌리면서 0인 값을 answer에 누적시킨다. for(int i =0 ; i < 10 ; i++) { if(arr[i] == 0) answer += i; } return answer; } 2021. 12. 29.
프로그래머스 (크레인 인형뽑기 게임, 2019 카카오 개발자 겨울 인턴십) C++ 처음 이 문제를 접근할 때 [row][column]이 있을 때 column부터 접근을 해야한다는 고정관념 때문에 새로운 2차원 벡터를 만들어서 해결을 했다. 코드를 보는 사람도 이해하기 힘든 그런 풀이법으로 진행했었다. 분명한 것은 Stack의 개념을 사용하며 알고리즘을 천천히 만든다면 금방 짤 수 있는 코드이다. #include #include #include #include using namespace std; int solution(vector board, vector moves) { int answer = 0; stack s; // 움직인 횟수만큼 for문을 반복시킨다. for(int i = 0 ; i < moves.size() ; i++) { // index라는 변수에 움직인 칸의 번호를 저장시.. 2021. 12. 29.
프로그래머스 (키패드 누르기, 2020 카카오 인턴십) C++ 가로로 인접한 키패드는 1만큼 차이가 나고 세로로 인접한 키패드는 3만큼 차이가 나는 이 경우를 어떻게 해결해야 할지 몰라서 고민을 너무 많이 했다. 사실 구글에서 어떤 사람도 고민해서 해결한 결과를 보고 충격에 빠진.... 3으로 나눈 몫과 3으로 나눈 나머지를 더하면 그 차이가 없어진다는 것이 새롭게 바라볼 수 있는 시야를 넓혔다. #include #include #include using namespace std; string solution(vector numbers, string hand) { string answer = ""; int left_count = 10; int right_count = 12; for(int i = 0 ; i < numbers.size() ; i++) { if(numb.. 2021. 12. 29.
프로그래머스 (숫자 문자열과 영단어, 2021 카카오 채용연계형 인턴십) C++ 입력 받은 영어와 숫자가 조합된 문자열에서 하나하나 비교를 통해 case를 만들었다. 영어 문자열이 나오는 경우 정해진 단어의 길이를 생각해서 one 부터 nine까지를 분류했다. #include #include #include using namespace std; int solution(string s) { int answer = 0; string arr = ""; for(int i = 0 ; i = '0' && s[i] 2021. 12. 29.
프로그래머스 (오픈채팅방, 2019 KAKAO BLIND RECRUITMENT) C++ 공백이 포함된 문자열인 stringstream을 사용하는 법을 처음 배웠다. 일일이 if문을 통해서 substr로 비교를 했고 이를 통해 Test Case를 통과한 방법은 구현을 했으나 Time Problem으로 실패했었다. Stringstream을 통해서 간편히 원하는 단어를 뽑아내고 If 문을 활용해서 원하는 논리로 구현시킬 수 있었다. Map 의 경우도 insert(make_pair)의 방법을 사용하고 find("찾고자 하는 문자열")->second 이렇게 선언해서 할당을 했었다. 이제는 원하는 문자열을 index화 시켜서 할당을 해도 될 것 같다. 사실 이 알고리즘은 구글에 존재하는 방법 중 하나이다. 그래도 배운건 배운 거니... #include #include #include #include .. 2021. 12. 29.
프로그래머스 (문자열 압축, 2020 KAKAO BLIND RECRUITMENT) C++ 문자열을 가지고 장난을 치는 문제라고 생각이 들었다. substr을 자유자재로 사용할 수 있는지, erase를 사용할 때의 index 문제점을 잘 파악하고 있는지를 물어보는 문제 같았다. 사실 원하는 결과값은 반복되는 문자열의 개수와 문자열의 크기이므로 이를 각각 구해서 더하는 방식으로 접근해도 된다. 복잡한 알고리즘을 요구하지는 않지만 조건을 잘 세워서 정답을 구할 수 있는 논리를 가지고 있는지를 파악하는 문제였다. #include #include #include using namespace std; int solution(string s) { int answer = 0; int total = 0; int count = 1; int min = 99999; string restore = s; string.. 2021. 12. 29.

티스토리툴바