✔ 이분 그래프 [백준 1707] 문제 분석하기 노드의 집합을 2개로 나누는데, 인접한 노드끼리 같은 집합이 되지 않도록 적절하게 임의로 분할해야 함 트리의 경우 사이클이 발생하지 않으면 탐색을 하면서 다음 노드를 이번 노드와 다른 집합으로 지정하면 되기 때문에 항상 이분 그래프가 됨 하지만 사이클이 발생하여 탐색한 노드에 다시 접근하게 됐을 때 현재 노드의 집합과 같으면 이분 그래프가 불가능하다고 판단할 수 있음 손으로 풀어보기 그래프 데이터를 가중치 없는 인접 리스트로 구현 모든 노드로 각각 DFS 탐색 알고리즘을 적용해 탐색을 수행 DFS를 실행할 때 현재 노드에서 연결된 노드 중 이미 방문한 노드가 나와 같은 집합이면 이분 그래프가 아닌 것으로 판별 그래프의 모든 노드가 이어져 있지 않고, 여러 ..
✔ 소수 구하기 [백준 1929] 문제 분석하기 N의 범위가 1000000이므로 일반적인 소수 구하기 방식으로 문제를 풀면 시간 초과가 발생 따라서 에라토스테네스 방법으로 문제를 풀이 손으로 풀어보기 첫 번째 인덱스가 0인 것을 고려하여 크기가 N + 1인 배열을 선언한 후 값은 각각의 인덱스값으로 채움 1은 소수가 아니므로 삭제 2부터 N의 제곱근까지 값을 탐색하며 값이 인덱스값이면 그대로 두고, 그 값의 배수를 탐색해 0으로 변경 N이 a * b라고 가정했을 때, a와 b 모두 N이 제곱근보다 클 수 없으므로 N의 제곱근까지만 확인해도 전체 범위의 소수 판별 가능 배열에 남아 있는 수 중 M 이상 N 이하의 수를 모두 출력 슈도코드 작성하기 M(시작 수) N(종료 수) A(소수 배열) for(N만큼 ..
✔ 동전 0 [백준 11047] 문제 분석하기 그리디 알고리즘으로 풀 수 있도록 뒤의 동전 가격이 앞에 나오는 동전 가격의 배수가 된다는 조건이 부여되어 반례없이 문제를 해결할 수 있도록 하였음 그러므로 동전을 최소로 사용하여 K를 만들기 위해서는 가장 가격이 큰 동전부터 차례대로 사용하면 됨 손으로 풀어보기 가격이 큰 동전부터 내림차순으로 K보다 가격이 작거나 같은 동전이 나올 때까지 탐색 탐색을 멈춘 동전의 가격으로 K를 나눠 몫은 동전 개수에 더하고, 나머지는 K값으로 갱신 위 과정을 나머지가 0이 될 때까지 반복 슈도코드 작성하기 N(동전 개수) K(목표 금액) A(동전 데이터 배열) for(N만큼 반복하기) { A 배열 저장하기 } for(N만큼 반복 → N - 1 ~ 0으로 역순으로 반복하기)..
✔ 수 찾기 [백준 1920] 문제 분석하기 N의 범위가 100000이므로 단순 반복문으로는 문제를 풀 수 없음 이진 탐색을 적용하면 O(MlogN) 시간 복잡도로 해결할 수 있으며, 자바의 기본 정렬을 사용하더라도 O(NlogN) 시간 복잡도를 가짐 손으로 풀어보기 탐색 데이터를 1차원 배열에 저장한 다음 저장된 배열을 정렬 X라는 정수가 존재하는지 이진 탐색을 사용해 확인 슈도코드 작성하기 N(정렬할 수 개수) M(탐색할 숫자의 개수) A(정렬할 배열 선언하기) for(N의 개수만큼 반복하기) { A 배열 저장하기 } A 배열 정렬하기 for(M의 개수만큼 반복하기) { target(찾아야 하는 수) start(시작 인덱스) end(종료 인덱스) while(시작 인덱스 target) { 종료 인덱스 ..
✔ 미로 탐색 [백준 2178] 문제 분석하기 N, M의 최대 데이터의 크기가 100으로 매우 작기 때문에 시간 제한은 별도로 생각하지 않아도 됨 지나야 하는 칸 수의 최솟값을 찾아야하므로 BFS를 이용해 완전 탐색을 진행하며 몇 번째 깊이에서 원하는 값을 찾을 수 있는지 구함 BFS는 해당 깊이에서 갈 수 있는 노드 탐색을 마친 후 다음 깊이로 넘어가기 때문에 적합 손으로 풀어보기 시작 위치인 (1, 1)에서 BFS를 실행하여 상, 하, 좌, 우 네 방향을 보며 인접한 칸을 살펴봄 인접한 칸의 숫자가 1이면서 아직 방문하지 않았다면 큐에 삽입 이때 방문한 노드의 배열의 값을 깊이 + 1로 업데이트 종료 시점 (N, M)에서 BFS를 종료하여 깊이를 출력 슈도코드 작성하기 dx, dy (상하좌우를 탐색하..
✔ 연결 요소의 개수 [백준 11724] 문제 분석하기 노드의 최대 개수가 1000이므로 시간 복잡도 N² 이하의 알고리즘을 모두 사용할 수 있음 연결 요소는 엣지로 연결된 노드의 집합이며, 한 번의 DFS가 끝날 때까지 탐색한 모든 노드의 집합을 하나의 연결 요소로 판단 손으로 풀어보기 그래프를 인접 리스트로 저장하고 방문 배열도 초기화 이때, 방향이 없는 그래프이므로 양쪽 방향으로 엣지를 모두 저장함 임의의 시작점인 1에서 DFS를 수행 아직 방문하지 않은 노드 중 시작점을 다시 정해 탐색을 진행 모든 노드를 방문한 후 전체 탐색을 종료 총 DFS의 횟수가 연결 요소의 개수가 되게 됨 만약 그래프가 모두 연결되어 있었다면 DFS는 1번 실행되게 됨 슈도코드 작성하기 n(노드 개수) m(에지 개수) A..
✔ 소트인사이드 [백준 1427] 문제 분석하기 숫자를 각 자릿수별로 나누는 작업이 필요하므로 입력값을 String으로 받은 후 substring() 함수를 이용해 자릿수 단위로 분리하고, 이를 다시 int형으로 변경해 배열에 저장하도록 함 이후 N의 길이가 크지 않으므로 선택 정렬 알고리즘을 이용해 해결 손으로 풀어보기 String 변수로 정렬할 데이터를 받은 후 substring() 함수를 사용해 각 자릿수별로 나눈 후 int형 배열에 저장 배열의 데이터를 선택 정렬 알고리즘을 이용해 최댓값을 찾아 swap하며 내림차순 정렬 슈도코드 작성하기 str(정렬할 수) A(자릿수별로 구분해 저장한 배열) for(str의 길이만큼 반복하기) { A 배열 저장 → str.substring 사용하기 } for(i..
✔ 수 정렬하기 [백준 2750] 문제 분석하기 N의 범위가 1000으로 매우 작기 때문에 O(N²)의 시간 복잡도를 갖는 버블 정렬 알고리즘을 이용해도 해결 가능 손으로 풀어보기 비교 연산이 필요한 루프 범위를 설정 인접한 데이터 값을 비교 swap 조건에 부합하면 swap 연산을 수행 루프 범위가 끝날 때까지 2~3을 반복 정렬 영역을 설정한 후, 다음 루프를 실행할 때는 이 영역을 제외 비교 대상이 없을 때까지 1~5를 반복 슈도코드 작성하기 N(정렬할 수 개수) A(정렬할 배열 선언) for(루프의 개수만큼 반복) { for(정렬하는 범위만큼 반복) { 현재 A 배열의 값보다 1칸 오른쪽 배열의 값이 더 작으면 두 수 바꾸기 } } A 배열 출력 코드 구현하기 /** * 2750) 수_정렬하기 *..
