IT/Algorithm24 정렬 - 가장 큰 수 정렬 - 가장 큰 수 문제 출저 - 프로그래머스 programmers.co.kr/learn/courses/30/lessons/42746 Answer code 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 #include #include #include using namespace std; bool cmp(int a, int b){ string str1 = to_string(a) + to_string(b); string str2 = to_string(b) + to_string(a); return str1 > str2; } string solution(vector numbers) { string answer = ""; sort(numbe.. 2020. 11. 15. 정렬 - K번째 수 정렬 - K번째 수 문제 출저 - 프로그래머스 programmers.co.kr/learn/courses/30/lessons/42748 풀이 생각 1. 특정 범위를 잘라서 정렬하자 2. 정렬한 배열의 k번째 수 push My code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include #include #include using namespace std; vector slice(const vector& array, int a, int b){ return vector(array.begin()+a, array.begin()+b); } vector solution(vector array, vector commands) { vector answer;.. 2020. 11. 15. 우선순위 큐, 그리디 - 허프만 압축 허프만 압축 허프만 압축이란? 어떤 데이터를 전송할 때, 한 글자를 1byte(8bits)로 전송하게 되면 글자수 * 8 의 bits가 쓰인다. 허프만 압축은 빈도수가 높은 글자를 짧은 bits로, 빈도수가 적은 긴 bits로 인코딩하는 압축방법이다. 문제 encoder : ASCII 코드로 표현되어 있는 txt 파일을 입력받아 encoding하여 압축 파일 생성하기 decoder : encoder를 통해 encoding된 압축 파일을 입력받아 원본 ASCII 코드로 표현되어 있는 txt 생성하기 단, 문장이 길 때 ASCII 코드로 표현되어 있는 파일보다 크기가 작아져야 함 풀이생각 1. 각 ASCII Character의 빈도수를 세야 한다. => hash 를 사용하여 쌍을 만들자. => unorder.. 2020. 11. 12. 재귀 - 2진수 변환 재귀 - 2진수 변환 문제 출저 - 코드업 codeup.kr/problem.php?id=1920 풀이 생각 1. 2진수로 표현한다. => 결국 2로 나누는 연산과 관련 있을 것임 => 2로 나눈 나머지가 1이면 1, 0이면 0을 붙여나가주자 2. 출력값을 역순으로 해주어야 함 => 스택으로 구현 * 그런데 이 문제에서 for문 사용이 불가해 채점이 불가했음 => 스택말고 string으로 구현하고, 역순으로 만들어주고 출력해주자 my code (stack) 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 #include #include using namespace std; vector binar.. 2020. 9. 28. 완전 탐색 - 소수 찾기 보호되어 있는 글 입니다. 2020. 9. 3. DFS - 타겟 넘버 DFS - 타겟 넘버 문제 출저 - 프로그래머스 https://programmers.co.kr/learn/courses/30/lessons/43165 풀이 생각 1. 재귀로 첫번째부터 마지막까지의 합을 차근차근 넘겨주자. => sum ± numbers[index] 2. 덧셈과 뺄셈이 있어야함 => 덧셈 재귀 끝난 후 뺄셈 재귀 들어가기 3. 기저사례는? => 마지막 index + 1 일때. numbers.size()와 일치할 때. => 이 때 sum이 targer과 같으면 1 리턴, 다르면 0 리턴 my code 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 #include #include using namespace std; int.. 2020. 9. 1. 무식하게 풀기(완전 탐색) - 모의고사 무식하게 풀기(완전 탐색) - 모의고사 문제 출저 - 프로그래머스 https://programmers.co.kr/learn/courses/30/lessons/42840 풀이 생각 1. 누가 많이 맞았을까를 어떻게 알까? => 전부 채점해봐야함. 완전탐색으로 생각하자 2. 각 학생마다 정답 패턴의 크기 (1번=5, 2번=8, 3번=10) 가 다르다. => 각 학생 for문 돌때마다 크기 받아서 처리 3. 정답 주기를 돌려야함 => answers가 7개라면 1번 학생은 6번째에서 다시 0번째로 와야함 => %로 index 만들기 => j%stuSize 4. 최대값을 어떻게 뽑을까? => *max_element 으로 학생들 중 max 정답수 뽑기 => max와 같으면 answer에 넣기 (오름차순까지 해결됨).. 2020. 8. 31. 무식하게 풀기(완전 탐색) - 게임판 덮기 보호되어 있는 글 입니다. 2020. 8. 30. 무식하게 풀기(완전 탐색) - 소풍 무식하게 풀기(완전 탐색) - 소풍 문제 출저 - 알고스팟 https://algospot.com/judge/problem/read/PICNIC 풀이생각 1. 입력되는 n, m값이 작다. => 브루트포스(완전탐색)으로 풀자 2. index로 처리할 수 있는 bool 필요 (쌍 맺기 위해서) 3. 짝을 이미 맺었는지 학생마다 확인필요 => bool 배열 생성. 재귀로 돌려주기 => 매개변수로. 4. 중복을 제거해야 한다. => 오름차순으로 맺어주자. => 앞 번호 친구부터 검사해서 짝을 맺어주자. answer code (알고리즘 문제해결전략 p158~159) 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 .. 2020. 8. 30. 무식하게 풀기 (완전 탐색) 무식하게 풀기 (완전 탐색) 완전 탐색? 가능한 방법을 전부 만들어 보는 알고리즘 재귀 호출과 완전 탐색 문제를 들여다볼수록 각 조각들의 형태가 유사해지는 작업. 이런 작업을 구현할 때 유용하게 사용되는 개념이 바로 재귀 함수(recursive function), 혹은 재귀 호출(recursion)이라고 한다. 재귀 함수 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수를 가리킨다. 반복문 -> 재귀 바꿔보기 1부터 n까지의 합을 반환하는 for문과 재귀 함수 (알고리즘 문제해결전략1 p147) 1 2 3 4 5 6 7 8 9 10 11 12 int sum(int n) { int ret = 0; for (int i = 1; i 2020. 8. 30. 너비 우선 탐색과 최단 거리 너비 우선 탐색과 최단 거리 깊이 우선 탐색과 달리 너비 우선 탐색은 대개 그래프에서의 최단 경로 문제를 풀 때의 용도로 사용된다. 그래서 깊이 우선 탐색에서는 모든 정점을 검사하면서 탐색을 수행하는 작업을 하지만, 너비 우선 탐색에서는 시작점으로부터 다른 정점들까지의 거리만 구하면 된다. ●최단 경로 문제 두 정점을 연결하는 경로 중 가장 길이가 짧은 경로를 찾는 문제 경로의 길이 = 경로에 포함된 간선의 개수 너비 우선 탐색 스패닝 트리를 보면, 각 정점으로부터 트리의 루트인 시작점으로 가는 경로가 그래프에서의 최단 경로임을 볼 수 있다. 그래서 함수 두개가 필요하다. 1. 각 정점까지의 최단 거리와 너비 우선 탐색 스패닝 트리를 계산하는 함수 2. 너비 우선 탐색 스패닝 트리를 입력받아 실제 최단 .. 2020. 8. 30. 그래프 - (백준 1260, 2606, 2667) DFS와 BFS, 바이러스, 단지번호붙이기 그래프 - (백준 1260, 2606, 2667) DFS와 BFS, 바이러스, 단지번호붙이기 문제 출저 - 백준 https://www.acmicpc.net/problem/1260 my code 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 #include #include #include #include using namespace std; vector adj; vector visited; void df.. 2020. 8. 28. 그래프 (DFS, BFS) 그래프 (DFS, BFS) 그래프의 표현 방법 1. 인접 리스트 - vector adjacent; - vector adjacent; adjacent[i]는 정점 i와 인접한 정점들의 번호를 저장하는 연결리스트(혹은 동적배열)임 여기서 추가적 속성을 갖는 그래프를 표현하려면? → pair 사용 2. 인접 행렬 - vector adjacent; adjacent[i,j]는 정점 i에서 j로 가는 간선이 있는지를 나타내는 bool값 변수임 가중치 그래프를 인접 행렬로 표현하려면? → bool이 아닌, int나 float으로 두면 됨 → 두 정점 사이에 간선이 없는 경우에는 이 값을 -1 혹은 아주 큰 값으로 설정 그래프는 트리보다 구조가 훨씬 복잡할 수 있기 때문에 탐색 과정에서 얻어지는 정보가 아주 중요하다 .. 2020. 8. 28. 우선순위 큐와 힙 - 변화하는 중간 값 우선순위 큐와 힙 - 변화하는 중간 값 문제출저 - 알고스팟 https://algospot.com/judge/problem/read/RUNNINGMEDIAN answer code 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 #include #include #include using namespace std; int MOD = 20090711; int n; struct RNG { int seed, a, b; RNG(int .. 2020. 8. 24. 이진 검색 트리 이진 검색 트리 검색트리 자료들을 일정한 순서에 따라 정렬한 상태로 저장해둠 원소의 추가와 삭제 + 특정 원소의 존재 여부 확인 등 다양한 연산을 빠르게 수행할 수 있음 검색트리가 사용될 수 있는 곳 예시 - 이미 가입한 사용자들의 주민등록번호를 저장해두고, 특정 사용자가 이미 가입되었나 찾기 - 사용자의 ID를 사용자 정보로 대응시키는 사전 객체 만들기 - 모든 학생들의 시험 점수를 저장해놓고, 나보다 1등 위인 사람과 1등 아래인 사람 찾기 검색트리 중 가장 흔하게 사용되는 것이 바로 이진 검색 트리이다. 이진 검색 트리 각 노드가 왼쪽과 오른쪽, 최대 두 개의 자식 노드만을 가질 수 있는 트리 왼쪽에는 root보다 작은 값, 오른쪽에는 root보다 큰 값이 들어감 원하는 값을 찾아가는 과정은 배열에.. 2020. 8. 23. 이전 1 2 다음
