섹션 3. 코딩테스트 [실전편] - 08. 그래프 - (2) -위상정렬
⬛ 08-3. 위상 정렬 🟦 위상 정렬 사이클이 없는 방향 그래프에서 노드 간의 순서 결정하는 알고리즘 사이클이 없어야 한다.(사이클 존재 시, 명확하게 순서 결정 불가능) 🟧 위상 정렬 수행 과정 1) 진입 차수가 0인 노드를 큐에 저장 2) 큐에서 데이터 poll() 후, 결과에 추가. 해당 노드가 가리키는 인접 정점의 진입차수 D[] 의 값 1씩 뺌 3) 감소한 상태의 진입 차수가 0인 경우 다시 Q에 add() 4) 큐가 빌때까지 1~3 반복 🟦 백준 2252번. 줄 세우기 문제 N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 6. 28.
![섹션 3. 코딩테스트 [실전편] - 08. 그래프 - (1) 이분 그래프, 유니온 파인드](http://i1.daumcdn.net/thumb/C120x120/?fname=https://blog.kakaocdn.net/dn/n1Bbt/btslmUfxOGN/by8oYHE3FxFQK9Nm2ZTRKk/img.png)
섹션 3. 코딩테스트 [실전편] - 08. 그래프 - (1) 이분 그래프, 유니온 파인드
섹션 3. 코딩테스트 [실전편] - 08. 그래프 ⬛ 08. 그래프 그래프는 노드와 엣지로 구성된 집합. 노드는 데이터 표현 단위, 에지는 노드를 연결 ⬛ 08-1. 그래프의 표현 그래프 구현 방식은 크게 3가지가 있다. 🟦 1. 에지 리스트 에지 중심으로 그래프 표현하는 방식이다. 🟧 1) 가중치 X 그래프 표현 배열의 행 2개로 출발노드, 도착노드 표현한다. 🟧 2) 가중치 O 그래프 표현 배열 행 3개로 출발노드 도착노드, 가중치 표현한다. 🟦 2. 인접 행렬 2차원 배열 이용하여 노드 중심으로 표현하는 방식이다. 다만, 에지 탐색 시, N번 접근해야 하므로 노드 개수에 비해서 에지가 적을 때는 공간 효율성 떨어진다. 🟧 1) 가중치 X 그래프 표현 i행 j열에 i → j 표현 🟧 2) 가중치 O ..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 6. 21.
섹션 2. 코딩테스트 - 07. 정수론 -(1) 소수, 오일러 피, 유클리드 호제법
섹션 2. 코딩테스트 - 07. 정수론 ⬛ 07. 정수론 정수론 : 수의 성질 탐구하고 공부하는 이론 분야 실제 코테에서는 모든 정수론 분야가 나오는 것은 아니므로, 가장 많이 등장하는 ‘소수 부분’과 ‘호제법’ 부분을 집중적으로 다뤄보자. ⬛ 07-1. 소수 구하기 🟦 소수 1과 자기 자신 외에 약수가 존재하지 않는 수 소수 판별 방식을 묻는 ‘소수 구하기 문제’ 종종 출제 🟦 대표적인 소수 판별 방식 | ‘에라토스테네스의 체’ 시간 복잡도 : O(N2) 이중 for문 사용하므로.. 🟧 에라토스테네스의 체 방식 구하고자 하는 소수 범위만큼의 1차원 배열[] 생성 for(2~N) : 현재 i의 숫자 선택 → (첫 수 제외) 현재 선택된 i의 배수를 배열 끝까지 탐색하면서 모두 지움 그 다음 지워지지 않은..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 6. 15.
백준 | 1449번. 수리공 항승 - 그리디 문제
🟦 백준 1449번. 수리공 항승 문제 항승이는 품질이 심각하게 나쁜 수도 파이프 회사의 수리공이다. 항승이는 세준 지하철 공사에서 물이 샌다는 소식을 듣고 수리를 하러 갔다. 파이프에서 물이 새는 곳은 신기하게도 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 샌다. 항승이는 길이가 L인 테이프를 무한개 가지고 있다. 항승이는 테이프를 이용해서 물을 막으려고 한다. 항승이는 항상 물을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 물이 다시는 안 샌다고 생각한다. 물이 새는 곳의 위치와, 항승이가 가지고 있는 테이프의 길이 L이 주어졌을 때, 항승이가 필요한 테이프의 최소 개수를 구하는 프로그램을 작성하시오. 테이프를 자를 수 없고, 테이프를 겹쳐서 붙이는 것도 가능하다. 입력 첫째 줄에 물이 새..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 6. 15.
[추가] 회의실 배정 - 그리디 문제
🟦 회의실 배정 - 그리디 문제 회의실 배정 한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. ▣ 입력설명 첫째 줄에 회의의 수 n(1
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 6. 15.
[추가] 씨름선수 - 그리디 문제
🟦 씨름선수 - 그리디 문제 현수는 씨름 감독입니다. 현수는 씨름 선수를 선발공고를 냈고, N명의 지원자가 지원을 했습니다. 현수는 각 지원자의 키와 몸무게 정보를 알고 있습니다. 현수는 씨름 선수 선발 원칙을 다음과 같이 정했습니다. “A라는 지원자를 다른 모든 지원자와 일대일 비교해서 키와 몸무게 모두 A지원자 보다 높은 (크고, 무겁다) 지원자가 존재하면 A지원자는 탈락하고, 그렇지 않으면 선발된다.” N명의 지원자가 주어지면 위의 선발원칙으로 최대 몇 명의 선수를 선발할 수 있는지 알아내는 프로그램을 작성하세요. ▣ 입력설명 첫째 줄에 지원자의 수 N(5
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 6. 15.
백준 | 1946번. 신입사원 - 그리디 & 정렬 기준 재정의
🟦 백준 1946번. 신입사원 - 그리디 문제 언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다. 그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다. 이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 6. 15.
백준 | 11399번. ATM - 그리디 & 구간 합 이용
🟦 백준 11399번. ATM 그리디 & 구간합 사용하는 문제 문제 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 6. 14.
섹션 2. 코딩테스트 - 06. 그리디 알고리즘
섹션 2. 코딩테스트 - 06. 그리디 ⬛ 06. 그리디 알고리즘 ⬛ 06-1. 그리디 알고리즘 🟦 그리디(Greedy) 알고리즘 현재 상태에서 볼 수 있는 최적해가 전체의 최적해라고 가정하며 근시안적으로 보는 알고리즘 전체를 보지 않고, 근시안적 선택(현 상황에서의 부분적 최적해)가 최종 문제의 최적해를 얻는 일이라고 가정하며 답을 찾아가는 알고리즘 항상 최적해를 보장하지는 못한다. 🟧 그리디 알고리즘 수행 과정 1) 해 선택 : 현재 상태의 부분적 최적해 선택 2) 적절성 검사 : 그 최적해가 전체 문제 제약 조건 벗어나지 않는지 검사 3) 해 검사 : 현재까지 선택한 해 집합들이 전체 문제 해결 가능한지 검사. 만약 전체 문제 해결 못한다면 다시 1)로 돌아가 이 과정을 반복 🟦 백준 11047번...
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 6. 14.
섹션 2. 코딩테스트 - 05. 탐색 - (2) 이분 탐색
섹션 2. 코딩테스트 - 05. 탐색 - (2) 이분 탐색 ⬛ 05-3. 이진 탐색 🟦 이진 탐색 (=이분 검색) 이진 탐색 : 이미 정렬된 데이터에서 원하는 값을 찾아내는 알고리즘 정렬된 대상 데이터 중앙값 vs 타겟값 비교하여 검색 범위를 절반씩 줄여나감 시간 복잡도 : O(logN) 🟧 이진 탐색 핵심 (1) 이미 정렬된 데이터에서 중앙값 선택 (2) 키값 < 중앙값 : 중앙값의 왼쪽 데이터셋 선택 (3) 중앙값 < 키값 : 중앙값의 오른쪽 데이터셋 선택 (4) 중앙값 == 키값 : break 탈출 🟦 백준 1920번. 원하는 정수 찾기 for문으로 각 타겟 데이터셋 찍으면서 while()문으로 탐색 대상 데이터의 st≤ed 동안 mid 값과 현재 타겟값 비교하며 if, if else 문 통과하면 ..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 6. 13.
백준 | 1926번. 그림 - DFS, BFS 모두 풀이
🟦 백준 1926번. 그림 문제 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다. 입력 첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다) 출력 첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 6. 13.
백준 | 4963번. 섬의 개수 - DFS, BFS 모두 풀이
🟦 백준 4963번. 섬의 개수 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다. 입력의 마지막 줄에는 0이 두 개 주어진다. 출력 각 테스트 케이스..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 6. 12.
백준 | 1012번. 유기농 배추 - DFS, BFS 모두 풀이
🟦 백준 1012번. 유기농 배추 문제 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다. 한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 6. 12.