본문 바로가기

Dev/알고리즘

(8)

[python] zip을 이용한 단어 비교 문자열에 관한 알고리즘을 풀 경우 아래와 같은 문제가 출제되는 경우가 있다. "dog"라는 문자열에서 한 개의 문자만 바꾸어 "cog"가 될 수 있는가? 위 문제를 풀 경우 보통 for문을 2번 사용하여 비교할 것이다. 아래와 같이 zip을 활용하면 간단히 해결할 수 있다. s1 = "dog" s2 = "cog" diff = 0 for a,b in zip(s1,s2): if a != b: diff +=1 print (f'{s1=} {s2=} {diff=}') zip 클래스를 보면 아래와 같이 리스트를 넣었을 때 각 요소를 묶어 돌려준다. 문자열 위치비교시 해당 방법을 사용하면 유용할 것 같다.

[최소 힙] 파이썬 코드 및 그림 설명 Python 3.10 파이썬에서 힙 사용 예제입니다. import heapq N = [3,6,1,8,2,4,11,9] heap = [] for i in N: heapq.heappush(heap, i) print (f'{heap=}') # 실행결과 heap=[3] heap=[3, 6] heap=[1, 6, 3] heap=[1, 6, 3, 8] heap=[1, 2, 3, 8, 6] heap=[1, 2, 3, 8, 6, 4] heap=[1, 2, 3, 8, 6, 4, 11] heap=[1, 2, 3, 8, 6, 4, 11, 9] N 배열의 요소를 하나씩 heap에 추가하는 예제입니다. 위의 각 요소를 실행한 결과를 그림으로 보면 아래와 같습니다. 최소 힙이기 때문에 낮은 숫자가 위에 위치하여야 하며, 부모 노..

[dijkstra] 백준 1753 파이썬 import sys import heapq input = sys.stdin.readline INF = int(1e9) N, M = map(int, input().strip().split()) start = int(input()) graph = [[] for _ in range(N+1)] distance = [INF]*(N+1) for i in range(N): a, b, c = map(int, input().strip().split()) graph[a].append((b,c)) def dijkstra(start): q = [] heapq.heappush(q, (0, start)) distance[start]=0 while q: dist, now = heapq.heappop(q) if distance[no..

[BFS] 백준 7576 토마토 설명 (python) BFS를 가장 잘 보여주는 대표적인 문제라고 생각됩니다. 문제는 아래와 같습니다. 토마토 밭이 주어지고 그중 1로 표시된 곳은 익은 토마토가 있고, 0으로 표시된 곳은 익지 않은 토마토가 있습니다. 하루가 지날때마다 익은 토마토 상.하.좌.우의 토마토가 익게 됩니다. 주어진 토마토밭의 토마토가 모두 익는 데까지 걸리는 일자를 구하는 문제입니다. 위의 그림에서 1일의 좌측상단에 1로 표시된 곳이 익은 토마토가 있는 곳이고 문제의 설명과 같이 상하좌우로 점점 익으며 7일에 모두 익게 됩니다. BFS에서 사용되는 큐와 함께 보면 더 이해가 쉽게 됩니다. 현재 익은 토마토의 좌표를 큐에 넣어주는 작업을 먼저 합니다. 이후 큐에서 하나씩 꺼내 상.하.좌.우를 살펴 익지 않은 토마토가 있다면 해당 좌표를 큐에 넣어..

[DFS] 기본 그래프에서 노드와 연결된 간선 정보를 알려주었을 경우 방문 여부를 알 수 있는 배열을 같이 사용하여 해결한다. 1차원 배열로 graph를 구성하였을 때 구현 def dfs(graph, v, visited): visited[v] = True print (v, end=' ') for i in graph[v]: if not visited[v]: dfs(graph, i, visited) 2차원 배열로 graph를 구성하였을 때 구현 def dfs(v): visited[v] = 1 print (v, end=' ') for i in range(1,N+1): if visited[i] == 0 and graph[v][i] == 1: dfs(i) 바둑판과 같이 직사각형 형태의 값들이 주어지는 경우 상하좌우로 이동하는 경..

계산 시간 (백준 10818) 알고리즘 계산 시간 백준 10818 문제를 풀다가 계산 시간에 대해 알아보았다. 10818번 문제는 단순하다.입력받은 값 중 최대, 최소 값을 구하는 문제 하지만 실제로 풀고 제출을 하면 의문점이 생긴다.계산시간이 왜 이렇게 오래 걸리지? 제일 처음 제출한 소스코드는 아래와 같다. #include using namespace std; int main(){ int t,min=1000000,max=-1000000,num; scanf("%d", &t); while(t--){ scanf("%d",&num); if(min>num){ min = num; } if(max> t >> num; min = max = num; t--; while(t--){ cin >> num; min = min>num ? num : min..

Scanf에 대하여 (백준 10953) scanf 알아보기 C언어를 처음 배울 때 표준입력으로 scanf를 사용한다. 당시에는 단순히 scanf("%d", &a); 수준의 scanf만 사용하였다. 하지만, 10953번 문제를 풀면서 scanf 함수에 대해 더 깊게 알아보았다. int scanf( const char *format, ...); 1. scanf 는 \n, ' ', \t 기준으로 문자를 분리 #include using namespace std; int main(){ int a,b; scanf("%d%d",&a,&b); printf("%d %d\n",a,b); return 0; }입력 : 4 (공백) 5입력 : 4 (Tab) 5입력 : 4 (엔터) 5출력 : 4 5 2. 단일문자로 구분 scanf("%d,%d",&a,&b); scan..

소수 구하기 (에라토스테네스의 체) 소수 구하기 - 에라토스테네스의 체소수 구하기 문제는 2분류로 나눌 수 있다. 1. 소수의 개수를 구하는 문제2. 소수 구하기 문제 소수를 구하는 방법에 대해 찾아보던 중 새로운 방법을 알게 되었다. 에라토스테네스의 체소수는 1과 자기 자신으로만 나누어 떨어지는 수를 말한다.즉, 2의 배수, 3의 배수, n의 배수는 소수가 될 수 없다. 에라토스테네스는 다음과 같이 소수를 구하였다.예를 들어, 20이하의 수에서 소수를 구해 본다. 1. 2의 배수를 제외한다.2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2. 3의 배수를 제외한다.2 3 5 7 9 11 13 15 17 19 3. 5의 배수를 제외한다.2 3 5 7 11 13 17 19 4. 20 이하의 수에서 소수..

이전 1 다음

티스토리툴바