본문 바로가기

반응형

PS/백준

(318)
[BOJ] 백준 6080 Bad Grass (Swift) 문제 https://www.acmicpc.net/problem/6080 6080번: Bad Grass Bessie was munching on tender shoots of grass and, as cows do, contemplating the state of the universe. She noticed that she only enjoys the grass on the wide expanses of pasture whose elevation is at the base level of the farm. Grass from elevations just www.acmicpc.net 풀이 Bad Grass의 개수를 찾는 문제입니다. 0 이상의 숫자로 된 섬이 Bad Grass 입니다. 0보다 큰 숫자에 대..
[BOJ] 백준 1543 문서 검색 (Swift) 문제 https://www.acmicpc.net/problem/1543 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net 풀이 완전탐색으로 풀 수 있는 문제입니다. 문서의 0번째 문자열부터 검색하고 싶은 단어의 길이만큼을 하나씩 확인해줍시다. 주의할 점으로는 단어를 찾았다면, 중복되지 않게 찾아야 하므로, index를 단어의 길이만큼 늘려주어야 합니다. 소스코드 후기 완전탐색으로 쉽게 풀 수 있는 문제였습니다.
[BOJ] 백준 3085 사탕 게임 (Swift) 문제 https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 풀이 완전탐색으로 풀이할 수 있습니다. 약간 애니팡 게임과 비슷한 문제였습니다. 모든 사탕에 대해서 인접한 사탕과 교환을 해본 후, 가장 긴 연속 부분을 확인해주는 작업을 거쳐서 최대 개수를 구할 수 있습니다. 소스코드 후기 답을 쉽게 구할 수 있는데 구현하는 것이 약간 까다로웠던 문제였습니다.
[BOJ] 백준 18352 특정 거리의 도시 찾기 (Swift) 문제 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 풀이 X번 노드에서 도달할 수 있는 도시들의 최단 거리를 구해야 합니다. 간선의 비용이 모두 동일하므로 BFS를 사용해서 풀이할 수 있는 문제입니다. 저는 visited라는 Int 배열을 선언하였고, 값을 X번 노드에서의 최단 거리로 사용하였습니다. visited 배열 중 값이 k와 같은 노드를 출력시켜주었고, 없다면 ..
[BOJ] 백준 2206 벽 부수고 이동하기 (Swift) 문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 BFS로 풀이할 수 있는 문제입니다. 벽을 한 번도 안부수고 이동하는 것과, 한 번 부수고 이동하는 것을 나누어서 생각해야합니다. 벽을 부시고 그 좌표를 방문했는지, 한 번도 안부수고 방문했는지를 나타내기 위해 3차원 Bool 배열을 사용하였습니다. 벽을 안부셨다면 다음 이동할 좌표가 0이면 그냥 방문하면되고, 1이라면 벽을 부시고 방문할 수 있습니다. 벽을 한..
[BOJ] 백준 9205 맥주 마시면서 걸어가기 (Swift) 문제 https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 풀이 BFS로 풀이할 수 있는 문제입니다. 입력으로 x, y 좌표를 주기 때문에 방향을 사용하여 풀이해야 하나 헷갈릴 수 있지만 그렇지 않습니다. 단순히 상근이네 집에서 락 페스티벌의 좌표로 이동할 수 있는지 확인하는 것에 중점을 두어야 합니다. 상근이네 집, 편의점, 락 페스티벌의 좌표를 노드라고 생각하고, 노드 사이 거리가 1,000 이하라면 연결되어 있다고 생각합시다. 1,000 ..
[BOJ] 백준 2162 선분 그룹 (Swift) 문제 https://www.acmicpc.net/problem/2162 2162번: 선분 그룹 첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하 www.acmicpc.net 풀이 CCW를 사용해 선분이 교차되는지 확인하고, 유니온 파인드를 사용해 풀 수 있는 문제입니다. 입력받은 모든 선분들에 대해 교차하는지 확인을 해주어야 합니다. 교차한다면 union 연산을 실행하여 같은 부모로 넣어줍시다. 저는 숫자가 더 작은 번호가 부모로 넣어주었습니다. 모든 선분들에 대해 확인했다면, 다시 한번 find 연산을 해 최대 부모? 의 번호..
[BOJ] 백준 20149 선분 교차 3 (Swift) 문제 https://www.acmicpc.net/problem/20149 20149번: 선분 교차 3 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 풀이 https://dev-mandos.tistory.com/314 [BOJ] 백준 17387 선분 교차 2 (Swift) 문제 https://www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 풀이 https://dev-mandos.tistory.com/313 [BO..

반응형