문제https://www.acmicpc.net/problem/2660  🏅풀이알고리즘다익스트라자료구조인접리스트(그래프표현), 최소힙(다익스트라) 자신을 0으로 두고 자신과 연결된 노드의 dist배열을 업데이트 하면서 해결했다.결국 dist의 max를 return 한다. 예제 1번의 경우 3의 dist배열은 [1000001, 2, 1, 0,1,1]이다. return 전 0인덱스를 -1로 초기화 하므로 max(dist)는 2이다. import sysimport heapqdef dijkstra(s): dist=[1000001]*(N+1) #dist는 0부터 N까지 heap=[] visited=set() dist[s]=0 heapq.heappush(heap,(0,s)) whil..

제목https://www.acmicpc.net/problem/1504  풀이알고리즘 : 다익스트라자료구조 : 인접리스트,  최소힙 import sysimport heapqdef dijkstra(s,e): #다익스트라 알고리즘 heap=[] heapq.heappush(heap,s) #힙에 시작노드 넣기 dist[s]=0 visited.add(s) #방문처리 while heap: v1=heapq.heappop(heap) for node in Graph[v1]: #연결된 노드 들 중방문되지 않았고 기존거리보다 거쳐서가는거리가 더 작은경우 dist갱신 if node[0] is not visited and dist[node[0]]>..

문제https://www.acmicpc.net/problem/1261  풀이알고리즘BFS자료구조리스트(인접행렬) import sysfrom collections import dequedef BFS(): queue=deque() queue.append((0,0,0)) while queue: x,y,b=queue.popleft() for i in range(4): #상,하,좌,우 탐색 n_x=x+dx[i] n_y=y+dy[i] if 0 visited 업데이트if N==M==1: #1 1 0 일경우 반례처리 print(maps[0][0])else: print(visited[M-1][N-1])  덧)1..

문제https://www.acmicpc.net/problem/14002   풀이다이나믹 프로그래밍으로 풀었다.아래 문제에서 부분수열을 출력해야한다는 점만 추가되었다. https://pleasestudy-alswldi.tistory.com/174 파이썬 백준 11053번 : 가장 긴 증가하는 부분 수열문제https://www.acmicpc.net/problem/11053  풀이다이나믹 프로그래밍으로 해결했다.1. dp테이블의 모든 값을 1로 초기화 한다.2. 수열의 수를 순회한다.2-1. 그 이전의 수가 자신보다 작을 경우2-2 . 자신의pleasestudy-alswldi.tistory.com11053번에서 현재까지의 증가하는 수열을 담을 dp_result만 추가해 주었다.import sysn = int(..

문제https://www.acmicpc.net/problem/11053  풀이다이나믹 프로그래밍으로 해결했다.1. dp테이블의 모든 값을 1로 초기화 한다.2. 수열의 수를 순회한다.2-1. 그 이전의 수가 자신보다 작을 경우2-2 . 자신의 dp값과 해당 수의 dp값 +1 중 큰 값으로  dp테이블을 업데이트 한다.3. dp테이블에서 가장 큰 값을 출력한다. import sysn = int(sys.stdin.readline())sequence = list(map(int, sys.stdin.readline().split()))dp = [1] * (n+1)for i in range(len(sequence)): for j in range(i): #이전까지의 수가 현재보다 작으면 dp테이블 값 조회 ..

문제 https://www.acmicpc.net/problem/9084  🪙풀이DP로 풀었다.DP table인 coin_list는 해당 동전이 없었을때  만들수 있는 경우의 수와 만들고자 하는 돈에서 해당동전을 뺐을때 만들수있는 경우의 수의 합이다!  예를 들어 2와 5 동전으로 10을 만들고자 할 때,7을 보면, 2와 5로 7을 만들 수 있는 경우는 2로만 만들수있는 경우(0) + 7-5=2 를 만들 수 있는 경우(1) 의 합이다. (이때 2와 5로 2를 만들 수 있는 경우의 수는 마찬가지로 2로만 2를만들 수 있는경우의 수(1) + 5로 만들수 있는경우의수 (0)의 합이다) 마찬가지로 10은 2로만 10을만들수 있는 경우(1) + 10-5를 만들수 있는 경우의수 (1) 이다!  import sysT..

문제https://www.acmicpc.net/problem/1043  🤥풀이알고리즘연결요소를 탐색이라고 생각하여 바로 BFS를 떠올렸다. 자료구조people Graph 표현방식에 인접 리스트를 사용하였다. visited와 party_people는 이후 issubset을 이용하기 위해 set으로 구현하였다.  1. 파티에 함께 참여하는 사람들을 인접 리스트로 표현한다.# 예제 입력 1의 결과people= [[], [2], [1, 3, 4], [2, 4], [2, 3]]2. 진실을 알고있는 사람들과, 그와 연결되어있는모든 사람들을 방문처리한다. 3. 방문처리된 사람들이 존재하지 않는 파티만 count한다.  import sysfrom collections import dequedef BFS(target)..

문제 https://www.acmicpc.net/problem/16928  🐍풀이 최단경로문제로 BFS로 풀었다.  import sysfrom collections import dequedef find_road(): queue=deque() queue.append((1,0)) while(queue): #BFS 시작 current_location,tries=queue.popleft() visited.add(current_location) if current_location>=100 : print(tries) break ladder_or_snakes=[] for num_ladder..

문제https://www.acmicpc.net/problem/2661  🔮풀이알고리즘- 백트레킹  1. 수열에 1,2,3을 순서대로 넣는다.2. 넣을때마다 좋은 수열인지를 판단한다.2-1. N개의 수로 이루어진 수열일때 좋은 수열인지 판별하기 위해서는  N+1//2(N>1)번의 탐색이 필요하다. (길이에 따라 0(len 1) 1 1 2 2 3 3...)2-2. 좋은 수열을 판단할때는 인덱스 슬라이싱을 사용한다. 3. 좋은 수열일 경우 다음 수에 1을 넣는다.4. 1,2,3 모두 들어갈 수 없는 경우는 이전의 결과를 증가시킨다.5. 수열의 길이가 N을 만족한다면 종료한다.  import sysdef make_progression(i): #i는 추가할 번호 (1,2,3) i+=1 if i>3:..

문제 https://www.acmicpc.net/problem/9205  🍺풀이자료구조 이차원 리스트를 활용해서 집, 편의점, 페스티벌의 좌표를 저장했다. visited함수는 set에 튜플을 저장했다. 알고리즘 BFS를 사용했다. import sysfrom collections import dequedef move(): queue=deque() queue.append(maps[0]) #집을 queue에 넣음 visited.add(tuple(maps[0])) #방문처리 while(queue): x,y=queue.popleft() visited.add((x,y)) #방문처리 if x==maps[n+1][0] and y==maps[n+1][1]: ..