Algorithm197 그래프 그래프 문제의 여러가지 상황들을 그래프로 그린 다음 그래프 알고리즘을 적용 그래프의 표현 그래프 저장 방법 1. 인접 행렬 공간 복잡도: O(V^2) 2. 인접 리스트 공간 복잡도: O(E) - 리스트는 크기를 동적으로 변경할 수 있어야 한다. - 링크드 리스트나 길이를 동적으로 변경할 수 있는 배열을 사용한다 그래프의 탐색 목적: 임의의 정점에서 시작해서 연결되어 있는 모든 정점을 1번씩 방문하는 것 DFS: 깊이 우선 탐색 --> 스택 이용 BFS: 너비 우선 탐색 -->큐 이용 DFS(깊이 우선 탐색) 스택을 이용해서 갈 수 있는 만큼 최대한 많이 가고, 갈 수 없으면 이전 정점으로 돌아간다 재귀 호출을 통해서 구현할 수 있다 * 인접 행렬을 이용한 구현 void dfs(int x) { check[.. 2022. 6. 3. [프로그래머스 lv1] 문자열 내 마음대로 정렬하기 코딩테스트 연습 - 문자열 내 마음대로 정렬하기 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 문자열 내 마음대로 정렬하기 문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다. 예를 들어 strings가 ["sun", "bed", "car"]이고 n이 1이면 각 단어의 인덱 programmers.co.kr 어려웠던 점 대상이 되는 문자를 뽑고 그 문자의 인덱스 혹은 전체 글자도 같이 저장해야하지 않나? 라는 생각에 multimap을 이용해서 풀어야겠다 라고 생각했고 그렇게 iterator까지 하다가 잘 안되서 풀이 봄 찾아보니 sort와 cmp를 연습하는 문제라고 함.. compare() 함수를 만.. 2022. 5. 27. [프로그래머스 lv1] 같은 숫자는 싫어 코딩테스트 연습 - 같은 숫자는 싫어 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 같은 숫자는 싫어 배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 programmers.co.kr 중복 제거 함수 C++ unique reference vector s; s.erase(unique(s.begin(),s.end()),s.end()); 2022. 5. 27. [프로그래머스 lv1] 문자열 내 p와 y의 개수 코딩테스트 연습 - 문자열 내 p와 y의 개수 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 문자열 내 p와 y의 개수 대문자와 소문자가 섞여있는 문자열 s가 주어집니다. s에 'p'의 개수와 'y'의 개수를 비교해 같으면 True, 다르면 False를 return 하는 solution를 완성하세요. 'p', 'y' 모두 하나도 없는 경우는 항상 True를 programmers.co.kr 문제점 문자열 중 하나가 p인지 비교 할 때 if(s[i]=="p") 이렇게 큰따옴표로 비교하니까 에러가 뜨고 if(s[i]=='p') 작은 따옴표로 바꾸니까 통과됨 문자열 하나하나에 접근할 때는 character임 그래서 작은 따옴표가 맞음 2022. 5. 19. [프로그래머스 lv1] 서울에서 김서방 찾기 코딩테스트 연습 - 서울에서 김서방 찾기 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 서울에서 김서방 찾기 String형 배열 seoul의 element중 "Kim"의 위치 x를 찾아, "김서방은 x에 있다"는 String을 반환하는 함수, solution을 완성하세요. seoul에 "Kim"은 오직 한 번만 나타나며 잘못된 값이 입력되는 경우는 없습니 programmers.co.kr 문제점 string에 int 넣는법 모름 해결 검색해서 찾음 to_string(number); #include #include using namespace std; string solution(vector seoul) { string answer = ""; int index=0; for(int i.. 2022. 5. 18. [프로그래머스 lv1] 소수 찾기 코딩테스트 연습 - 소수 찾기 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 소수 찾기 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.) 제한 조건 n은 2이상 programmers.co.kr 문제점 소수 찾는 법 잊음 자세히 모름 해결 에라토스테네스의 체 #include #include using namespace std; int solution(int n) { int answer = 0; vector v(n+1,true); for(int i=2;i 2022. 5. 18. 이전 1 ··· 20 21 22 23 24 25 26 ··· 33 다음
