알고리즘/백준

[백준 11724] 연결 요소의 개수 C++

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주�� www.acmicpc.net 이번 시간은 그래프의 기본인 연결 요소의 개수를 구하는 문제의 풀이법을 설명하겠습니다. 문제에서 조건은 방향이 없는 그래프라고 말하고 있습니다. 입력으로 정점의 개수 N과 간선의 개수 M을 입력받고요, 연결된 요소가 총 몇개 있는지 구하는 문제입니다. 이 문제는 DFS, BFS로 어느것으로 풀어도 되지만, 저는 DFS를 이용해서 깊..

[백준 16929] Two Dots C++

https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문�� www.acmicpc.net 이번 시간은 Tow Dots 문제 풀이법에 대해 설명드리겠습니다. 같은 색깔에 한해서 Circle이 존재하느냐를 찾는 문제입니다. 그래프 탐색 알고리즘인 BFS와 DFS 중 어떤 것을 사용하면 좀 더 효율적으로 사용할지 고민하다가 DFS 깊이 탐색으로 일정하게 쭉 들어가면서 탐색하면 될 것이라고 생각했습니다. DFS를 구현하는 방법은 대표적으로 2가지가 있습니다. 1. Stack을 이..

[백준 2667] 단지번호붙이기 C++

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net 안녕하세요. 현's story 입니다. 이번 시간에는 단지번호붙이기 풀이법에 대해 설명해드리겠습니다. 이 문제의 경우 여러가지 변형된 문제를 다수 풀어본 경험이 있습니다. 자신감(?)에 넘쳐서 바로 풀었더니!!!땅 하고 프로그램이 안돌아가더라고요.. 다시 주의깊게 보니까 입력이 변수 간에 서로 띄워져있지 않고 모두 붙여져 있는 형태로 입력이 들어오기 때문에 한자리만 입력받을 필요가 생겼습니다. i..

[백준 17090] 미로 탈출하기 C++

https://www.acmicpc.net/problem/17090 17090번: 미로 탈출하기 크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문� www.acmicpc.net 오늘은 Gold 2 난이도를 가지는 미로 탈출하기 문제 풀이를 하려고 합니다. Gold 2난이도라고 해서 큰 맘먹고 문제를 풀었는데, 생각외로 10분만에 문제를 풀어버렸습니다.. 대단한건아니지만....문제 길이도 짧고 규칙성을 바로 찾아서 바로 풀게 되었습니다. 문제에서 각 적힌 칸에서 U, R, D, L, 문자 그대로 (Up, Right, Down, Left)방향으로 이동해서 ..

[백준 12931] 두 배 더하기 C++

https://www.acmicpc.net/problem/12931 12931번: 두 배 더하기 모든 값이 0으로 채워져 있는 길이가 N인 배열 A가 있다. 영선이는 다음과 같은 두 연산을 수행할 수 있다. 배열에 있는 값 하나를 1 증가시킨다. 배열에 있는 모든 값을 두 배 시킨다. 배열 B가 주� www.acmicpc.net 문제풀이 0으로 채워진 배열에서 1. 배열 중 하나의 값을 1 증가 2. 배열의 모든 값을 두배 시킴 의 방법을 사용해서 입력으로 주어진 배열을 찾는데 최소 횟수를 구하는 문제인데, 역으로 입력으로 주어진 배열에서 0으로 채워지게 하려면 최소 몇번을 구해야하는지로 바꿔서 풀었습니다. 다행이도, 2배와 1추가는 홀짝으로 구분할 수 있기 때문에, 모든 배열이 0을 만나지 않는 한 무..

[백준 16987] 계란으로 계란치기 C++

https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 문제풀이 계란으로 계란치기 문제의 경우, 글을 해석하느라 시간이 조금 오래걸렸습니다. 생각 보다 문제에 도움이 안되는 말이 앞에 주절주절이 있고, 중간 설명하는 부분에 중요 포인트가 많은데 처음 읽었을 때 확실하게 안와닿는 부분이 많았습니다. 먼저, 문제에서 말한대로 계란의 정보를 가져오는데, 저는 struct로 대입했습니다. (뭔가 구조안에 넣어서 체계적으로 만들고 싶은 생각?) ..