boj
-
[BFS] BOJ 2667 : 단지번호붙이기백준 문제풀이/GRAPH 2019. 8. 14. 02:05
백준 알고리즘 강의를 토대로 작성된 문제풀이입니다. DFS 와 BFS 의 개념에 대해서는 지난 포스트를 봐주세요. DFS : 2019/05/23 - [프로그래밍/알고리즘] - [알고리즘] 깊이 우선 탐색(DFS, Depth-First Search) BFS : 2019/05/26 - [프로그래밍/알고리즘] - [알고리즘] 너비 우선 탐색(BFS, Breadth-First Search) 예제 : 2019/07/22 - [프로그래밍/1일1백준] - [Graph] BOJ 1260 : DFS 와 BFS 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 ..
-
[BFS] BOJ 11724 : 연결 요소백준 문제풀이/GRAPH 2019. 7. 24. 06:14
백준 알고리즘 강의를 토대로 작성된 문제풀이입니다. DFS 와 BFS 의 개념에 대해서는 지난 포스트를 봐주세요. DFS : 2019/05/23 - [프로그래밍/알고리즘] - [알고리즘] 깊이 우선 탐색(DFS, Depth-First Search) BFS : 2019/05/26 - [프로그래밍/알고리즘] - [알고리즘] 너비 우선 탐색(BFS, Breadth-First Search) 예제 : 2019/07/22 - [프로그래밍/1일1백준] - [Graph] BOJ 1260 : DFS 와 BFS 문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,0..
-
[Graph] BOJ 1260 : DFS 와 BFS백준 문제풀이/GRAPH 2019. 7. 22. 06:03
백준 알고리즘 강의를 토대로 작성된 문제풀이입니다. DFS 와 BFS 의 개념에 대해서는 지난 포스트를 봐주세요. DFS : 2019/05/23 - [프로그래밍/알고리즘] - [알고리즘] 깊이 우선 탐색(DFS, Depth-First Search) BFS : 2019/05/26 - [프로그래밍/알고리즘] - [알고리즘] 너비 우선 탐색(BFS, Breadth-First Search) 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과..
-
[Graph] BOJ 13023 : ABCDE백준 문제풀이/GRAPH 2019. 7. 18. 08:52
백준 알고리즘 강의를 토대로 작성된 문제풀이입니다. 문제 BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다. 오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다. A는 B와 친구다. B는 C와 친구다. C는 D와 친구다. D는 E와 친구다. 위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다. 둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주..
-
[Brute Force] BOJ 6603번 : 로또백준 문제풀이/BRUTE FORCE 2019. 7. 7. 12:58
백준 알고리즘 강의를 토대로 작성된 문제풀이입니다. 문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다. 예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34]) 집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다..
-
[Brute Force] BOJ 1476 번 : 날짜 계산백준 문제풀이/BRUTE FORCE 2019. 6. 25. 20:08
문제 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19) 우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1년이 지날 때마다, 세 수는 모두 1씩 증가한다. 만약, 어떤 수가 범위를 넘어가는 경우에는 1이 된다. 예를 들어, 15년은 15 15 15로 나타낼 수 있다. 하지만, 1년이 지나서 16년이 되면 16 16 16이 아니라 1 16 16이 된다. ..
-
[Greedy] BOJ 4796 번 : 캠핑백준 문제풀이/GREEDY 2019. 5. 29. 00:15
문제 보기 정말 작심삼일이라고 고작 8일하고 포기했던 1일 1백준을 다시 시작합니다... 정말 직관적이고 쉬운 문제를 풀면서 자신감을 키우기 위해 그리디문제를 가져왔습니다. 풀이 연속하는 20일중 10일을 사용할 수 있다 .... 이런 경우에 캠핑을 가장 많이 사용하기 위해서는 어떻게 해야될까요? 당연히 휴가 시작날짜부터 바로 캠핑을 시작하는 것이 가장 많이 사용하는 방법일겁니다. 그렇게 되면 휴가 28일중 첫날부터 사용하여 연속하는 20일 동안 총 10일을 사용할수 있을것입니다. 그리고 남은 8일은 다시 연속하는 20일이 되기 때문에 사용횟수가 초기화되서 8일 모두 사용할 수 있게 됩니다. 이러한 상황을 이제 코드로 구현해봅시다. 이러한 Case 의 번호를 저장할 변수 a 를 선언합니다. 연속적인 연산..
-
[STACK] BOJ 1874 번 문제풀이백준 문제풀이/etc 2019. 5. 13. 13:33
문제 분석 문제에 친절하게 스택을 사용하라고 나와있죠? ㅎㅎ 내용은 이렇습니다. 원하는 수를 사용하기 위해서는 반드시 스택에 push, pop 하는 과정을 거쳐야 합니다. 스택에 값은 아래의 그림처럼 채워집니다. 예를 들어, 가장 처음에 5를 사용해야 한다면 1 ~ 5 의 숫자를 push 한 후에 pop 을해서 사용하는 겁니다. 이게 이해가 되셨다면, 만들고자 하는 배열을 저장해야 하는데 이 배열을 큐에 저장하면 간단합니다. 입력 파트를 보면 먼저 입력된 값부터 스택에서 추출하기 때문입니다. 따라서 예시문제를 순서대로 큐에 push 하게 되면 아래 그림처럼 채워집니다. 자, 이제부터 알고리즘을 설계해봅시다. 1. 큐를 선언하여 입력되는 값을 큐에 넣습니다. 2. 우선 큐의 front 값에 대해서 처리해줍..