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..

https://programmers.co.kr/learn/courses/30/lessons/42892 코딩테스트 연습 - 길 찾기 게임 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] programmers.co.kr 풀이 입력으로 [x, y] 좌표 데이터를 원소로 하는 리스트를 받아 조건에 맞게 이진트리를 만든 뒤 전위 순회, 후위 순회했을 때 방문해야할 노드 index리스트를 반환하는 문제 y값이 level이라 먼저 y값으로 내림차순, x값은 오름차순으로 동시에 정렬하면 순차적으로 node를 추가할 수 있음. 전위 순회, 후위 순회는 재귀함수를 사용하면 간단히 구현할 수 있..

https://www.hackerrank.com/challenges/ctci-connected-cell-in-a-grid/problem DFS: Connected Cell in a Grid | HackerRank Find the largest connected region in a 2D Matrix. www.hackerrank.com 풀이 0과 1로 구성된 grid가 주어지면, 1을 기준으로 한 영역의 최댓값을 구하는 문제. 8가지 방향에 1이 있으면 같은 영역이라 가정.(왼쪽 대각선 위부터 시계방향) visited를 확인하기 위한 matrix 만들고, 방향 정보 리스트 만들고, stack을 사용해 dfs 구현하면 됨. def maxRegion(grid): n = len(grid) m = len(grid..

https://www.hackerrank.com/challenges/ctci-bfs-shortest-reach/problem BFS: Shortest Reach in a Graph | HackerRank Implement a Breadth First Search (BFS). www.hackerrank.com 풀이 그래프와 시작노드가 주어졌을 때 BFS로 다른 노드까지의 depth를 구하는 문제. 도달할 수 없으면 -1 리턴. BFS로 depth를 구할 때, 아래와 같은 순서대로 풀면 됨. 먼저 start_node를 정의(혹은 주어짐). 방문 정보를 저장할 visited 리스트 0으로 초기화. start_node에 대해서는 1로 처리 queue에 start_node 저장. depth는 dictionary를..

https://www.hackerrank.com/challenges/find-the-nearest-clone/problem Find the nearest clone | HackerRank Find the shortest path length between any two nodes with the given condition. www.hackerrank.com 풀이 그래프 정보와 각 노드의 색깔 저보가 주어짐. 특정 색깔을 입력받았을 때 같은 색깔의 다른 노드에 도달할 수 있는 최단 거리를 구하는 문제 먼저 adj_matrix를 만들어주는데, 파이썬의 dictionary를 사용. key : node, value : [인접 노드] 방향이 없기 때문에 graph_from, graph_to에 있는 노드를 번갈아..