우당탕탕 감자 바보의 바보 탈출기

BFS 방문 처리 BFS의 방문 처리는 방문을 한 곳을 체크하는 것이 아니라 방문할 예정인 곳을 체크하는 방식이다. BFS를 풀 때 Queue를 보통 사용하게 되는데, 방문 체크를 Queue에서 데이터를 뽑을 때 방문 체크를 하는 것이 아닌, Queue에 집어넣을 때 방문체크를 하게 된다. 방문 한 곳을 체크한 경우, 방문 하진 않았지만 방문할 예정인 곳을 다른 곳에서도 접근 가능할 때 반복해서 탐색하는 경우가 생길 수 있다. 하지만 방문할 예정일 때 이를 체크한다면 이런 경우를 없앨 수 있다. 따라서 방문 한 곳 을 체크한다는 말은 틀린 말이고 방문 할 곳 을 체크하는 것이 적절한 말이다. 예제

공부/알고리즘 2023. 3. 9. 22:40

[알고리즘/브루트포스/JAVA] 백준 1107 - 리모컨 문제: 백준 1107 - 리모컨 문제 : https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 사용언어 : JAVA 시간제한 : 2초 메모리 제한 : 256 MB 문제 설명 초기 채널 번호 : 100 입력 맞추려는 채널 번호 : N (0 ≤ N ≤ 500,000) 망가진 숫자 번호 개수 : M (0 ≤ M ≤ 10) 입력 셋 째 줄 : 고장난 버튼들 M개(띄어쓰기로 구분) +,..

공부/알고리즘 2023. 3. 6. 23:12

[알고리즘/DP/JAVA] 백준 2193 - 이친수 문제 : 백준 2193 - 이친수 문제 : https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 사용언어 : JAVA 시간제한 : 2초 메모리 제한 : 128 MB 문제 설명 이진수 숫자 중 아래 성질을 만족하는 수들을 이친수라고 한다. 이친수 조건 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 숫자 n이 주..

공부/알고리즘 2022. 7. 24. 12:03

문제 : 2747번: 피보나치 수 (acmicpc.net) 2747번: 피보나치 수 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 사용언어 : Python 3 시간제한 : 1초 메모리 제한 : 128 MB 문제 설명 n 번째 피보나치 수를 구하는 문제이다. 피보나치 수의 0과 1번째 피보나치 수는 각각 0과 1이다. 이후 n번째(n>1) 피보나치 수는 바로 앞 두 피보나치 수의 합이 된다. $F_{n} = F_{n-1} + F_{n-2}$ (n > 1) 입력 첫째 줄에 n이 주어진다. n은 45보다 ..

공부/알고리즘 2022. 3. 16. 23:49

문제 : 10989번: 수 정렬하기 3 (acmicpc.net) 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 사용언어 : Python 3 시간제한 : 5초 메모리 제한 : 8 MB 문제 설명 수의 범위가 제한적이나 많은 수의 데이터를 정렬하는 문제이다. 제한 시간 내에 정렬을 수행 완료해야 한다. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 예제 입력 10 5 2 3 1 4 2 3 5 1 7 출력 첫째..

공부/알고리즘 2022. 3. 16. 18:16

문제 : 4195번: 친구 네트워크 (acmicpc.net) 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 사용언어 : Python3 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다. 예제 입력 2 3 Fred Barn..

공부/알고리즘 2022. 3. 12. 18:39