본문 바로가기

728x90

전체 글302

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.

Do it 알고리즘 코딩테스트 하루코딩 4장 정렬 이론 # 10 버블정렬 인접한 데이터끼리 크기 비교하여 swap 시간 복잡도 O(n^2) // 1번 루프당 1개 픽스 0과 1 비교하여 스왑, 1과 2를 비교하여 스왑, ... 맨뒤가 정렬된 영역 정렬된 영역을 제외하고 0과 1 비교하여 스왑, 1과 2를 비교하여 스왑, ... 만약 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면, 모두 정렬되어 있다는 뜻이므로 더 이상 정렬 수행하지 않아도 된다. # 11 선택 정렬 정렬 해야 되는 범위에서 최솟값 또는 최댓값을 찾고, 남은 정렬 해야 되는 부분의 가장 앞에 있는 데이터와 swap 시간 복잡도 O(n^2) // 1번 루프당 1개 픽스 # 12 삽입 정렬 이미 정렬된 데이터의 범위에 정렬되지 않은 하나의 데이터를 적절한 위치에 삽입시켜 정렬 .. 2022. 11. 17.

Do it 알고리즘 코딩테스트 하루코딩 3장 자료구조 이론 Do it 알고리즘 코딩테스트 하루코딩 3장 자료구조 요약 # 5 배열과 리스트 java 배열 메모리에 연속적인 공간에 값을 저장하는 자료구조 특징 1. 인덱싱O, 접근속도 ↑ 2. 값 삽입, 삭제 번거로움, 속도 ↓, 주변 값 이동시키는 과정 필요 3. 크기 선언할 때 지정O, 크기 고정 4. 구조 간단 리스트 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조 특징 1. 인덱싱X, 접근속도 ↓, Head 포인터부터 순서대로 접근하여 속도 느림 2. 값 삽입, 삭제 편리, 속도 ↑, 주변 값 이동시키는 과정 필요X 3. 크기 선언할때 지정X, 크기 가변 4. 구조 복잡 java에서는 ArrayList LinkedList 상황별 유리한 자료구조 배열: 크기고정, 값 접근 리스트: 크기가변, 삽입,.. 2022. 11. 16.

이전 1 ··· 18 19 20 21 22 23 24 ··· 34 다음

728x90

티스토리툴바