Algorithm & Data Structure/BOJ
-
[백준] 1922. 네트워크 연결(MST, Kruskal)2020.03.25
-
[백준] 9251 LCS2020.03.11
-
[백준] 9466 팀 프로젝트(DFS, Cycle)2020.03.04
-
[백준] 1699 제곱수의 합 (Dynamic programming)2020.03.02
-
[백준] 11057 오르막 수 (DP)2020.02.27
-
[백준] 15686 치킨 배달 (Brute force)2020.02.23
-
[백준] 16234 인구 이동2020.02.18
[백준] 1922. 네트워크 연결(MST, Kruskal)
https://www.acmicpc.net/problem/1922
1922번: 네트워크 연결
이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다.
www.acmicpc.net
최소 신장 트리 문제였습니다.
크루스칼 알고리즘을 사용해 해결했습니다.
* 간선정보를 저장하는 자료형을 LinkedList로 하면 시간초과가 나서 Edge클래스를 자료형으로 하는 배열을 사용했습니다.
'Algorithm & Data Structure > BOJ' 카테고리의 다른 글
| [백준] 9252. LCS 2 (Longest Common Subsequence) (0) | 2020.03.26 |
|---|---|
| [백준] 5582. 공통 부분 문자열 (LCS, Longest Common Substring) (0) | 2020.03.26 |
| [백준] 9251 LCS (0) | 2020.03.11 |
| [백준] 9466 팀 프로젝트(DFS, Cycle) (0) | 2020.03.04 |
| [백준] 1699 제곱수의 합 (Dynamic programming) (0) | 2020.03.02 |
[백준] 9251 LCS
https://www.acmicpc.net/problem/9251
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
LCS(Longest Common Subsequence) 최장 공통 부분 문자열 알고리즘 문제였습니다.
*Longest Common Substring 은 연속적인 부분 문자열이지만 Longest Common Subsequence 는 연속적이지 않은 부분 문자열 입니다.
알고리즘이 생소해서 다른 블로그를 참고해서 풀었습니다.
LCS(Longest Common Subsequence) 알고리즘
1. 개요 LCS란 Longest Common Subsequence의 약자로 최장 공통 부분 문자열이다. 우리가 알고 있는 substring과 비교하면 substring은 연속된 부분 문자열이고 subsequence는 연속적이지는 않은 부분 문자열이다...
twinw.tistory.com
'Algorithm & Data Structure > BOJ' 카테고리의 다른 글
| [백준] 5582. 공통 부분 문자열 (LCS, Longest Common Substring) (0) | 2020.03.26 |
|---|---|
| [백준] 1922. 네트워크 연결(MST, Kruskal) (0) | 2020.03.25 |
| [백준] 9466 팀 프로젝트(DFS, Cycle) (0) | 2020.03.04 |
| [백준] 1699 제곱수의 합 (Dynamic programming) (0) | 2020.03.02 |
| [백준] 11057 오르막 수 (DP) (0) | 2020.02.27 |
[백준] 9466 팀 프로젝트(DFS, Cycle)
https://www.acmicpc.net/problem/9466
9466번: 텀 프로젝트
문제 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다. 학생들이(s1, s2, ..., sr)이라 할 때, r=
www.acmicpc.net
2차원 배열, 스택을 사용해서 풀면 메모리 초과가 나서 인터넷을 참고해서 풀었습니다.
참고사이트 : https://minbyeongchan.github.io/category/Algorithm/9466
[백준] 9466 팀 프로젝트
Problem
minbyeongchan.github.io
해당 정점을 방문하고 해당 정점에서 가르키는 다음 정점(next)이 방문안했다면 dfs(next)호출, 방문했다면 사이클 형성 여부 확인(check)방식으로 진행됩니다.
마지막엔 해당정점에 사이클여부를 확인했다고 체크 해줍니다.
'Algorithm & Data Structure > BOJ' 카테고리의 다른 글
| [백준] 1922. 네트워크 연결(MST, Kruskal) (0) | 2020.03.25 |
|---|---|
| [백준] 9251 LCS (0) | 2020.03.11 |
| [백준] 1699 제곱수의 합 (Dynamic programming) (0) | 2020.03.02 |
| [백준] 11057 오르막 수 (DP) (0) | 2020.02.27 |
| [백준] 15686 치킨 배달 (Brute force) (0) | 2020.02.23 |
[백준] 1699 제곱수의 합 (Dynamic programming)
https://www.acmicpc.net/problem/1699
1699번: 제곱수의 합
어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는
www.acmicpc.net
동적 계획법 문제였습니다.
자연수를 1부터 n까지 나열하며 최소의 제곱수의 합을 표현해보면서 점화식을 구해봅니다.
점화식
1. n이 완전제곱수일 경우 제곱수의 수는 1개
2. 나머지는 (해당수 - k 번째 제곱수 항의 수) + (k 번째 제곱수 항의 수) (k=1,2,3....)해나가며 최소값을 정해주면 됩니다.
'Algorithm & Data Structure > BOJ' 카테고리의 다른 글
| [백준] 9251 LCS (0) | 2020.03.11 |
|---|---|
| [백준] 9466 팀 프로젝트(DFS, Cycle) (0) | 2020.03.04 |
| [백준] 11057 오르막 수 (DP) (0) | 2020.02.27 |
| [백준] 15686 치킨 배달 (Brute force) (0) | 2020.02.23 |
| [백준] 17779 게리 맨더링 2 (2) | 2020.02.22 |
[백준] 11057 오르막 수 (DP)
https://www.acmicpc.net/problem/11057
11057번: 오르막 수
오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.
www.acmicpc.net
동적 계획법 문제였습니다.
규칙은 찾았지만 구현하기 까다로웠습니다.
처음 생각
각 자리수 마다 오르막 수는 이전 자리수들의 경우의 수들을 계속해서 합쳐나가는? 식으로 접근함.
위의 방법을 함수로 구현하려다가 까다로워져서 다른방법 생각..
다른 방법
반복문을 통해서 위의 sum을 구현해봄.
일단 1자리 수는 모두 1로 초기화 해줍니다.
2자리 부터 점화식을 사용해 해결합니다.
k 를 시작하는 수로 생각하면
k부터 만들수 있는 오르막 수 는 이전 자리 수(n-1)에서 k부터 시작해서 9까지 만들 수 있는 경우의 수를 모두 더해주면 됩니다.
코드를 보는게 이해하기 더 쉬울것 같습니다.
'Algorithm & Data Structure > BOJ' 카테고리의 다른 글
| [백준] 9466 팀 프로젝트(DFS, Cycle) (0) | 2020.03.04 |
|---|---|
| [백준] 1699 제곱수의 합 (Dynamic programming) (0) | 2020.03.02 |
| [백준] 15686 치킨 배달 (Brute force) (0) | 2020.02.23 |
| [백준] 17779 게리 맨더링 2 (2) | 2020.02.22 |
| [백준] 16234 인구 이동 (0) | 2020.02.18 |
[백준] 15686 치킨 배달 (Brute force)
https://www.acmicpc.net/problem/15686
15686번: 치킨 배달
크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는
www.acmicpc.net
백트래킹을 사용해 완전탐색하는 문제였습니다.
문제 접근
- 치킨집이 최대 m개까지 설치 가능하므로 1개부터 시작해서 치킨거리 구해야한다.
- 필요한 함수는 도시의 치킨거리를 구하는 함수 1개, 재귀호출과 백트래킹으로 완전탐색할 함수 1개 필요
- 치킨집과 집의 위치를 담아둘 저장소가 필요
알고리즘
- 도서의 모든 집과 치킨집의 위치를 각각 LinkedList에 담는다.
- 지도에 치킨집을 1개부터 최대 m개까지 설치한다.
- 치킨집의 각 최대 설치 개수가 만족되면 도시의 치킨거리를 구하여 최소값을 업데이트 해준다.
* 메인에서 설치할 최대 치킨집의 개수를 1개부터 최대 m개까지 설정해주면서 완전탐색을 해야합니다.
* 매번 설치되는 치킨집을 담아둘 LinkedList가 필요합니다.
* 재귀호출과 백트래킹을 이해하는게 핵심인 문제같습니다.
'Algorithm & Data Structure > BOJ' 카테고리의 다른 글
| [백준] 1699 제곱수의 합 (Dynamic programming) (0) | 2020.03.02 |
|---|---|
| [백준] 11057 오르막 수 (DP) (0) | 2020.02.27 |
| [백준] 17779 게리 맨더링 2 (2) | 2020.02.22 |
| [백준] 16234 인구 이동 (0) | 2020.02.18 |
| [백준] 16235 나무 재테크 (0) | 2020.02.18 |
[백준] 17779 게리 맨더링 2
https://www.acmicpc.net/problem/17779
17779번: 게리맨더링 2
재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다. 재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다
www.acmicpc.net
완전탐색 문제 였습니다.
경계설정하기가 까다로워 보이지만 주어진 조건을 그대로 구현하면 경계설정은 생각보다 간단했습니다.
문제에 주어진 조건을 그대로 따라 순차적으로 구현해주면 됩니다.
문제 풀이
- 기준점을 선별한다. 문제에 제시된 조건을 활용
- 경계선을 따라 그리고 경계선 안쪽에 있는 5번구역을 먼저 masking해준다.
- 5번구역을 제외한 나머지 1,2,3,4구역을 masking한다
- masking된 맵을 사용해 각 지역의 인구수 총합을 계산하고, 인구차이의 최소값을 업데이트 한다.
조건들은 문제에 주석처리 하였습니다.
'Algorithm & Data Structure > BOJ' 카테고리의 다른 글
| [백준] 11057 오르막 수 (DP) (0) | 2020.02.27 |
|---|---|
| [백준] 15686 치킨 배달 (Brute force) (0) | 2020.02.23 |
| [백준] 16234 인구 이동 (0) | 2020.02.18 |
| [백준] 16235 나무 재테크 (0) | 2020.02.18 |
| [백준] 17837 새로운 게임 2 (0) | 2020.02.15 |
[백준] 16234 인구 이동
https://www.acmicpc.net/problem/16234
16234번: 인구 이동
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명
www.acmicpc.net
Deque를 사용해 해결했습니다.
풀이 방법
- 하루를 보내면서 BFS적으로 연합할 수 있는 나라들을 임시 큐에 넣어줍니다.
- 탐색이 끝나면 Deque<Deque> unions 에 연합된 나라들을 담은 임시 큐를 넣어줍니다.
- 만약 연합이 안되있으면(나라가 1개라면) unions에 넣지 않습니다.
- 하루가 지나고 unions의 상태를 검사해서 비어있으면 그대로 종료합니다.
- 아니면 연합별로 인구를 이동시킵니다.
* 하루가 지날때마다 visited배열을 초기화 해줍니다.
'Algorithm & Data Structure > BOJ' 카테고리의 다른 글
| [백준] 15686 치킨 배달 (Brute force) (0) | 2020.02.23 |
|---|---|
| [백준] 17779 게리 맨더링 2 (2) | 2020.02.22 |
| [백준] 16235 나무 재테크 (0) | 2020.02.18 |
| [백준] 17837 새로운 게임 2 (0) | 2020.02.15 |
| [백준] 15684 사다리 조작(Brute force) (0) | 2020.02.14 |