Junior-Developer

1일 1커밋! 1일 1 백준!

문제풀이/백준oj

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 풀이 BFS를 이용하였다. BFS를 이용해서 처음 입력받은 수를 각각 D,S,L,R 을 시행했을때, 변환된 숫자가 한번도 나오지 않은 숫자라면, 큐에 추가해주며 최단거리로 바꿔야 하는 숫자에 도달했을때, 그 바뀐 로그를 출력해주면 된다. 시간복잡도 BFS알고리즘이므로, 최악으로 0~10000까지 모두 탐색을 해서 맞추는것이므로, O(1)이 된다. 코드 #include #include ..

2021. 8. 13.

문제풀이/백준oj

https://www.acmicpc.net/problem/14476 14476번: 최대공약수 하나 빼기 첫째 줄에 정수의 개수 N (4 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 N개의 수가 주어진다. 각각의 수는 20억을 넘지 않는 자연수이다. www.acmicpc.net 풀이 먼저, 유클리드 호제법과 누적합의 개념을 이용하여 풀었다. 유클리드 호제법에 대해선 아래에 설명을 해놓았다. https://khu98.tistory.com/229 [알고리즘] 최소공배수와 최대공약수 C++ 0. 목차 최대공약수(Greatest Common Divisior) 의 개념 최대공약수 알고리즘 1 (시간복잡도 O( min(A ,B) ) ) 최대공약수 알고리즘 유클리드 호제법 (시간복잡도 O(lo..

2021. 8. 12.

문제풀이/백준oj

https://www.acmicpc.net/problem/9079 9079번: 동전 게임 입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 세 줄로 이루어지며, 한 줄에 세 개의 동전모양이 주어지는데, 각각의 동전 표시 사이에는 하나의 공백이 www.acmicpc.net 풀이 BFS알고리즘을 이용하여 문제를 해결했다. BFS를 이용할때, 이전에 만났던 동전들의 상태를 체크해주기위해, 먼저 입력받은 동전들을 H는1로, T는 0으로 초기화를 시켜준 뒤, 해당 배열을 이진수로 나타내어 해당 상태를 체크해주었다. 예시 1번을 예를들어 설명해보자면, 처음 입력했을때 다음과 같이 초기화를 해준다. H T T1 0 0 H T T => 1 0 0 T H H0 1 1 그런뒤..

2021. 8. 11.

문제풀이/백준oj

https://www.acmicpc.net/problem/16400 16400번: 소수 화폐 구매하려고하는 물건의 값 N(2 ≤ N ≤ 40,000, N은 정수)이 주어진다. www.acmicpc.net 풀이 이 문제를 풀기전에 동전문제를 풀고오면 쉽다. 왜냐면 경우의수를 구하는 알고리즘이 같기때문이다. https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 소수판별 알고리즘과 DP를 혼용하여 문제를 해결하였다. 하지만 N값이 최대 40000이기때문에,..

2021. 8. 10.

문제풀이/백준oj

https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 풀이 DP가 없는 LCA(Lowest Common Ancestor) 알고리즘을 이용하여 문제를 해결했다. N값이 10000으로 작기때문에 DP없이 올라가더라도 시간안에 들었다. 먼저, 처음 세팅으로 모든 노드의 깊이를 0으로, 부모를 자기 자신으로 셋팅을 해준다. 그런뒤 입력을 모두 받고, 트리를 만들어 주며 부모-자식 관계를 저장해주었다. 다음..

2021. 8. 9.

문제풀이/백준oj

https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 풀이- 간단한 BFS문제이다. 다만 1초일때의 불의움직임과 사람의 움직임, 2초일때의 불의움직임과 사람의 움직임을 맞춰서 탐색해야는것을 주의해주면 된다. 코드 #include #include #include #include #include using namespace std; char maze[1000][1000]; int mv[4][2] = { {1,0},{-1,0},{0,1},{0,-1} }; pair s..

2021. 8. 8.

문제풀이/백준oj

https://www.acmicpc.net/problem/8972 8972번: 미친 아두이노 요즘 종수는 아두이노를 이용해 "Robots"이라는 게임을 만들었다. 종수는 아두이노 한대를 조정하며, 미친 아두이노를 피해다녀야 한다. 미친 아두이노는 종수의 아두이노를 향해 점점 다가온다. www.acmicpc.net 풀이 문제에 제시된 조건들을 유의해주면서 시뮬레이션을 해주면 된다. 이때 , 미친 아두이노가 동시에 움직인다는것을 고려해주어야 해서, 모두 움직인 뒤 , 한번에 아두이노를 터트리고 살려야 한다. 시간복잡도 종우가 움직이는 방향의 길이를 S, 가로 세로의 길이를 C,R라고 한다면, O(RCS)가 된다. 코드 #include #include #include #include #include #incl..

2021. 8. 6.

문제풀이/백준oj

https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net -풀이- 간단한 BFS이다. 주의할점만 생각해주면 구현이 복잡하진 않다. 1. 구슬을 굴리고 난 뒤, 빨간공과 파란공이 겹치면 조정이 필요하다. 1-1 밑으로 내려가는 방향이였을때 겹치면, 더 위에있던공의 i좌표 -1 1-2 위로 올라가는 방향이였을때 겹치면, 더 아래있던공의 i좌표 +1 1-3 오른쪽으로 가는 방향이였을때 겹치면, 더 왼쪽에있던 ..

2021. 8. 5.