Seung_story

데이터 입력받기 input: 데이터를 입력 받도록 하는 함수. 입력 받은 데이터는 모두 문자열로 취급 # LIST로 입력받기 data=list(input().split()) # 변수가 많이 필요하지 않을 때 a,b = input().split() 숫자 입력 받을 경우 map: 여러 데이터를 한번에 일괄적으로 변환하기 위해 사용 / map(변환함수, 가능한 데이터) # LIST로 입력받기(int로 MAPPING) data=list(map(int, input().split())) # 변수가 많이 필요하지 않을 때 a,b = map(int,input().split()) NxM 크기 이차원 리스트 초기화 & 입력받기 ## 리스트 초기화하기 data=[[False]*m for _ in range(n)] ## 리스..

반복문 컴퓨터에게 반복적인 작업을 지시하기 위해 사용하는 방법이다. while 문 / for문 이 있다. For문 기본구조 For문 기본구조는 위와 같이 구성되어 있다. For 반복문은 in 뒤에 존재하는 문자열, 리스트, 튜플 또는 range(시작 숫자, 끝 숫자)를 순회하면서 하나씩 변수에 값을 넣어준다. * range(숫자1,숫자2)-> 시작 숫자부터 끝숫자까지의 숫자 (이때 끝 숫자는 포함되지 않는다) For문 예시 ### 예시1 구구단-2단 N=2 for i in range(1,10): print('{0} x {1} = {2}'.format(N,i,N*i)) ### 예시1-1 구구단-2단~9단 for N in range(2,10): print("===={0}단====".format(N)) for..

조건문이란? 참과 거짓을 판단하는 문장을 말한다. C언어 같은 경우 {}를 통해서 코드 블록을 나누지만 Python의 경우에는 들여쓰기를 통해 코드 블럭을 나눕니다. if 의 조건에 참과 거짓 대신 문자열이나 다른 것을 넣을 수도 있습니다. False로 판단 하는 경우: None / 0 / "" / [] / () / {} / set() --> 문자열, 리스트, 튜플, 딕셔너리 등의 값이 비어 있음 if문의 기본 구조 조건문을 테스트해서 참이면 if문 안의 블록들을 수행하고, 조건문이 거짓일 경우 else문 안의 블록을 수행하게 된다.(위의 사진 참고) 다양한 조건을 사용하는 elif if와 else 만으로는 다양한 조건을 판단하기 어렵다. 다중 조건 판단을 하기 위해 elif 를 사용한다. a=1 if ..

딕셔너리 키(Key)와 값(Value)으로 가지고 있는 자료형 리스트나 튜플 처럼 순차적으로 해당요소값을 구하지 않고, Key를 통해 값을 얻는것이 특징 사용방법 딕셔너리 추가 [ex] A['number']=1 딕셔너리 요소 삭제: [ex] del A['number'] 딕셔너리 주의 사항 딕셔너리를 만들 때에는 Key 에 리스트를 쓸 수 없다. -> Key 값은 변하지 않는 값으로 설정해야 한다. Key 값이 중복으로 사용될 수 없다.(중복될 경우, 하나를 제외한 나머지 Key 값이 무시된다.) 딕셔너리 관련 함수들 keys(): 딕셔너리의 Key 값이 출력된다. values(): 딕셔너리의 Value 값들이 출력된다. items(): 딕셔너리의 key와 value가 쌍을 이루어 출력된다. clear()..

Dijkstra 알고리즘 문제점 현재위치로부터 모든 방향으로 최단경로를 찾아 쓸대없는 경로를 모두 탐색(시간 오래걸림) 개선한 알고리즘이 A* 알고리즘이다! A* 알고리즘 vertex 중 도착점과 가까운 vertex를 골라 경로 탐색 g(n): 시작 노드부터 현재 노드까지의 비용 h(n): 현재 노드에서 목표 노드까지의 예상 비용 ( 휴리스틱 함수, 설계하는 방법에 따라 알고리즘 성능 결정) 두 값을 더한 f(n) = g(n) + h(n)이 가장 최소가 되는 노드를 다음 탐색 노드로 선정한다. A* 알고리즘 단점: 찾은 경로가 최단경로가 아닐 수 있다. Dijkstra vs A* 알고리즘 비교 A* 알고리즘을 이용하여 미로찾기 구현하기 1. 각 장소에 해당하는 dtable의 배열을 초기화한다. 2. 출발..

구현방법 1. 주어진 지도를 2차원 배열로 만든다. (1= 지나갈 수 있음 / 0=벽이 있음) ※ 모든 거리는 1로 계산하였다. 2. 2차원으로 만든 지도의 연결관계를 또다른 배열 Graph에 표현한다. 내 좌표에서 상,하,좌,우가 지도안에 있고, 벽이 아니면 연결되있다는 것을 의미한다. map의 (i,j)를 값으로 나타내면 3*i+j이고, n 값이 나타내는 map 배열의 좌표를 나타내면 (n/3, n%3)으로 나타낸다. 3. Dijkstra 알고리즘을 통해 최단경로를 찾는다. 만약 아직 현재 좌표의 최단거리를 찾지 않았을 때, 시작좌표~현재 좌표의 최단거리를 알고 현재좌표~다음좌표의 거리를 알면 두 값을 더해서 다음좌표의 최단거리 값에 저장한다. 만약 다른 경로를 통해 간 거리가 짧다면 그 거리 값을 ..

Dijkstra 알고리즘이란? 최단거리르 찾는 아록리즘 장점: 모든 최든경로를 알 수있다 / 누구를 거쳐서 지나갔는지 알 수 있다. Dijkstra 알고리즘 구현방법 1. 하나의 vertex로부터 시작 2. 최단거리의 vertex로부터 하나씩 추가 3. 모든 vertex에 대한 최단거리를 찾을 때 반복 [ex] 하기와 같은 그래프가 있고, A->F까지 가는 최단경로를 구하려면... 1. 그래프에 대해 Table로 내용을 작성한다. 2. 시작점을 'A'라 하면, A와 연결된 경로를 입력한다. 3. 'B'와 연결된 최단거리 노드를 찾고, 경로를 입력한다. 4.'C'와 관련된 최단거리 노드를 찾고, 경로를 입력한다. 이때, D로 갈때, A-C-D로 가는것이 A-B-D로 가는것보다 빠르므로 update 해준다...

그래프 탐색 알고리즘 하나의 Vertex에서 시작하여 Graph의 모든 Vertex를 방문하는 알고리즘(중복 없이 방문) DFS(Depth First Search) 깊이 위주의 탐색 길을 가다 막히면 갈림길이 있던 곳으로 돌아와 다시 시작 Stack / 재귀함수 이용 1. Stack 으로 구현했을 경우 #include #define NUM_VERTEX 5 int graph[NUM_VERTEX][NUM_VERTEX]; int visited[NUM_VERTEX]; char stack[NUM_VERTEX]; int top = -1; void push(char s){ if (top == NUM_VERTEX - 1) return; top++; stack[top]=s; } char pop(){ if (top == ..

그래프란? 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구소 [ex] 지하철 자료구조 그래프 용어 Vertex(정점): node를 나타냄 Edge(간선): Vertext간의 관계를 나타내는 선(Vertex를 연결해줌) Adjacent vertex : 어느 vertex에 대해 edge 로 연결된 vertex(A's adjacent vertex ->B,C,D / B's adjacent vertex -> A, C) Degree: edge의 개수 Cycle: 시작 vertex로 다시 돌아오는 그래프( 시작 vertex=도착vertex) Completed Graph: 모든 vertex들이 다른 vertex들과 모두 연결된 그래프, edege의 개수=n(n-1)/2 (n은 vertex 개수) 그래프의 종류 ..

리스트(List)란? 자료를 순서대로 저장하는 구조입니다. 리스트를 사용하면 여러 변수를 한 번에 저장할 수 있습니다. 리스트 자료형은 순서도 있고, 중복도 있고, 수정도 가능하고, 삭제도 가능합니다. 리스트 만들기 변수에 값을 저장할 때 [ ](대괄호)로 묶어주고, 각 값을 , (콤마)로 구분할 수 있습니다. 위와 같은 리스트가 있다고 가정한다면.. A[0]=1이 되고, A[: 2]=[1, 2]가 됩니다. 이런 식으로 원하는 값을 가져오고, 슬라이싱 할 수 있습니다. 리스트 연산 리스트 더하기: 리스트끼리 +에 의해 합쳐지게 됩니다. [ex] A=[1,2,3]이고, B=[4,5,6] 일 때 A+B=[1,2,3,4,5,6]이 됩니다. 리스트 곱하기: 리스트는 *에 의해 반복할 수 있습니다. [ex] A=..