본문 바로가기

728x90

Coding Test 코딩테스트13

Do it 알고리즘 코딩테스트 하루코딩 7장 정수론 문제 #18 소수 구하기 M이상 N이하의 자연수 중 소수 모두 출력 최대 크기 1,000,000이므로 시간복잡도가 O(N^2)인 알고리즘은 사용 불가하다. 과정 1. 크기가 N+1인 배열 생성, 각 요소에 인덱스 대입 // 인덱스 순서 1부터 시작하여 신경 안 쓰게 하기 위하여 2. 1은 소수 X이므로 삭제, 2부터 N의 제곱근까지 탐색하여 값이 인덱스와 일치하면 그대로 두고 // 처음 선택한 수는 소수로 인정, 그 배수는 삭제 3. 남아 있는 수 모두 출력 // M이상 N이하 *N의 제곱근까지만 탐색하는 이유 N을 두 수의 곱 a*b로 표현하면 각 수인 a, b는 둘중 하나는 N의 제곱근보다 클 수 없다. 그러므로 N의 제곱근까지만 탐색하면 전체 범위의 소수 탐색 가능 for(int i = 2; i 2022. 11. 20.

Do it 알고리즘 코딩테스트 하루코딩 6장 그리디 문제 #16 32 동전의 개수의 최솟값 == 거스름돈을 가장 적은 개수의 지폐로 거슬러 주는 경우의 수 동전의 종류 개수N, 만들고자하는 가격K, 동전 수는 충분 가장 가격이 큰 금액의 동전부터 구성하면 된다. // 먼저 그리디로 풀어도 되는지 판단한 후 구현 그러나, 반례를 잘 따져봐야 한다. ex) 135 9 51111 5개 333 3개 배수라는 조건이 있으므로 괜찮다. // Ai-1의 배수 Ai 오름차순이므로 역순으로 접근해야 가장 가격이 큰 금액부터 접근 가능하다. 가장 가격이 큰 것 부터 순서대로 찾아서 K보다 작은 값 찾기 int count = 0; // 동전의 개수 초기화 for(int i = N-1; i>=0; i--) { 동전 수 += 목표금액 K/현재 동전의 가치 K = K % 현재 동전의 .. 2022. 11. 20.

Do it 알고리즘 코딩테스트 하루코딩 5장 탐색 문제 이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다. # 13 연결 요소의 개수 구하기 연결요소는 에지로 연결된 노드의 집합 ex) 1, 2, 5와 3, 4, 6 총 2개 DFS는 그래프 완전 탐색이므로, 한번의 DFS가 끝날 때 까지 탐색한 노드의 집합이 연결요소 1개이다. 즉 모든 노드를 탐색할 동안 DFS 횟수가 연결요소의 개수이다. 만약 그래프의 모든 노드가 연결 되어 있었다면 DFS 횟수는 1이다. 방향이 없는 그래프이므로 양방향 모두 인접 리스트로 표현 N=1,000이므로 O(n^2)인 알고리즘도 사용가능하다. if(방문하지 않은 노드가 존재한다면) { // 각 연결요소의 방문 여부 count++; DFS(i); } DFS(int i) { if(visited[.. 2022. 11. 20.

Do it 알고리즘 코딩테스트 하루코딩 4장 정렬 문제 이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다. # 11 15 수 정렬하기1 (백준 2750) 수의 최대 개수, 즉 데이터 N의 최대 개수가 1,000이므로 시간복잡도가 O(n^2) 인 알고리즘도 사용가능하다. 버블 정렬을 이용하여 정렬 0번째 루프에서 0과 1 비교하여 swap, 1과 2 비교하여 swap ... // 오름차순인 경우 앞이 더 크면 swap 정렬되지 않은 범위 -1 for 0 N-1 // 루프의 개수, 마지막엔 데이터 2개가 정렬되므로 N이 아니라 N-1번 루프 for 0 N-1-i // 정렬되지 않은 범위, -i는 루프의 횟수가 진행될수록 정렬되지 않은 범위가 1개씩 줄어드므로 # 12 17 내림차순으로 자릿수 정렬하기 (백준 1427) 수의 각.. 2022. 11. 20.

Do it 알고리즘 코딩테스트 하루코딩 3장 자료구조 문제 # 1 각 자리 숫자의 합 구하기 java 숫자의 개수 N N개의 숫자의 나열 5 54321 54321/10000 == 5 54321%10000 == 4321 4321/1000 == 4 4321%1000 == 321 이런 로직으로 풀면 복잡하다. 구현하기도 어려울 것이다. 그러나, 가장 핵심적인 것은 N이 100이므로 100자리 수를 int, long 형으로 받을 수 없다는 것이다. 자료형의 범위를 벗어나기 때문에 그러므로 String으로 받아야한다. 문자열 "54321"의 각 자리 수를 뽑아내려면 toCharArray() 메소드 호출하여 문자형 배열로 만들어야한다. 그러고나서 문자 숫자를 숫자로 변환하기위해 '1' -> 1 아스키코드를 이용한다. 문자'1'을 숫자1로 변환 '1' - 48 또는 '1' .. 2022. 11. 20.

Do it 알고리즘 코딩테스트 하루코딩 8장 그래프 이론 # 20 그래프 그래프는 노드와 엣지로 구성된 집합이다. 노드는 데이터를 표현하는 단위 에지는 노드로 연결 트리도 그래프의 일종 유니온 파인드 그래프의 싸이클이 생성되는지 판별 위상정렬 조건 싸이클X, 방향O 전후 관계가 있는 노드를 선형으로 정렬 ex) 수강신청 수1 -> 수2 게임 빌드오더 주의 결과가 유일하지 않다. 최단거리 알고리즘 다른 모든 노드로 가는 최단거리를 구하는 알고리즘 다익스트라 조건 시작점O, 음수간선X 벨만포드 조건 시작점O, 음수간선 ok 음수 싸이클이 있는지? 최단거리가 음의 무한대로 간다. ex) 시간 여행, 웜홀 플로이드 워셜 조건 시작점X 모든 노드 쌍의 최단거리 단점 시간복잡도 나쁘다. // 노드의 개수가 작을 때 또는 모든 노드쌍을 구할때 사용 최소신장트리 MST 모든.. 2022. 11. 18.

Do it 알고리즘 코딩테스트 하루코딩 7장 정수론 이론 #18 소수 구하기(에라토스테네스의 체) 소수(prime number)? 약수가 1과 자기 자신 이외에는 존재하지 않는 수 // 1은 소수가 아니다. 코딩테스트에서는 에라토스테네스의 체를 사용하여 소수를 구한다. 과정 1. 구하고자하는 범위 만큼 1차원 배열 생성 2. 2부터 시작하여 // 1은 소수가 아니므로 삭제 배열에서 현재 선택된 숫자의 배수에 해당하는 수를 끝까지 탐색하며 삭제 처음 선택된 숫자는 지우지 않는다. // 소수이므로 3. 끝까지 과정 2를 반복후 남아 있는 수를 출력 // 소수 시간복잡도는? 이중 for문 이므로 O(n^2) 이라고 생각하지만 아니다. 실제는 O(nlog(logn)) // 바깥 for문이 빈번하게 생략되므로 # 19 최대 공약수 구하기(유클리드 호제법) 최대 공약수란.. 2022. 11. 18.

Do it 알고리즘 코딩테스트 하루코딩 6장 그리디 이론 # 17 그리디 알고리즘 (탐욕법) 현재 단계의 선택지 중에서 최선을 선택해나가다 보면, 결과가 최선일 것이라고 가정하는 알고리즘 그러므로 결과가 항상 최선을 보장하지 않는다. 그러므로 그리디로 풀어도 되는지 판단해야한다. 과정 1. 해선택: 현재 단계에서 가장 최선인 해를 선택한다. 2. 적절성 검사: 현재 선택한 선택지가 전체 문제의 제약조건을 벗어나지 않는지 검사한다. 3. 해검사: 결과가 전체문제를 해결할 수 있는지 검사한다. 그렇지 못하면 1로 돌아가 반복한다. 2022. 11. 18.

Do it 알고리즘 코딩테스트 하루코딩 5장 탐색 이론 # 14 깊이우선탐색(DFS) 시작 노드에서 출발하여 탐색할 한쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후, 다른 분기로 이동하여 다시 탐색을 수행하는 알고리즘 기능 특징 시간복잡도 그래프 완전탐색 LIFO 재귀함수 또는 Stack으로 구현 O(V+E) // 재귀함수 구현시 스택 오버 플로우 유의 A{ A(); } 응용 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상정렬 1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화 원본 그래프, 인접 리스트로 그래프 표현, 방문배열 1에 T, 스택에 1 2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접노드를 스택에 삽입 3. 스택에 값이 없을 때까지 반복 이미 다녀간 노드는 재방문X pop() 하면서 탐색 순서에 기록, 인접 노드를 방문 배열에서 체크후.. 2022. 11. 17.

이전 1 2 다음

728x90

티스토리툴바