백준 삼성 코딩 기출 문제 - 주사위 굴리기 python 출처 : BAEKJOON ONLINE JUDGE주사위 굴리기 (https://www.acmicpc.net/problem/14499) 문제 설명지도의 크기 NXM에서 오른쪽은 동쪽, 위쪽은 북쪽입니다. 주사위가 하나 주어지는데 모든 면에는 0이 적혀져 있습니다. 주사위가 놓여진 좌표가 (x, y)가 있습니다. 지도의 각 칸에는 정수가 쓰여져 있고, 주사위를 굴리면 돌아가는데 이동한 칸 수에 0이면 주사위 바닥면에 쓰여 있는 수가 복사됩니다. 0이 아닌 경우에는 칸에 쓰여 있는 수가 바닥면으로 복사되고, 칸에 쓰여 있는 수는 0으로 교체가 됩니다. 명령이 주어지는대 동쪽은 1, 서쪽은 2, 북쪽은 3, 남쪽은 4로 주어집니다. 복잡하게 생각하면 끝없이..

백준 삼성 코딩 기출 문제 - 시험 감독 python 출처 : BAEKJOON ONLINE JUDGE시험 감독(https://www.acmicpc.net/problem/13458) 문제 설명N개의 시험장이 있고, i번 시험장에 있는 응시자의 수의 A_i명이 있습니다. 총 감독관이 감시할 수 있는 응시자의 수 B명, 부감독관은 C명입니다. 시험장에 총감독관은 오직 1명만 있어야 하고, 부감독관은 여러명 있어도 됩니다. 필요한 감독관 수의 최솟값을 구하는 프로그램을 작성합니다. 문제 풀이[1] 우선 입력값을 받아 들입니다. N = int(input()) # 시험장 개수 applicant = list(map(int, input().split())) # 시험장에 응시자의 수(리스트) B, C = map(int,..

백준 삼성 코딩 기출 문제 - 2048 (Easy) python 출처 : BAEKJOON ONLINE JUDGE2048 (Easy) (https://www.acmicpc.net/problem/12100) 문제 설명2048 게임은 4×4 크기의 보드에서 같은 값을 갖는 두 블록이 충돌하면 합쳐집니다.다음의 게임을 해보시면 이해가 갑니다ㅎㅎ 핸드폰 앱 게임으로도 많이 나와 있죠.https://play2048.co 여기서는 NxN크기의 보드가 주어집니다. 이미 합쳐진 블록은 다른 블록과 다시 합쳐지지 않습니다. 실제 게임에서는 이동을 할 때마다 블록이 추가되지만, 이 문제에서는 추가되지는 않고 주어진 보드에서 최대 5번을 이동할 경우 가장 큰 블록 값을 구합니다. 문제 풀이시뮬레이션을 해보는 문제입니다.[1]..

백준 삼성 코딩 기출 문제 - 구슬 탈출2 python 출처 : BAEKJOON ONLINE JUDGE구슬 탈출2 (https://www.acmicpc.net/problem/13460) 처음 보시는 분들은 다음의 링크에서 문제 풀이를 꼭 봐주세요!! 백준 삼성 코딩 기출 문제 - 구슬 탈출 python(https://jeongchul.tistory.com/665) 문제 설명이전 문제와 조건은 동일합니다. 보드의 상태가 주어졌을 때, 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성해야 합니다. 문제 풀이이전에 구슬의 움직이는 시도한 횟수(depth)를 출력하면 풀이는 끝납니다.depth는 초기화를 1로 하였습니다. 처음의 움직임은 시도 1이니 1로 초기화해서 푸는게 쉽습니..

백준 삼성 코딩 기출 문제 - 구슬 탈출 python 출처 : BAEKJOON ONLINE JUDGE구슬 탈출(https://www.acmicpc.net/problem/13459) 문제 설명보드가 N X M 크기로 있고, 중력을 통해서 떨어지기 때문에 기울이는 것을 통해서 위/아래/오른쪽/왼쪽으로 움직임이 가능합니다. 빨간 구슬(R)을 구멍(O)으로 움직여야 하고, 단 파란 구슬(B)가 구멍(O)으로 들어가거나 또는 같이 들어가도 실패합니다. 움직이는 횟수는 총 10번 이하로 제한되고 가능하면 1, 실패하면 0을 출력합니다. 문제 풀이BFS(Breadth-First-Search) 알고리즘은 queue(FIFO -> deque사용)과 while(무한 루프)를 사용해 탐색을 구현합니다. DFS(Depth F..

python 부분합, 연속 부분수열 최대합부분합부분합은 배열의 시작부터 현재 위치까지의 원소의 합을 구해둔 배열(paritial_sum)입니다.다음의 표를 보면 partial_sum을 미리 계산하면 특정 구간의 합을 O(1)에 구할 수 있습니다. index012345scores[]10095801007065partial_sum[]100195275375445510 예를 들어 3번째부터 5번째의 합을 구하고 싶다하면 partial_sum[5] - partial_sum[3-1] = 510-275 = 235를 구할 수 있습니다.이 공식을 이용하면 구간합을 구할 수 있게 됩니다. def partial_sum(arr, a, b): arr = [0] + arr partial_sum = [0] * len(arr) for..

Python 구간 사이의 최소 제곱근 찾기 문제설명A, B의 두 개 정수 구간 사이에서Square Root의 최대 반복된 적용된 정수값을 반환하면 됩니다. A가 10, B가 20인 경우에 살펴보면 구간 사이에 10,11,12,13,14,15,16,17,18,19,20 값이 있습니다. 여기서 sqrt가 최대로 적용된 최소 제곱근 정수값을 찾아보면16은 16->4->2가 되므로, 함수는 2를 반환하면 됩니다. A가 3000, B가 6000인 경우를 보면 4096은 4096->64->8로 떨어지므로, 함수는 8을 반환하면 됩니다. A와 B는 2 ~ 1,000,000,000 사이의 값입니다. [1] math.sqrt를 쓰면 float형이 나온다. 이는 정수로 나눠 떨어지는 것을 확인해보기 위해서는int(math..

graph shortest path - 최단 경로 다익스트라 알고리즘 python다익스트라 알고리즘하나의 정점(node) A에서 다른 정점 B까지 최단 경로를 구한다. 이 때 간선들은 양의 weight를 가져야 한다.시작하는 A를 제외하고는 나머지 node는 미방문으로 초기화하고, 연결되지 않은 값은 inf(무한대)로 표시한다. 시작하는 node에서부터 연결된 노드들의 edge 값을 확인한다. edge 값 중에서 가장 짧은 edge를 선택하여 node의 값을 업데이트 합니다. 그 다음 노드에서도 마찬가지로 인접한 노드들의 edge를 확인하고 선택한다. 경로에 필요한 edge들의 합을 통해서 node를 업데이트 한다. 다익스트라 알고리즘은 방문하지 않은 노드가 없고, 목표 지점인 B까지 도달하면 멈추고, ..