코딩/알고리즘 - 백준
-
[백준 BOJ] 1260번 DFS와 BFS (파이썬 Python)코딩/알고리즘 - 백준 2023. 5. 30. 14:46
문제 설명 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 예제 입력 1 4 5 1 1 2 1 3 1 4 2 4 3 4 예제 출력 1 1 2 4 3 1 2 3 4 문제 풀이 알고리즘 문제풀이(1)의 그래프 단계 중 첫번째 문제. dfs는 재귀로, bfs의 queue로 구현하는 것이 일반적이라고 한다. 기본적인 개념조차 없어 답을 봐도 이해가 어려웠다. dfs는 계속 따라 내려가면 되는데, bfs는 어떻게 진행되는지 이해하기까지 시간이 좀 걸렸다. 입력 1에 따른 그래프 모양 (https://c..
-
[백준 BOJ] 17298번 오큰수 (파이썬 Python)코딩/알고리즘 - 백준 2022. 9. 6. 12:58
문제 설명 크기가 N인 수열 A = a_1, a_2, ..., a_N이 있다. 수열의 각 원소 A_i에 대해서 오큰수 NGE(i)를 구하려고 한다. A_i의 오큰수는 오른쪽에 있으면서 A_i보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다. 예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다. 예제 입력 1 4 3 5 2 7 예제 출력 1 5 7 7 -1 예제 입력 2 4 9 5 4 8 예제 출력 2 -1 8 8 -1 코드 및 풀이 2개의 ..
-
[백준 BOJ] 1158번 요세푸스 문제 (파이썬 Python)코딩/알고리즘 - 백준 2022. 8. 8. 16:23
문제 설명 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K (≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 예제 입력1 7 3 코드 및 풀이 처음에는 리스트를 이용하여 풀이를 진행했다. (아래 코드) 리스트는 더 오래걸린다는 것을 알고 있었지만 단순히 양쪽 끝 인덱스만 사용하기 때문에 혹시나 괜찮지 않을까라고 생각하였지만 시간 초과가 발생했..
-
[백준 BOJ] 1406번 에디터 (파이썬 Python)코딩/알고리즘 - 백준 2022. 7. 29. 16:53
문제 설명 첫 출에 초기 문자열(아래 예제의 경우 abcd)이 주어진다. 문자열은 영어 소문자로만 이루어져 있고, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 M(1 ≤ M ≤ 500,000)이 주어진다. 셋째 줄부터 M개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다. 예제 입력1 abcd 3 P x L P y 코드 및 풀이 import sys input = sys.stdin.readline left = list(input().rstrip()) right = [] m = int(input()) for i in range(m): command = list(input().split()) if command[0] == 'L': if left: right.append..
-
[백준 BOJ] 1874번 스택 수열 (파이썬 Python)코딩/알고리즘 - 백준 2022. 7. 18. 10:28
문제 설명 첫 출에 입력으로 들어올 n이 주어진다. 둘째 줄부터 수열을 이루는 정수가 하나씩 순서대로 주어지고, 숫자는 중복없이 한번 씩만 나온다. 예제의 경우 다음과 같이 입력이 주어진다. 8 4 3 6 8 7 5 2 1 첫 줄에 8(n)이 등장하고, 8개의 숫자가 있다. 첫 숫자는 4이고, 스택에는 오름차순으로 숫자를 push하기 때문에, 다음과 같은 연산이 실행된다. stack = [1, 2, 3, 4] push, push, push, push push 연산 후 pop 연산을 실행해, stack의 마지막 숫자인 4를 꺼내 수열을 만든다. stack = [1, 2, 3, 4] (pop) [1, 2, 3] sequence = [4] 다음 숫자는 3이기 때문에 추가적인 push 없이 한번의 pop을 실행..