알고리즘/백준

https://www.acmicpc.net/problem/9935 스택을 활용하면 되는 문제다.폭발 문자열에 해당하는 문자열이 스택의 탑에 오는 경우에 pop해버리면 된다.  첫 풀이import sysinput = sys.stdin.readlineword = input().rstrip()bomb = input().rstrip()len_word = len(word)while True: word = word.replace(bomb, '') if len_word == len(word): break else: len_word = len(word)if word == '': print('FRULA')else: print(word) 처음에는 replace를 사용해서..

https://www.acmicpc.net/problem/1406  스택 혹은 큐를 활용해서 풀면 되는 문제.커서를 기준으로 left, right 두 스택 혹은 큐로 나눠서 로직을 구현하면 된다.  처음에는 스택을 활용해서 풀었다.import sysinput = sys.stdin.readlineleft = list(input().rstrip())right = []n = int(input()) # 명령 개수for _ in range(n): command = input().rstrip() if command == 'L': if left: char = left.pop() right.append(char) elif command == 'D': ..

https://www.acmicpc.net/problem/10799 스택을 활용하는 문제다. # 10799번: 쇠막대기import sysinput = sys.stdin.readlinearr = list(input())stack = [arr[0]]cnt = 0 # 잘려진 쇠막대기 조각의 총 개수for i in range(1, len(arr)): check = arr[i] # 만약 현재 넣으려는 괄호가 '('인 경우에는 stack에 집어 넣는다. if check == '(': stack.append(check) # 만약 현재 넣으려는 괄호가 ')'인 경우에는 더 구체적으로 확인한다. elif check == ')': stack.pop() # stack에는 ..

https://www.acmicpc.net/problem/1461 그리디 문제다.처음 문제를 보고, 음수와 양수를 나눠서 풀어야겠다는 생각이 들었다.그리고, 음수, 양수 중 절댓값이 큰 수에 마지막으로 도착하도록 해야겠다는 생각도 해냈다.왜냐하면 갔다가 다시 책을 가지기 위해 원점으로 돌아와야 하는데, 가장 큰 값에 도착했다가 다시 돌아온다면절대 최솟값이 될 수 없기 때문이다. 이런 아이디어는 어떻게든 생각해내니 거의 1시간이 지나있었다.구현해보다가 잘 안되어서 결국 풀이를 약간 참고해서 풀었다. # 1461번: 도서관# 음수와 양수를 나눠서 계산한다.import sysinput = sys.stdin.readlinen, m = map(int, input().split())arr = list(map(int..

https://www.acmicpc.net/problem/1689 그리디 문제다.여러 선분의 시작점과 끝점이 주어졌을 때, 겹치는 선분의 최대 개수를 출력하는 문제다. 처음에는 각 선분의 좌표가 .5를 지나가는 경우 1을 더해주는 방식으로 구해보려고 했다.예를 들어 선분의 시작점, 끝점 좌표가 (3, 6)인 경우에는 3.5, 4.5, 5.5를 지나가는 것이다.그러므로 리스트를 선언해 전체 좌표에 대해 지나가는 선분의 개수를 저장하려고 해봤는데,생각해보니 선분의 개수가 100만개이고, 선분의 좌표의 절댓값이 10억 이하이므로 무조건 시간초과가 나기 때문에 구현하지 않았다. 그 다음 아이디어로, 입력받은 좌표들을 정렬한 후에, 조건을 넣어줘서 선분 개수의 최댓값을 갱신해주면 되지 않을까?라는 생각이 들어서 ..

https://www.acmicpc.net/problem/1946 이번에도 그리디 문제다.바로 전 문제인 회의실 배정 문제와 거의 비슷한 문제라고 볼 수 있다. 그리고 문제 설명이 살짝 헷갈렸던 문제기도 하다.지원자의 (서류심사 성적, 면접시험 성적)이 주어지는데, 둘 중 적어도 하나가 다른 지원자보다 떨어지지 않는 사람만이 선발 될 수 있다.즉, A라는 인원의 (서류심사 성적, 면접시험 성적)이 임의의 인원 B의 (서류심사 성적, 면접시험 성적)보다 둘 다 떨어지는 경우가 하나라도 있다면, A는 뽑힐 수가 없는 것이다. 결국 정렬이 필요하다.문제를 풀다 보니 그리디는 정렬과 항상 붙어 있는 느낌이다. 서류심사 성적 기준으로 오름차순 정렬한다.그리고  면접시험 성적을 반복문을 돌면서 비교하면 된다. 만약..

https://www.acmicpc.net/problem/1931 그리디 문제다. 그리디 문제는 주로 정렬과 관련되어 있다.이 문제도 N이 최대 10만이고, 시간 제한은 2초이므로 O(NlogN)까지 가능하다. 회의를 최대한 많이 넣어야 한다.그러므로, 회의의 종료시간을 기준으로 오름차순 정렬한다. 그리고 여기서 주의할 점은, 두번째 정렬 기준으로 회의의 시작시간 기준으로 오름차순 정렬해야한다는 것이다.왜냐하면 이런 경우 때문이다. 예를 들어6 1013 1312 1311 13이렇게 회의 시간이 있다고 해보자.만약, 회의의 종료시간만을 기준으로 오름차순 정렬했다면, 반복문을 돌며 들어가는 회의는(6, 10) - (13, 13)이 될 것이다.하지만, 이렇게 회의를 넣으면, 회의의 최대개수가 나오지 않는다.(..

https://www.acmicpc.net/problem/1926   DFS  # 1926번: 그림(DFS)import syssys.setrecursionlimit(10**6)cnt = 0 # 그림의 개수max_area = 0 # 가장 넓은 그림의 넓이n, m = map(int, input().split())visited = [[False]* m for _ in range(n)]arr = []for _ in range(n): arr.append(list(map(int, input().split())))dx = [0, 0, 1, -1]dy = [1, -1, 0 , 0]def dfs(x, y): visited[x][y] = True global area for i in range(4):..

9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 대표적인 백트래킹 문제다. 퀸을 2차원 리스트 체스판에 놓을 수 있는 경우는 다음과 같다. 1. 이전까지 놓은 퀸들이 같은 행에 없는 경우 2. 현재 놓으려는 퀸의 이전 대각선에 퀸이 위치하지 않는 경우 그래서 1번, 2번 조건을 각각 만들어줬다. # 9663번: N-Queen n = int(input()) visited = [[False] * (n+2) for _ in range(n+2)] visited_row = [False] * (n+2) # 1~n번 행에 퀸이 놓였는지 ..

16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 백트래킹 문제다. 계란으로 계란을 쳐서 최대 몇 개의 계란을 깰 수 있는지 맞추는 문제다. 조건은 다음과 같다. 일렬로 놓여 있는 n개의 계란에 대해 왼쪽부터 차례대로 들어서 한 번씩만 다른 계란을 쳐 최대한 많은 계란을 깨면 된다. 1. 가장 왼쪽의 계란을 든다. 2. 손에 들고 있는 계란으로 깨지지 않은 다른 계란 중 하나를 친다. 단, 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다. 이후 손에 든 계란을 원래 자리..