본문 바로가기

전체 글

(76)
알고리즘 기초 및 파이썬 기초 문법(3) - 리스트, 튜플, 문자열 자료형 리스트 자료형 - 여러 개의 데이터를 연속적으로 담아 처리하기 위해 사용 - 리스트 대신 배열 혹은 테이블로 불리기도 함 1. 리스트 자료형 초기화 #직접 데이터를 넣어 초기화 a = [1, 2, 3, 4] # [1, 2, 3, 4] #네 번째 원소만 출력 print(a[3]) # 4 #크기가 N이고, 모든 값이 0 인 1차원 리스트 초기화 n = 4 a = [0] * n print(a) # [0, 0, 0, 0] #반목문을 이용해서 초기화 array = [i for i in range(4)] print(array) # [0, 1, 2, 3] # 0 ~ 9까지 홀수만 포함하는 리스트 array = [i for i in range(10) if i % 2 == 1] print(array) # [1, 3, 5..
알고리즘 기초 및 파이썬 기초 문법(2) - 수 자료형 파이썬 기초 문법 자료형 - 파이썬에서의 자료형 정수형, 실수형, 복소수형, 문자열, 리스트, 튜플, 사전 등이 있음 수 자료형 정수형 #정수형(양/음의 정수, 0) a = 1000 #양의 정수 b = -7 #음의 정수 c = 0 #0 실수형 - 컴퓨터 시스템은 실수 정보를 표현하는 정확도에 한계를 가짐 - 개발 과정에서 실수 값을 제대로 비교하지 못 할 수도 있음 - round() 함수를 이용하여 문제 해결 - 123.456 소수 셋째 자리에서 반올림 round(123.456, 2) -> 123.46 #실수형 #소수점 아래의 데이터를 포함하는 수 자료형 a = 157.93 #양의 실수 b = -1837.2 #음의 실수 c = 5. #5.0 #소수부가 0일 때 0을 생략 d = -.7 #-0.7 #정수부..
알고리즘 기초 및 파이썬 기초 문법(1) - 알고리즘 기초 알고리즘 성능 평가 1. 복잡도(Complexity) - 알고리즘 성능을 나타내는 척도 (복잡도가 낮을수록 좋은 알고리즘) - 시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘 수행 시간 분석 - 공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘 메모리 사용량 분석 2. 빅오 표기법(Big-O) - 가장 빠르게 증가하는 항만 표기 (차수가 가장 큰 항만 남김) 3. 알고리즘 설계 팁(Python) 1. Python을 기준으로 5 ~ 15초 가량 시간 소요 2. 상황에 따라 PyPy도 이용해 보는 것도 좋음 3. 코딩 테스트 문제의 시간제한은 통상 1~5초 4. 문제에서 시간제한(수행시간 요구사항)을 가장 먼저 확인 - N의 범위 500인 경우 - O(N^3) 알고리즘 - N의 범위 2,000인 경..
백준 1987번_알파벳 (Python/파이썬) https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 ..
[Python] set(집합) 자료형 정리 1. 파이썬 set(집합) 집합에 관련된 것을 처리하기위해 만들어진 자료형 순서가 없음 - 인덱싱 불가능 중복을 허용하지 않음 (고유한 값을 가짐) mutable(=값이 변하는) 객체 s1 = set([1,2,3]) print(s1) s2 = set("hello") # {1,2,3} # {'o', 'h', 'l', 'e'} 만약 set 자료형에 저장된 값을 인덱싱으로 접근하려면 리스트 또는 튜플로 변환 후 접근해야함 s1 = set([1,2,3]) list1 = list(s1) print(list1) print(list1[0]) # [1,2,3] # 1 2. 파이썬 set(집합), 교집합/합집합/차집합 s1 = set([1, 2, 3, 4, 5, 6]) s2 = set([4, 5, 6, 7, 8, 9])..
백준 2178번_미로 탐색 (Python/파이썬) https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 N×M크기의 배열로 표현되는 미로가 있다. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 ..
백준 1260번_DFS와 BFS (Python/파이썬) https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 1..
그래프 탐색 알고리즘 DFS & BFS, Backtracking(백트래킹) (2) DFS(Depth-First Search) - DFS : 깊이우선 탐색 - 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 - DFS는 스택 자료구조(혹은 재귀 함수)를 이용 1. 탐색 시작 노드를 스택에 삽입 후 방문 처리 2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리, 방문하지 않은 노드가 없으면 스택에서 최상단 노드를 꺼냄 3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복 + ) Backtracking(백트래킹) - 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되는 즉시 후보를 포기에 정답을 찾아가는 범용적 알고리즘 - 탐색에서는 이 길이 아닌 것 같으면 왔던 길로 되돌아와 다른 선택지로 감 - 재귀로 보통 구현, 재귀..