본문 바로가기

코딩테스트_백준풀이54

경로찾기 #11403 c++ 풀이 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 유난히도 이해가 잘 안됐던 문제 단어에 꽂히면 문제가 잘 안풀리는 것 같다. i->j 로 갈수 있는지 단방향 그래프에 관해서 묻는 문제였다. 따라서 최근 bfs문제를 많이 풀어서 그런지 bfs 알고리즘으로 접근하였다 문제 카테고리는 플로이드 워셜 알고리즘이라고 표시가 되어있긴 했다. bfs로 순회시키고, 방문했던 경로를 저장한 visited 배열을 다시 순회하여, 해당 정점부터 표시된 곳까지 1로 칠해주면 된다. #inclu.. 2023. 10. 27.
DSLR #9019 c++ 풀이 ㅁhttps://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 코드 #include #include #include #include #include #include #include using namespace std; //int Graph[101][101]; int visited[10001]; //int Board[1001][1001]; int A, B; int N, M; void bfs() { //cout > B; memset(visited,.. 2023. 10. 26.
숨바꼭질 #1697 c++ 풀이 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net n에서 k로 가는 최단경로는 BFS를 사용하여 구현할 수 있다. 문제는, N에서 K까지 도달하는데 총 몇번 걸렸어? 이다. 이동할때마다 누적해줘야한다. 노드마다 최단거리를 구할수 있다. 조금 달랐던 점은 그래프를 초기화하지 않고 그냥 이어져 있다고 가정하는 것이다. #include #include #include #include #include #include using.. 2023. 10. 26.
리모컨 #1107 c++ 풀이 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 www.acmicpc.net 브루트 포스 2초 2억번 계산에 맞게 알고리즘 짜기가 생각보다 만만치 않았던 문제 0. 0인 경우 0. 1. 처음부터 +,-로만 이동하는 경우와 비교 2. 어디까지 이동한 다음 + 혹은 -로 이동하는 경우와 비교 2.1. 어디까지 이동이라는 것은 고장나지 않은 숫자로 만들수 있는 모든 숫자를 의미(brute force) 2.2. 그런 다음 abs(이동한 수 - target)을 숫.. 2023. 10. 24.

티스토리툴바