본문 바로가기

백준

 (47)
[백준]_2568번 : 전깃줄 - 2(파이썬) 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 일단 아이디어 자체는 전깃줄과 다를 바가 없다. 꼬인 전깃줄을 꼬이지 않게 하기 위해서는 전깃줄을 하나의 쌍(예를 들어 [1, 8])으로 묶은 다음에 첫 번째 요소에 대해 정렬을 진행한 다음에 두 번째 요소의 LIS(최장 부분 수열)를 구하면 된다. 애초에 전깃줄의 꼬임이 왜 발생하는지에 대해 생각해 보면 이해하기 수월해진다. 전깃줄은 다음과 같은 조건을 만족시킬 때 꼬인다. 왼쪽 전봇대의 전깃줄을 a1, b1 이라고 하고 그에 대응하는(이어져 있는) 오른쪽..
[백준]_2239번, 2580번 : 스도쿠(파이썬) # 입력 부분 import sys input = sys.stdin.readline tmp=[input().strip() for _ in range(9)] board=[[0]*9 for _ in range(9)] for r in range(9): for c in range(9): board[r][c]=int(tmp[r][c]) # 출력 부분 for r in range(9): for c in range(9): print(board[r][c], end='') print()​ 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc..
[백준]_16139번 : 인간-컴퓨터 상호작용(파이썬) 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 누적합과 사전을 적절히 사용하면 무난하게 풀렸던 문제이다. 문제에 나와 있듯이 문자열의 길이와 질문의 수는 최대 200,000까지 늘어날 수 있기 때문에 질문을 하나 받을 때마다 문자열 구간 [l, r]에서 목표 알파벳이 몇 개 나오는지 다시 샐 여유가 없다. 따라서 아래와 같은 접근을 사용하여 시간을 줄이는 전략을 선택했다. 접근 알파벳을 target, l을 start, r을 finish라고 하자. 또한 과거에 ..
[백준]_2565번 : 전깃줄(파이썬 and C언어) 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 아이디어만 잘 찾으면 풀기 쉬웠던 문제였다. 다만 LIS(Longest Increasing Subsequence)와 이 문제가 무슨 연관이 있는지 떠올리는 데에 시간의 대부분을 할애했다. 접근 전깃줄이 꼬이지 않게 하기 위해서는 어떤 특징이 있을까? 먼저 예제에서 언급한 대로 전깃줄 3개를 한 번 제거해 보자. 3개를 제거하고 나니 전깃줄이 꼬이지 않기 위해서는 어떤 원칙을 지켜야 하는지 보이기 시작한다. 그것은 바로 전봇대 A가 전봇대 B로 전사하는 전깃줄은 A의 번..
[백준]_12852번 : 1로 만들기 2(파이썬) 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 1로 만들기 문제에서 업그레이드된 문제이다. 이 문제는 크게 두 가지 영역으로 나뉘고 서로 거의 독립적인 코드를 요구한다. 사실 1번 코드로부터 2번 코드에서 사용될 정보는 1번 코드의 결괏값 1개뿐이다. 이 문제에서 요구하는 그대로 1로 만들기 위해 필요한 연산 횟수를 구하는 코드. 입력 n에 대해 1까지의 경로를 탐색하는 코드. 1번 코드는 이미 만들었다고 가정하고(궁금하면 위의 링크를 타고 해결책(dp, bfs)을 보고 오시기를 바랍니다) 2번 코드만 작성해 보겠다. 접근 n에 대한 연산 횟수 정보를 이미 얻었다고 가정하고 이 값을 A라고 하자. 이제 n에서 출발..
[백준]_1463번 : 1로 만들기(파이썬) 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 동적 계획법? 잘 알려져 있는 동적 계획법(Dynamic Programming) 문제이다. 동적 계획법은 큰 문제를 여러 개의 작은 문제로 나누어 푸는 방법을 의미한다고 생각하면 편하다. 각 하위 문제를 해결한 후 그 해결에서 얻은 답을 나중에 다시 사용하는 방법인 것이다. 이 꼬리의 꼬리를 무는 과정을 계속하다 보면 결국 우리가 원하는 큰 문제에 대한 답이 튀어나온다는 원리인 것이다. 가장 좋은 예시로는 피보나치 수열이다. 9 번째 피보나치 수열의 값을 얻기 위해서는 0+1=1 -> 1+1=2 -> 1+2=3....처럼 아래에서부터 차근차근 올라가는 과정을 진행에 있어 과거..
[백준]_2096번 : 내려가기(파이썬) 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 비슷한 문제로는 RGB 거리 문제가 떠오른다. 전형적인 DP문제로 쉽게 풀 것이라고 생각했지만 모든 dp문제가 다 그렇듯이 문제마다 요구하는 특별한 방법이 있기 때문에 상황 파악이 우선이다. 필자는 이 문제를 풀 때 잘못된 접근을 하여 한동안 헤맸었다. 잘못된 접근 법은 아래에 정답 코드 이후에 설명하겠다. 접근 문제의 조건을 보면 N이 100000까지 커질 수 있기 때문에 2차원 dp N*3짜리를 만드는 것은 별로 효율적이지 않다. 따라서 dp리스트는 3*1짜리로만 풀 것이..
[백준]_1260번 : DFS와 BFS(파이썬 and C언어) 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net INDEX 1. 그래프 탐색 2. 전략(파이썬) 3. 전략(C언어) 1. 그래프 탐색 어떤 정점들이 서로 간선으로 연결되어 있다. 이것을 그래프라고 한다. 그래프 탐색이 초반에 까다롭게 느껴지는 점은 바로 방문했던 정점을 다시 방문할 필요가 없다는 사실이다. 이제 이것을 코드로 어떻게 처리하냐는 나중의 문제이고, 그래프 탐색에는 크게 두 가지 방법이 있고 이번 문제에서는 그것들에 대해 묻고 있다. 첫 번째는 DFS(Depth..

티스토리툴바