본문 바로가기

알고리즘 공부 및 문제 풀이/백준(BOJ)

 (220)
[boj] 백준 1446 지름길 - 다익스트라 [문제] https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net [풀이] 다익스트라 최단 거리 문제이다. 먼저 지름길의 시작위치, 도착위치, 길이를 입력받을 때, (도착위치-시작위치)보다 지름길 전체 길이가 더 긴 경우에는 지름길의 의미가 없다. 또한 역주행이 불가능하므로 도착위치가 D를 넘어서면 안된다. 이 두가지 경우를 제외하고 벡터에 저장해준다. 그 후, 그래프를 계속 최단 거리로 갱신해준다. 예를 들어 (0, 50, 10) (50, ..
[boj] 백준 1743 음식물 피하기 - DFS [문제] https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net [풀이] DFS, BFS에 해당하는 문제이다. [코드] // Created by strit on 2022-02-06. silver1 1743 음식물 피하기 - dfs #include #include using namespace::std; int N, M, K; int board[101][101]; bool visited[101][101]; int ..
[boj] 백준 1303 전쟁 - 전투 - DFS [문제] https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net [풀이] DFS, BFS 둘 다 풀이 가능하다. [코드] #include #include #include using namespace::std; int N, M; char board[100][100]; bool visited[100][100]; int dx[] = {1, -1, 0, 0}; int dy[] = {0, 0, 1, -1}; int cnt; void d..
[boj] 백준 1342 행운의 문자열 [문제] https://www.acmicpc.net/problem/1342 1342번: 행운의 문자열 민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작 www.acmicpc.net [풀이] 문자열의 길이가 최대 10이어서 전부 확인해도 시간 내 해결이 가능하다. next_permutation 이라는 함수를 이용하는데, 이는 순열을 구하고 싶은 1-2-3-4의 배열이 있다고 가정했을 때 다음 순열인 1-2-4-3로 바뀌고 true를 반환해주는 함수이다. [코드] #include #include #include using namespace::std; int main() { ..
[boj] 백준 1389 케빈 베이컨의 6단계 법칙 [문제] https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net [풀이] BFS로 분류되어 BFS로 풀었으나 Floyd-Warshall Algorithm을 이용하는 방법도 있다고 한다. 이게 더 쉬울 것 같은데 이렇게도 한 번 풀어봐야겠다.. bfs 코드를 그대로 이용하면 되는데, 연결된 다리의 누적합을 구해서 비교해야 하므로 connect 배열에 연결 다리 수를 저장하도록 했다. [코드] #includ..
[c++] 백준 1309 동물원 - 동적계획법 [문제] https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net [풀이] dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] i번째 행에 사자를 배치하지 않는 경우, i-1행에 어떤 식으로 사자를 배치해도 상관없다. dp[i][1] = dp[i-1][0] + dp[i-1][2] i번째 행 왼쪽에 사자를 배치할 경우, i-1행에 사자를 배치하지 않거나 오른쪽에만 배치해야 한다. dp[i][2] = dp[i-1][0] + dp[i-1][1] i번째 행 오른쪽에 사자를 배치할 경우, i-1행에 사자를 배치하지 않거나 왼쪽에만 배치해야 한다. [코드] #in..
[c++] 백준 1263 시간 관리 - 그리디 [문제] https://www.acmicpc.net/problem/1263 1263번: 시간 관리 진영이는 캠프 조교를 온 후 효율적으로 시간 관리를 해야 한다는 것을 깨달았다. 진영이는 하루에 해야 할 일이 총 N개가 있고 이 일들을 편하게 1번부터 N번까지 차례대로 번호를 붙였다. 진영 www.acmicpc.net [풀이] 그리디 알고리즘. 가장 늦게 끝내도 되는 시간 순으로 내림차순 정렬을 한다. 그 후 끝내야 하는 시간이 더 작으면 계속 갱신해준다. 예를 들어, 아래 테이블의 경우 가장 늦은 시간은 20시이다. 3 5 8 14 5 20 1 16 해당 일은 5시간이 걸리므로 20-5=15, 즉 적어도 15시에는 시작해야 한다. 만약 그 전 일인 16시까지 끝내야 하는 일을딱 16시에 맞춰서 끝냈다면..
[c++] 백준 1254 팰린드롬 만들기 - 투포인터 [문제] https://www.acmicpc.net/problem/1254 1254번: 팰린드롬 만들기 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. 동호는 www.acmicpc.net [풀이] 문제를 잘 읽자....문자열 뒤에만 추가할 수 있단다. 그걸 못보고 insert로 중간 삽입해서 풀다가 왜 계속 틀리는 거지??? 멘붕 왔는데...뻘짓했다... 먼저 맨 처음 문자부터 맨 마지막까지 팰린드롬이 되는지를 확인하고 팰린드롬이 되는 첫번째 인덱스를 찾는다. 그럼 전체 문자열 길이+팰린드롬이 되는 첫번째 인덱스 값이 답이 된다. 예를 들어, aabcaa의 경우 마지막 aa만 ..

티스토리툴바