Archive

www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 풀이 DFS를 사용하는 문제 모든 경우의수를 다 시도해봄. max_val, board를 글로벌 변수로 두고 사용. 해당 위치에서 숫자가 바뀌었는지 안바뀌었는지 정보도 저장해야함. 4, 4, 4, 4 -> 오른쪽으로 -> 0, 0, 8, 8이 되어야함 (cf. 0, 0, 8, 8에서 0, 0, 0, 16이 되면 안됨.) # 입력 받음 n = int(input()) board = [li..

www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 풀이 BFS를 사용하는 문제 4가지(위쪽, 오른쪽, 아래쪽, 왼쪽)에 대해 빨간공, 파란공이 움직인 결과, 이동 거리 정보가 필요 움직일때 격자 밖으로 벗어나지 않고, '#'이 아니고, 현재 위치가 'O'이 아니면 해당 방향으로 한칸씩 계속 이동 이동했는데, 빨간공, 파란공이 겹칠 때 이동거리를 기준으로 위치를 다시 조정해줌 # 입력 받기 n, m = map(i..

www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 풀이 메모이제이션 문제 0, 1의 개수 정보를 글로벌 변수로 선언해 입력값 들어왔을 때 기존에 계산한 정보 있으면 바로 리턴해줌. 그리고 계산정보 없을경우 이전 개수 정보를 기반으로 최소한의 계산만 수행해 시간을 단축 # global 변수로 0, 1 카운트 정보 놔둠 zero = [1, 0] one = [0, 1] def solution(n): # 입력값 n이 이전 정보에 있을 경우 -> 바로 값을 리턴함.(중복계산 방지) if n

www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 풀이 DFS문제. 처음 시작노드 -> 방문안한노드를 방문 -> 방문한 노드를 마주치면 while문 밖으로 처음 시작노드 = 최종 도착노드일 경우(cycle) count 변수 +1해줌. def solution(): n = int(input()) lst = [0] + list(map(int, input().split())) cnt = 0 vi..

www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 queue를 사용한 BFS문제. def solution(M, N, m): rs = 0 visited = [[False for _ in range(N)] for _ in range(M)] queue = [[0, 0]] m[0][0] = 1 # 상, 하, 좌, 우 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] while queue: x, y = queue.pop(0) for idx in range(4): next_x =..

www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 풀이 queue를 사용한 DFS문제. visited 2차원 리스트를 만들어 방문했는지 여부를 저장 첫 시작점 방문 -> DFS로 갈수 있는 모든 점 방문 방문하면서 visited를 업데이트 방문 끝나면 다시 순차적으로 다음 위치 탐색(visited에 이미 방문했으면 건너뜀) def solution(M, N, m): """ M : 가로 N : 세로 m : 병사 배치 매트릭스 """ w_s..

www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 deque를 사용한 bfs로 품 from collections import deque def bfs(start, end): cnt = 0 # [현재 위치, 현재까지 걸린 시간] pair queue = deque([[start, cnt]]) # 문제 조건에 0~100000 위치까지로 명시됨. # 방문안한 위치만 queue에 값 추가해서 탐색 visited = [False] * 10..

www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 풀이 처음에는 case로 나누고 조건에 맞게 문자열 추가하는 방법 수행(실패, 시간초과) # 실패 edit_text = str(input()) edit_text_len = len(edit_text) cur_pointer = edit_text_len command_num = int(input()) for _ in range(command_num): command = input().split(' ') if comma..