백준 | 2644번. 촌수 계산 DFS, BFS 풀이
🟦 백준 2644번. 촌수 계산 문제 우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다. 여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오. 입력 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 6. 12.
백준 | 2667번. 단지번호 붙이기 DFS, BFS 풀이
🟦 백준 2667번. 단지번호 붙이기 DFS-BFS 모두 가능 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 입력 첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 6. 12.
JAVA| 그래프 표현 방식 2가지 | ArrayList<Integer> 의 사용
그래프의 표현 방식 2가지 1) ArrayList 타입의 1차원 배열[] static ArrayList A []; //main에서 사용 시 A = new ArrayList[n+1]; for(int i=1; i
- 코딩 테스트 [준비]/JAVA | 활용할 문법 정리
- · 2023. 6. 9.
섹션 2. 코딩테스트 - 05. 탐색 파트 - (1) DFS, BFS
섹션 2. 코딩테스트 - 05. 탐색 ⬛ 05. 탐색 (= 순회) 그래프의 순회 한 정점에서 시작하여 그래프의 모든 정점을 ‘한 번씩’ 중복 없이 방문하는 것 🏓그래프 순회의 종류 1) DFS (깊이 우선 탐색) 한 정점에서 시작하여 깊이 탐색하다가 다시 직전 정점으로 돌아와 깊이 탐색을 반복 (1) 정점 v 방문 (2) 정점 v에 대한 인접 정점들 中 (1개) 방문 방문 안한 w 존재 O : v 방문처리(push) 후, w 방문 (DFS(v) ) 방문 안한 w 존재 X : 더이상 방문할 w들이 존재하지 않으므로 복귀 pop (3) 스택(DFS) 공백되면 종료 2) BFS (너비 우선 탐색) 시작 정점에 대한 인접 정점들 모두를 차례로 방문하고, 다시 처음 방문했던 정점으로 되돌아와 너비 우선 탐색 반복..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 6. 8.
섹션 2. 코딩테스트 - 04. 정렬 파트
섹션 2. 코딩테스트 - 04. 정렬 ⬛ 04. 정렬 ⬛ 04-1. 버블 정렬 🟦 버블 정렬 두 인접한 요소끼리 비교한 뒤, swap 연산 수행하며 정렬 O(n2) 속도 느린 편 🟦 백준 2750번. 수 정렬하기 -1 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. package to_0605_6; import java.util.*; /* 2750번. 수 정렬 하기 1 - 버블 정렬 사용 * */ p..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 6. 5.
섹션 2. 코딩테스트 - 자료구조 (2) 파트
⬛ 03-4. ‘슬라이딩 윈도우’ 알고리즘 🟦 슬라이딩 윈도우 알고리즘 2개의 포인터로 고정 범위 지정한 뒤, 고정 범위를 옆으로 밀면서 이동함. O(n)으로 해결 원할 때 多 사용 크기를 유지한 상태로 이동하면서 조건에 맞는지 유효성 검사하며 탐색함 ⬛ 03-5. 스택과 큐 🟦 스택 (Stack) 삽입/삭제 연산이 후입선출 LIFO 로 이루어지는 자료구조 top 지칭하는 값(한쪽)에서만 삽입과 삭제가 일어남 🟧 스택 용어 1) 위치 top : 삽입과 삭제가 일어나는 위치 지칭 2) 연산 push : top 위치에 새 데이터 삽입 연산 pop : top 위치의 데이터 삭제 & 확인 연산 peek : top 위치의 데이터 단순 확인 연산 🟧 스택 활용 DFS(깊이 우선 탐색), 백트래킹 에서 多 활용 🟦 ..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 6. 5.
섹션 2. 코딩테스트 - 자료구조 (1) 파트
섹션 2. 코딩테스트 [기초] ⬛ 03. 자료구조 ⬛ 03-1. 배열과 리스트 🟦 배열과 리스트 🟧 배열 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조 각 값은 인덱스를 통해 참조 가능 배열 크기는 최초 선언 시 지정 가능하며, 한 번 선언한 뒤 크기 변경 불가능 🟧 리스트 값과 포인터를 묶은 노드를 다시 포인터로 연결한 자료구조 선언 시 크기 별도 지정 안하므로 크기 정해져 있지 않다. ⬛ 03-2. ‘구간 합’ 알고리즘 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 미리 구간합을 구해놓는 알고리즘 **** 🟦 구간 합 알고리즘 1차원 배열의 합 배열 S[i] 🟧 1) 합 배열 S의 정의 S[i] = A[0] + A[1] + ... + A[i]; //A[0] ~ A[i]까지의 합 저장 🟧 ..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 5. 31.
섹션 1. 코딩테스트 [준비] 하기 - 시간 복잡도, 디버깅
섹션 1. 코딩테스트 [준비] 하기 ⬛ 01. 시간 복잡도의 중요성 어떤 알고리즘으로 풀어야 하는가 ? 알고리즘 선택의 기준이 되는 ‘시간복잡도’ ⬛ 01-1. 시간 복잡도 표기법 🟦 시간 복잡도 시간복잡도 : 주어진 문제 해결을 위한 ‘연산 횟수’ 기본적으로 1억 번(10의 8승) 의 연산 = 1초의 시간으로 간주한다. 🟦 시간 복잡도의 유형 1) 빅-오메가 : ‘최선’일 때의 연산 횟수 표기법 2) 빅-세타 : ‘보통’일 때의 연산 횟수 표기법 3) 빅-오(O(n)) : ‘최악’일 떄의 연산 횟수 표기법 - 코테에서 사용 ⬛ 01-2. 시간 복잡도 활용하기 연산 횟수 = (알고리즘 시간복잡도) X (데이터 크기) 시간 제한을 확인하여 가능한 연산 횟수의 제한을 두고 생각할 것. 🟦 (1) 시간 제한 ..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 5. 30.
백준 | 9655번. 돌 게임
9655번. 돌 게임 이 문제는 DP를 활용하는 문제이다. 문제 돌 게임은 두 명이서 즐기는 재밌는 게임이다. 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다. 입력 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000) 출력 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. 문제 풀이 이 문제에서는 상근이와 창영이가 턴을 번갈아가면서 돌을 가져가며, 돌은 1개나 3개를 가져갈 수 있다. 그리고 마지막 돌을 가져가는 사람이 게임을 이기게 되고 돌 n개가..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 5. 25.
섹션4. Sorting & Thinking - (3)
🎈섹션4. Sorting & Thinking - (3) 🟦 4-5. 모임 장소 문제 풀이 완성 코드 최소거리가 될 중앙점 찾는 게 중요하다. row[] 에 각 학생 행 위치 좌표 담고 col[]에 각 학생 열 위치 좌표 담고 그 각각을 오름차순 정렬해준다. 오름차순 정렬된 인덱스가 갖는 좌표의 값(행, 열) 이 최소 이동 거리 좌표값이 된다. ⇒ 이유 : 모이는 지점이 모든 좌표(가장 밀접한 두 점) 의 중앙에만 위치한다면 (그 사이에만 존재한다면) 그 사이의 어디에서 모여도 최소 이동 거리가 동일하다는 사실을 이용한다. package to_0525_1; // 4-5. 모임 장소 import java.util.*; class Solution { //솔루션 함수 public int solution(int[..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 5. 25.
섹션4. Sorting & Thinking - (2)
🎈섹션4. Sorting & Thinking - (2) 🟦 4-3. 카드 가져가기 문제 풀이 첫 시도 코드 1) 먼저 내림차순 정렬 한 뒤에 2) 기본적으로 영희 우선권이므로 (짝수 번째), 철수는 홀수번째 일텐데 3) k번의 철수 우선권이 존재하므로 각 케이스별 차이를 담을 배열을 생성하고 4) 차이가 클 때 철수가 우선권을 사용할 index값을 따로 담고 그 인덱스값의 2배에서 철수가 (짝수 번째) 값을 누적하여 사용할 수 있게 문제 풀이를 시도했다. → 코드가 꼬여서 마무리를 못했다. import java.util.*; class Solution { public int solution(int[] nums, int k){ int answer = 0; //복붙 ArrayList numsA = new A..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 5. 24.
섹션4. Sorting & Thinking - (1)
🎈섹션4. Sorting & Thinking - (1) 🟦 4-1. 이진수 정렬 문제 풀이 첫 시도 코드 정답은 맞았는데 ,코드가 너무 길고 비효율적이다. 우선 객체를 NumCnt로 생성했다. 이 클래스의 경우 Comparable를 implements해서 내부적으로 compareTo메소드를 재정의할 수 있도록 했다. compareTo() 메소드는 기본적으로 cnt값 기준 오름차순 하되, 만약 두 객체간 cnt 값이 일치할 경우 num의 값 기준 오름차순 정렬이 되도록 재정의했다. 우선 [10진수 → 이진수(String) ] : Integer.toBinaryString() 사용하여 각 nums별로 이진수값을 tmp에 담은 뒤, tmp내부를 탐색하여 ‘1’을 가진 경우에 한해서 OneCnt[i]로 카운팅했다..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 5. 22.
프로그래머스 | Lv2. 최솟값 만들기 (Java)
프로그래머스 | Lv2. 최솟값 만들기 (Java) 문제 풀이 A, B 두 배열을 모두 오름차순 정렬 시킨다. 뽑은 값들의 누적합이 최솟값이 되기 위해서는 (A의 가장 작은 값이 B의 가장 큰 값과 곱한 것)을 누적하면 된다. 코드 import java.util.*; class Solution { public int solution(int []A, int []B) { //A, B 모두 오름차순 정렬 후 //A의 가장 작은 값과 B의 가장 큰 값을 곱하면서 점차 범위를 좁히면 된다 int answer = 0; Arrays.sort(A); Arrays.sort(B); for(int i=0; i
- 코딩 테스트 [준비]/[문풀] 프로그래머스_문풀_조지기
- · 2023. 5. 20.
프로그래머스 | Lv2. 숫자의 표현 (Java)
프로그래머스 | Lv2. 숫자의 표현 (Java) 문제 풀이 n 은 10000 이하의 자연수 이므로, 이중 for문을 돌려도 시간 초과가 나지 않는다. 바깥 for문으로 i = 1 ~ n까지 돌면서 연속된 자연수의 시작값을 세팅했다. 안쪽 for문은 j = i+1 ~ n 까지 돌면서 tmp에 각 i 부터 시작되는 연속된 합을 더하다가 - 만약 tmp == 15 가 될 경우 cnt++, break; - 만약 tmp > 15 초과할 경우 그냥 break; 되도록 조건을 걸어두었다. 코드 class Solution { public int solution(int n) { int cnt= 1; for(int i =1; i
- 코딩 테스트 [준비]/[문풀] 프로그래머스_문풀_조지기
- · 2023. 5. 20.
