본문 바로가기

프로그래머스, 백준

백준 1051번 숫자 정사각형 문제와 입출력 조건은 다음과 같다.    N×M 크기의 2차원 배열로 생각을 한다.배열의 각 칸에는 한 자리 숫자라 했으니 0부터 9까지의 숫자가 적혀 있다.정사각형의 꼭짓점이 모두 같은 숫자로 이루어져야 한다.  자 이제 가능한 모든 정사각형의 크기를 생각해야 한다. 크기는 1x1부터 시작하여 최대 N×M의 크기로 나올 수 있다.1x1 정사각형은 항상 가능하므로 초기 최대 크기를 1로 설정한다.  정사각형의 크기(size)를 증가시키며 2부터 시작하여 가능한 최대 크기까지 반복하면서 최대 크기를 찾고현재 정사각형의 크기를 기준으로 가능한 모든 정사각형의 시작 위치를 찾는다. 정사각형의 꼭짓점 값들을 비교하고 모든 꼭짓점 값이 동일하다면 현재 정사각형의 크기를 최대 크기(max_size)로 업데이트한다... 더보기
백준 1045번 도로 https://www.acmicpc.net/problem/1045  문제와 입출력 조건은 다음과 같다.     우선순위에 따라 정렬해야 되기에 우선순위 큐나 정렬된 리스트를 생각해볼 수 있었다.인접행렬로 탐색하면서 저장하고 둘 중 하나로 정리를 하면 될 것 같은데 더 이상의 아이디어가 생각나지 않았다. 몇 번 도전했지만 계속 틀려서 다른 분의 풀이를 보면서 이 문제를 풀 때 주의해야 할 점을 정리했다.  MST 구성 시 반드시 N-1개의 간선을 사용해야 한다.도로의 우선순위를 정확히 반영하여 내림차순으로 처리해야 한다.Union-Find를 사용해 두 도시가 연결되었는지 확인한다.남는 도로는 나중에 필요하면 추가로 사용한다.MST가 유효하지 않다면 -1을 출력해야 한다.출력 형식에 맞게 도로 개수를 각 도.. 더보기
백준 1012번 유기농 배추 입출력 조건은 다음과 같다.        각 테스트 케이스에 대해 M x N 크기의 2차원 리스트 field를 생성했다.입력받은 배추의 위치를 field에 표시하여 1로 설정한다.field를 순회하면서 아직 방문하지 않은 배추(1)를 발견하면-해당 위치에서 DFS를 시작합니다.-DFS는 연결된 모든 배추를 방문했다고 0으로 변경한다.-DFS가 종료되면 하나의 연결된 배추 그룹을 모두 처리한 것이므로 count를 +1한다.모든 배추를 처리할 때까지 반복문으로 처리한다.   import syssys.setrecursionlimit(10000)def dfs(x, y): # 주어진 범위를 벗어나는 경우 즉시 종료 if x = M or y = N: return # 현재 노드를 .. 더보기
백준 1011번 Fly me to the Alpha Centauri https://www.acmicpc.net/problem/1011     입출력 조건은 다음과 같다.  이전에 k광년을 이동했다면 다음은 k-1,k,k+1 광년 중 하나다.첫 이동은 1광년이고 도착 전 마지막 이동이 반드시 1광년이어야 한다.총 이동거리가 n(n+1)/2보다 작거나 같을 때, n번의 이동으로 y에 도착할 수 있다.   n(n+1)/2가 distance와 같거나 약간 크다면-> n번의 이동으로 도착지에 도달하거나 약간 지나칠 수 있으므로 n을 반환한다.n(n+1)/2가 distance보다 작다면-> 추가로 한 번 더 이동해야 도착지에 도달 가능하여 n+1을 반환한다. distance = y - x: 총 이동해야 할 거리를 계산한다.while 루프 안에서:현재 step만큼 이동하고 moves.. 더보기
백준 1932번 정수 삼각형 https://www.acmicpc.net/problem/1932   첫째 줄부터 밑으로 내려가면서 최대 합을 계산하는 단순한 방법으로 생각했다. 문제에서 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다고 한다. 이를 생각하면 아래층에 있는 수는 세 가지 경우로 나눌 수 있다. 1. 현 위치가 해당 줄에서 가장 왼쪽2. 현 위치가 해당 줄에서 가장 오른쪽3. 현 위치가 해당 줄에서 가운데 끼어 있는 수 입력값을 줄 때 첫 줄은 일자로 보이기 때문에 바로 위라고 표기했다. 세 가지 경우에 윗 줄 수는 1번은 바로 위2번은 대각선 왼쪽 위3번은 바로 위 or 대각선 왼쪽 위 중 큰 쪽이다. 첫 번째 수는 맨 꼭대기 값으로 자동 결정이 된다. 따.. 더보기
백준 2798번 블랙잭 https://www.acmicpc.net/problem/2798 합의 경우의 수를 구해야 한다..for문과 list를 사용해서 경우의 수를 구할 수 있지만순열과 조합 함수가 있던 것이 기억났다.그렇지만 제대로 어떻게 쓰는지 몰라서 찾아봤다. 순열 (nPr)- permutations 순열이란 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미한다. (순서 상관 있음)조합 (nCr)- combinations 조합이란 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미한다. (순서 상관 없음)첫번째 인자는 조합할 요소들이 들어있는 list, tuple과 같은 컨테이너 타입의 변수이고 두번째 인자는 몇 개로 조합할지 나타내는 변수이다.permutations의 경우에는 두 번째 인자를 할당하지 않으면 첫 번.. 더보기
백준 2231번 분해합 https://www.acmicpc.net/problem/22310부터 N까지 탐색하라고 만든 문제는 아니겠지...라고 생각은 했지만 마땅히 좋은 방법이 생각나지 않았다.비효율적이어도 나의 현 실력으로 풀 수 있는 방법으로 접근해보자하고 0부터 N까지 탐색하는 법으로 코드를 짰다. N = int(input()) result = 0for i in range(N): # 0부터 N까지 순회 result = i str_i = str(i) # 자릿수 문자열로 변환 for j in str_i: #현재 값을 이루는 각 자릿수에 대해 반복 i += int(j) if i == N: print(result) breakelse: # 생성자가 없을 때는 0 출력.. 더보기
백준 9095번 1,2,3 더하기 https://www.acmicpc.net/problem/9095 규칙을 찾아내기 위해 경우의 수를 세봤다.정수합을 나타내는 방법의 수11223447513 4의 합을 나타내는 방법의 수는 1,2,3의 합을 나타내는 방법의 수의 합이고 5의 합을 나타내는 방법의 수는 2,3,4의 합을 나타내는 방법의 수의 합이다. 일반화 하면 n의 합을 나타내는 방법의 수는 n-1,n-2,n-3의 합을 나타내는 방법의 수의 합이다.이를 이용하여 코드를 짠다. 저번 백준 과제를 하면서 알게 된 dp 동적 프로그래밍을 사용하면 된다.코드에 추가적인 주석을 달아놨다.T = int(input())# 0부터 10까지의 숫자를 만들기 위한 경우의 수를 저장할 리스트를 생성# 초기값으로 1, 2, 3을 만드는 경우의 수를 설정d = .. 더보기

티스토리툴바