동학 개발 운동

문제 출처 : www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 해석 : 붙어있는 집끼리 같은 단지로 취급하여 몇개의 단지가 있는지 단지 번호 몇개의 집이 있는지 출력하는 문제이다. 문제 풀이 : BFS를 통해서 간단하게 문제를 풀이할 수 있다. 가능한 다른 풀이 : DFS도 이용가능하지만 BFS가 더 적당할 것 같다. 풀이 코드 from collections import deque def BFS(a, b, count): global visited Q = ..

문제 출처 : www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 문제 해석 : 색종이를 계속해서 쪼개어 같은 색만 남을 때까지 자르는 행위를 하고 한 가지 색상으로만 된 색종이의 갯수를 출력하는 문제이다. 문제 풀이 : 전형적인 분할정복 문제로 아래의 풀이는 실제 배열을 잘라서 파라미터로 넘기고 이를 저장하는 방식으로 문제를 풀었다. 4 분할을 진행하기 때문에 2중 for문을 2번씩 도는 형식으로 진행된다. 가능한 다른 풀이 : 파라..

문제 출처 : www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제 해석 : 1번 컴퓨터로 부터 바이러스가 퍼진다. 이때 네트워크상에 연결된 모든 컴퓨터가 감연되는데 이 수를 구하는 문제이다. 문제 풀이 : 다양한 방법으로 문제를 풀이할 수 있지만 자신의 부모를 찾는 연산을 통해서 부모 노드가 1인 모든 노드를 찾으면 되기 때문에 부모를 찾는 방법을 사용했다. 다만 입력의 순서 때문에 오류가 발생할 수 있기 때문에 2번의 union 연산을 진행했다. 가능한 다른 ..

문제 출처 : www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 해석 : 계단에 적힌 수들을 합하면서 올라간다. 이때 한번에 한 개씩 3개 이상의 계단을 오르지 못하고 2계단을 한번에 이동할 수 있다. 수의 최대값을 구하는 문제이다. 문제 풀이 : 전형적인 DP 문제로 점화식을 도출 할 수 있다. 한번에 3개의 계단을 연속적으로 이동하지 못하기 때문에 1. 이전계단과 자신의 계단 + 3칸 전 최대값 2. 두개 이전의 계단의 최대값 + 자신의 계단 중 가장 큰 값을 구..

문제 출처 : www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 해석 : 0과 1로 이루어진 배열에서 1은 이동가능한 것을 뜻한다. 여기서 1,1 에서 N,M으로 이동하는 최소 칸 수를 출력하는 문제이다. 문제 풀이 : 전형적인 탐색 문제로 여기서는 BFS를 이용해서 문제를 풀 수 있다. 거리를 기록하는 array와 방문 여부를 체크하는 array 두개를 이용해서 매 순간 가능한 모든 경로를 체크하면서 문제를 해결 할 수 있다. 풀이 코드 from collections import de..

문제 출처 : www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 문제 해석 : 0 또는 1로만 이루어진 구역을 찾는 것으로 다른 숫자가 섞여 있다면 이를 4분할 해서 다시 한 번 검사하는 문제이다. 문제 풀이 : 전형적인 분할정복 문제로 재귀적으로 함수를 사용하여 풀 수 있다. 풀이 코드 def check(arr): length = len(arr) first = arr[0][0] for i in range(length): for j in range..

문제 출처 : www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 해석 : 유명한 자료구조 중 하나인 최소힙의 사용법 또는 구현을 할 수 있는지 묻는 문제이다. 문제 풀이 : 입력이 자연수일 때는 삽입 연산을, 0일 때는 pop을 해주는 문제이다. Python에서 제공하는 heapq 를 사용하면 간단하게 문제를 풀 수 있다. 가능한 다른 풀이 : Python에서 제공하는 모듈인 heapq를 사용하지 않고 직접 구현하여 만들 수 있다. 풀..

문제 출처 :www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net 문제 해석 : 자른 종이의 모든 수가 같은 경우를 -1, 0, 1 케이스로 카운팅하여 출력하는 문제이다. 만약 모든 수가 같지 않으면 다시 종이를 9등분하여 행위를 반복한다. 문제 풀이 : 전형적인 분할 정복 문제로 작은 문제로 부터 큰 문제로 생각하여 풀이를 진행하면 풀 수 있다. 1. 종이의 모든 내용이 같은지 체크한다. 2. 같지 않다면 인덱싱을 통해서 재귀적으로 이를 수행한다. 3..

기본 설정 우분투는 한글 사용이 되지 않는다. (ex. AWS Instance) ps) 홈페이지에서 한글판 리눅스를 받은 경우에는 자동으로 언어팩을 설정하게 되어있다. -> 이러한 경우에는 한글 입력, 출력이 제한되기 때문에 한글 설치 방법에 대해서 알아보고자 한다. 1. 아래의 명령어를 통해서 언어팩을 다운 받는다. sudo apt-get install language-pack-ko sudo apt-get install language-pack-ko-base sudo vim /etc/environment 2. sudo vim /etc/environment 명령어를 통해서 vim을 켜 아래 내용을 가장 끝에 추가해 준다. LANG="ko_KR.UTF-8" LANG="ko_KR.EUC-KR" LANGUAG..

문제 출처 : www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 문제 해석 : 듣지도, 보지도 못한 사람 이름을 출력하는 문제이다. 문제 풀이 : 두 집합에서 교집합을 찾는 문제로 파이썬의 intersection을 이용하면 풀 수 있다. 풀이 코드 import sys input = sys.stdin.readline N, M = map(int, input().split()) answer = [] hear = [] saw = [] for _ in range(N)..