•알고리즘(Algorithm )/문제풀이

[백준-1966] 프린터 큐 파이썬

# 문제 # 풀이 일반적인 큐의 정책에 따라서 pop되어야 하는 원소를 기준으로 그 뒤의 원소들 중 큰 값이 있다면 큐의 맨뒤에 줄을 세우는 과정을 반복하면 된다. 그러나 출력해야하는 문서의 초기 인덱스 값인 M 큐가 계속해서 update됨에따라서 인덱스 번호가 바뀐다. 이 것을 해결하는 것이 문제를 푸는 가장 중요한 포인트라고 생각했다. M이 맨앞에오는 시점(인덱스가 0일때) 즉 출력되어야하는지 맨 뒤로 가야하는지를 결정하는 시점또한 중요 포인트다. # 실패한 풀이 def unsolve(n): result = [] for _ in range(n): cnt = 0 N,M = list(map(int, sys.stdin.readline().strip().split())) data = list(map(int,..

[백준-1874] 스택 수열 파이썬

# 문제 # 풀이 1~N까지의 숫자를 차례대로 스택에 push 또는 pop하여 수열을 만들 수 있는지 확인하는 문제였다. 주어진 수가 현재 스택에 넣어진 수가 아닌지 확인하며 주어진 수까지는 스택에 꾸준히 push시킨다. 핵심 포인트는 pop을 하는 상황인데, pop은 무조건 스택의 최상위의 숫자만 할 수 있기때문에 해당 조건을 통해서 검사해야한다. # 실패한 풀이 import sys PLUS = "+" MINUS = "-" # 실패 코드 def get_top(stack): stack_len = len(stack) if stack_len == 0: return 0 return stack[stack_len-1] def get_start(stack): if len(stack) == 0 : return 0 r..

[백준-2798] 블랙잭 파이썬, 3중 반복문 사용

# 문제 # 풀이 문제를 너무 어렵게 생각했다. 알고리즘 공부를 막 시작한터라 시간복잡도에 얽매이면서 뭔가 코드를 가장 효율적이게 짜야한다는 생각에 휩싸였다. ## 실패한 풀이1 맨 처음에는 백트래킹방법으로 조건에 맞는 가지치기를 하려고 했다. 이것도 틀린 풀이가 될 것 같지는 않았는데, 어제 공부했던 백트래킹인데 막상 구현하려니 헷갈려서 다른 방법을 찾아보려고 했다. ## 실패한 풀이2 이번엔 3중 반복문을 사용하면서 비교하도록 했다. 결국에 이렇게 푸는게 정답이었는데, 나의 뭔지 모르는 자신감이 정답을 산으로 가게 만들었다. 나름 효율성을 생각한다고.. 가장 큰값 하나는 무조건적으로 선택 될 것이라는 말도 안되는 생각이 [예제 입력2] 케이스를 넘지 못하게 했다. 풀면서 생각해보니까 정말 어디서 나온..

[백준-2920] 음계 파이썬, 오름차순 내림차순 판단하기

# 문제 # 풀이 입력조건이 너무 깔끔하기 때문에 여러 경우의 수를 생각할 필요는 없었다. 또한 8개만 입력이 들어오기 때문에 시간복잡도에대한 생각을 하지 않아도 됐다. 오름차순 경우의 수와 내림차순 경우의 수는 8개의 음계를 정렬, 리버스정렬로 리스트를 재생성하고, 비교해주는 풀이방법을 사용했다. # 다른 풀이 전략 그러나 입력이 이렇게 깔끔하지 않는 문제가 존재할 것이고 데이터가 많아진다면 상당히 비효율적인 방법이 될 것이다. 오름차순과 내림차순은 간단하게 앞-뒤 두개의 데이터쌍만을 비교하면 되기 때문에 반복문을 이용해서 두개의 데이터를 비교해 나가면 더욱 효과적일 것이다. 내림차순 Flag와 오름차순 Flag를 각각 만들고 조건에 맞지 않는다면 해당 Flag를 Flase로 바꿔준다. 이후 두개의 플..

[백준-9663] N-Queen 파이썬, 백트랙킹, 파이썬 전역변수, enumerate

# 문제 # 풀이 백트래킹기법을 사용하여 문제를 풀었다. 기존 탐색이나 반복문으로 풀게 되면 중간에 퀸을 놓을 수 없는 경우에도 그 다음에 대한 탐색을 실시할 것이다. 그렇기 때문에 중간에 이미 틀린 길이라면 이 후 반복을 중지하고 그 뒤로 돌아가야한다. 그렇게 하기 위해 백트래킹 기법을 사용해서 문제를 풀었다. 첫 행의 열들은 각각의 시작점이 된다. 그 기점으로 시작해서 가지가 뻗어나가기 때문에 시작위치를 지정해주었다. 이후 dfs를 이용해서 재귀함수로 다시 호출해나가는 방법으로 문제를 풀었다. for candidate_col in range(N): if is_available(cur_row, candidate_col, upper_queen_info): upper_queen_info.append(can..

[백준-11399] ATM 파이썬, 탐욕알고리즘을 이용한 최적해 찾기

# 문제 # 풀이 탐욕 알고리즘(Greedy Algorithim)을 이용해서 최적해를 구하는 방법의 문제라고 생각했다. 탐욕 알고리즘은 현재 상황이 가장 최적이라고 생각하고 문제를 풀어나가는 방법인데, 항상 최적의 해를 구하는 것은 아니다. 때때로는 근사한 값을 구할 수 있다. 위와 같이 6이 최적이라고 판단했지만 사실은 17->23으로 가는 것이 더 최대값을 구할 수 있는 경우가 생기기 때문이다. 이번 문제에서는 위와 같은 경우는 고려하지 않았도 됐기 때문에 그냥 풀었다. for문을 두 번 돌려서 풀면 당연히 편하겠지만 시간복잡도가 O(n^2)으로 늘어나기 때문에 O(n)으로 풀 수 있는 방법이 있을까 고민했고 아래와 같이 반복문을 한번만 돌려서 정답을 구 할 수 있었다. # 코드 import sys ..