본문 바로가기

전체 글

[백준] 1337번: 올바른 배열 (C++) https://www.acmicpc.net/problem/1337 최근 c++을 공부하고 있어서 c++로 풀어봤다. 문제에서 배열 속에 원소 중에 5개가 연속인 배열을 올바른 배열이라고 했을 때, 주어진 배열이 올바른 배열이 되기 위해 추가되어야 할 원소의 최소 개수를 출력하는 문제였다. 예를 들어,배열이 [5,6,7] 이면 3,4나 8,9만 추가하면 되므로 답은 2다.문제는 배열이 [5,7,9,8492,8493,192398] 같은 경우다.5 7 9 사이에 6,8만 채우면 되므로 답은 2이다. 처음엔 첫번 째 케이스만 보고 for문으로 돌면서 다음 원소가 이번 원소보다 1크면 count를 증가시키면서 나가려고 생각했는데 5 7 9 같은 경우는 그런 것이 불가능했다. 곰곰히 생각하다가 좋은 생각이 났다.f.. 더보기
[백준] 15654번: N과 M(5) (파이썬) https://www.acmicpc.net/problem/15654 이번엔 직접 입력받은 값으로 순열을 만드는 문제였다.백트래킹을 진행하는데, result에 arr의 i번 째 값이 없다면 추가하면 된다.n,m = map(int,input().split())arr = list(map(int,input().split()))arr.sort()result = []def back(): length = len(result) if length == m: for num in result: print(num, end=' ') print() return for i in range(n): if arr[i] not in result:.. 더보기
[백준] 15662번: N과 M(4) (파이썬) https://www.acmicpc.net/problem/15652 어제 풀었던 N과 M (1), (2) 번에서 조건만 조금 바꾸면 바로 풀어지는 문제였다.전에 나왔던 것 보다 같거나 크기만 하면 된다.만약 result가 비어있다면 그냥 append 한다.n,m = map(int,input().split())result = []def back(): length = len(result) if length == m: for num in result: print(num, end=' ') print() return for i in range(1,n+1): if result == []: result.a.. 더보기
[백준] 15649번: N과M(1), 15650번 N과M(2) (파이썬) https://www.acmicpc.net/problem/15649문제를 보고, 이건 DFS로 풀어야겠는데? 라는 생각이 들었다. 문제 유형을 보니 '백트래킹'??처음보는 문제 유형이었다.무작정 문제를 풀 수는 없으니, 백트래킹이 무슨 유형인지 찾아봤다. 🐳 백트래킹이란?백트래킹이란 현재 상태에서 가능한 모든 경로를 따라 들어가 탐색하는 방법이다.원하는 값이 아닐 경우 더 이상 탐색을 진행하지 않고 전 단계로 back해서 돌아가는 방법으로 이름 그대로 backtracking 알고리즘이다. 백트래킹은 DFS와 모두 탐색 알고리즘이어서 같은 유형의 문제는 두 방법으로도 모두 해결가능하다고 하다!하지만 성능면에서는 백트래킹이 DFS보다 뛰어나다고 한다.DFS는 트리의 바닥까지 모두 탐색해야하지만, 백트래킹은.. 더보기
[백준] 7662번: 이중 우선순위 큐(파이썬) https://www.acmicpc.net/problem/7662 우선순위 큐를 응용해서 푸는 문제였다.heapq를 사용하여 구현하려고 했다. import heapqt = int(input())for _ in range(t): k = int(input()) dup = [] # 공용 리스트 min_heap = [] # 최소힙 max_heap = [] # 최대힙 # k번 만큼 명령 실행 for i in range(k): cmd, num = map(str, input().split()) num = int(num) cnt = 0 flag = True # 추가 if cmd == "I": .. 더보기
[백준] 9019번: DSLR (파이썬) https://www.acmicpc.net/problem/9019 문제를 보고, 이 문제도 BFS로 풀 수 있겠다. 라고 생각하고 BFS로 풀어나갔다.시간 제한이 6초여서 모든 경우의 수를 queue에 넣어가도 괜찮을 거라고 생각했다. from collections import dequet = int(input())def bfs(a,b): queue = deque([(a,"")]) cnt = 0 visited = [False] * 10000 visited[int(a)] = True while True: length = len(queue) for _ in range(length): da, cmd = queue.popleft() .. 더보기
[백준] 14500번: 테트로미노 (파이썬) https://www.acmicpc.net/problem/14500 문제를 읽고, BFS가 먼저 생각났다.from collections import dequen,m = map(int,input().split())graph = [ list(map(int,input().split())) for _ in range(n)]#방향dx = [1, 0, -1, 0]dy = [0, -1, 0, 1]4방향을 탐색해야 하므로, 방향 리스트를 만들어 준다.result = 0for i in range(n): for j in range(m): score = search(i,j) result = max(result, score)print(result)모든 좌표에서 나올 수 있는 점수중에 가장 큰 점.. 더보기
[백준] 16928번: 뱀과 사다리 게임 (파이썬) https://www.acmicpc.net/problem/16928 BFS 문제였다.queue에 주사위를 한 번 던질 때 갈 수 있는 모든 칸을 queue에 저장하고 만약 만약 queue에 100이 들어오면 while문을 멈춘다.from collections import dequen,m = map(int,input().split())# 사다리ladder = dict()for i in range(n): x,y = map(int,input().split()) ladder[x] = y#뱀snake = dict()for i in range(m): x,y = map(int,input().split()) snake[x] = y#방문 리스트graph = [0] * 101queue = deque(.. 더보기

티스토리툴바