알고리즘/백준 문제풀이 (38) 썸네일형 리스트형 백준 - 1697(숨바꼭질, 자바) 문제 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 접근 출력할 값 : 두 위치 N과 K에서 N이 +1, -1, *2의 연산을 활용해 K에 도달하는 방법의 최소 횟수 BFS로 만들 수 있는 모든 경우를 구해가며 K와 같아지면 리턴 DFS vs BFS 만약 dfs로 모든 수를 다 만드려면 +1로 만들 수 있는 수를 모두 만들고 거기서 리턴해서 -1을 추가해 만들 수 있는 수를 모두 만들고 거기서 리턴해서 *2를 .. 백준 - 14502(연구소, 파이썬) https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 이해 N * M 크기의 연구소에 바이러스가 퍼진다. 이때 벽을 3개 세워 안전구역을 최대한 많이 확보할 때 안전구역의 최대값을 구하는 문제 2는 바이러스, 1은 벽, 0은 빈칸을 의미한다. 제한사항은 3 ≤ N, M ≤ 8 이다. 문제 접근 문제를 이해하고 난뒤 두 가지의 알고리즘을 떠올렸다. 먼저 바이러스를 퍼지게하고 안전 구역의 개수를 구하기 위해 bfs를 통해 바이러스를 퍼뜨리게한다. 문제 조건에서.. 백준 - 15650(N과M(1), 파이썬) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 접근 백트래킹을 연습하기위해 n과 m 시리즈를 풀어보기로 했다. 함수내에서 반복문으로 이미 추가한 원소와 중복되지않을시 원소를 추가하고 재귀를 돌리는식으로 구현했다. 정답 코드 n, m = map(int, input().split()) s = [] def dfs(): if len(s) == m: print(' '.join(map(str, s))) return for i in range(1,.. 백준 - 1182(부분 수열의 합, 파이썬) https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 접근 문제를 보자마자 아 이거 재귀함수로 다 해보면 되겠는데? 라는 생각이 들었다. 재귀함수의 리턴하는 성질을 이용하면 모든 경우의 수를 구할 수 있다는건 코테 문제 쫌 풀어본 사람이면 알 것이다. 근데 뭐지..정답이 12퍼센트에서 틀렸습니다가 나왔다. 일단 정답 코드 n, s = map(int, input().split()) numbers = list(m.. 백준 - 1021(회전하는 큐, 파이썬) https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 문제 접근 큐를 최소한으로 회전시키며 값을 추출하는 문제 다행히 파이썬에는 큐를 회전시키는 rotate 함수가 있어서 편하게 구현 어떤 기준에 따라 오른쪽, 왼쪽으로 회전시킬지만 정해주면 될듯 처음에는 구하려는 값이 오른쪽 끝과 가까운지 왼쪽 끝과 가까운지를 판단해 큐를 회전시키려 했다. from collections import deque n, m = map(int, input().split.. 백준 - 5568(카드 놓기, python) https://www.acmicpc.net/problem/5568 5568번: 카드 놓기 예제 1의 경우 상근이는 11, 12, 21, 112, 121, 122, 212를 만들 수 있다. www.acmicpc.net 문제 풀이 n개의 카드 중에서 k개를 선택하여 그 수를 나열해 만들 수 있는 수의 개수를 구하는 문제 재귀를 이용해 만들 수 있는 수를 만들고 set에 저장해 중복을 제거해주면 되겠다 판단함 다만 재귀를 구현하던 중 코드가 꼬여서 다른사람의 풀이를 보았음..구현력 이슈 정답 코드(1) # n개 중에서 k개를 선택하여 만들 수 있는 정수의 개수 n = int(input()) k = int(input()) numbers = [] for _ in range(n): numbers.append(inp.. 백준 - 15736(청기 백기, 파이썬) https://www.acmicpc.net/problem/15736 15736번: 청기 백기 예제 입력 1의 경우 1, 2, 3번 깃발이 존재하고, 3명의 선수가 참가한다. 첫 번째 선수는 1의 배수의 번호를 가진 깃발을 뒤집는다. 초기에 청색이였던 깃발은 첫 번째 선수에 의해 모두 백기로 된 www.acmicpc.net 문제 접근 문제 자체는 매우 간단하지만 입력 값이 높아 규칙을 발견해서 시간 초과를 해결하는 문제 초과나는 코드 # 초기의 깃발은 모두 청색? # 1. 일단 완전탐색으로 구현해보기 -> 시간초과 날것임 n = int(input()) # 0은 청, 백은 1 flag = [0] * (n+1) flag [0] = 10 for i in range(1, n+1): for j in range(i,.. 백준 - 3085(사탕 게임, 파이썬) https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 문제 접근 완전탐색으로 하나씩 교환해주며 개수를 센다. 상하좌우 다 교환할 필요없이 오른쪽과 아래쪽만 교환하면 된다. # 로직은 맞는데 구현을 실패함 # 다른사람이 구현한 것 참조 import sys input = sys.stdin.readline n = int(input()) board = [list(input()) for _ in range(n)] maxCnt = 0 # 행렬을 검사하여 최대값을 갱신하는 함수 def check(): global maxCnt for i in range(n): # 행을 검사 cnt.. 이전 1 2 3 4 5 다음
