몽상실현개발주의

[BOJ] 2667 / 단지번호붙이기 / Python 파이썬 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 이중배열로 된 데이터를 탐색하는 문제이다. 붙어있는 block 의 개수를 구하기 위하여, deque 로 BFS 를 구현하여 탐색하였다. import sys from collections import deque input = sys.stdin.readline def BFS(r, c): dq = deque() dq.append((r, c..

[BOJ] 9466 / 텀 프로젝트 / Python 파이썬 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 풀이 순환되는 graph 를 찾는 문제이다. 키 포인트는 마지막 node 와 첫 node 가 이어져서 Loop 를 이룬다는 것이다. 순환되는 graph 를 찾는 방법은 다음과 같다 방문 node 를 check 하며 순회 거쳐간 node 를 재방문 하였을때 순회 종료 마지막 node 와 이어진 node 의 index 부터 grpah 를 구성 lo..

[알고리즘 기초] 02_배열 2 (Array 2) / Python 1. 배열 : 2차 배열 1.1 2차원 배열의 선언 1차원 List를 묶어놓은 List 2차원 이상의 다차원 List는 차원에 따라 index를 선언 2차원 List의 선언: 세로길이(행의 개수), 가로길이(열의 개수)를 필요로 함 Python에서는 데이터 초기화를 통해 변수선언과 초기화가 가능함 arr = [[0, 1, 2, 3], [4, 5, 6, 7]] 1.2 2차원 배열의 접근 배열 순회 n X m 배열의 (n * m) 개의 모든 원소를 빠짐없이 조사하는 방법 행 우선 순회 # i 행의 좌표 # j 열의 좌표 for i in range(len(Array)): for j int range(len(Arrary[i])): Array[i]..

[알고리즘 기초] 01_배열 1 (Array 1) / Python 1. 배열 프로그램 내에서 여러개의 변수가 필요할때 사용. 하나의 선언으로 둘 이상의 변수를 선언 할 수 있다. - 완전탐색 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법이다. Brute-force 혹은 generate-and-test 기법이라고도 불리 운다. 모든 경우의 수를 테스트 한 후, 최종 해법을 도출한다. 일반적으로 경우의 수가 상대적으로 작을 때 유용하다. 수행속도가 느리지만 해답을 찾지 못할 확률이 적다. - 순열 (Permutation) 서로 다른 것들 중 몇개를 뽑아서 한 줄로 나열하는 것 nPr nPr = n * (n-1) * (n-2) * ... * (n-r+1) nPn = n * (n-1..

[알고리즘 기초] 00_intro ASP (Algorithm Problem Solving) / Python 0. 시작하기 전 - Programing Language Python Java C C++ C# Java script - 프로그래밍 절차 요구사항 분석 -> 문제 / 제약조건 파악 설계 -> 설계 : 연필로 적으며 가장 작은 test case를 해결해보기 개발론에서는 1,2 가 중요하다고 함. software는 도구일 뿐이다. 구현 -> 코딩 테스트 유지보수 1. Algorithm 어떤 문제를 해결하기 위한 절차나 방법. ex) 요리 레시피. 식을 만들 수 있으면 유리. - 알고리즘을 표현하는 방법은 크게 두가지 pseudocode(중간코드) : 타인이 보았을 때, 어떠한 논리인지 설명 될 수 있을 ..

[BOJ] 2331 / 반복수열 / Python 파이썬 https://www.acmicpc.net/problem/2331 2331번: 반복수열 첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다. www.acmicpc.net 풀이 제시되는 규칙으로 수열을 만들고, 반복되지 않는 수의 개수를 출력하는 문제이다. 각 수의 자리수인 0~9 까지의 수를 거듭제곱한 합으로 수열이 형성되므로, 수열은 반복되는 구간이 만들어진다. 이를 이용하여 수의 중복을 확인하고 중복 이전까지의 수열의 길이를 세어주었다. A, P = map(int, input().split()) nums = [A] while True: tmp = 0 for s in str(nums[-1]): tmp += int(s)..

[BOJ] 10451 / 순열 사이클 / Python 파이썬 https://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 풀이 순열과 index 로 그려진 graph 의 사이클 수를 구하는 문제이다. 순열의 수가 다음 순열의 index 가 된다는 것을 이해하면 쉽게 구할 수 있다. import sys input = sys.stdin.readline T = int(input()) for..

[BOJ] 1707 / 이분 그래프 / Python 파이썬 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 풀이 이분 그래프 (Bipartite Graph) 를 판별하는 문제이다. 그래프를 탐색하면서 node 에 -1 을 곱해주는 것으로 이분 그래프를 검사하였다. import sys input = sys.stdin.readline T = int(input()) for _ in range(T): N = int(input()) nums..