본문 바로가기
반응형

코딩 이야기

 (100)
백준 1342번: 행운의 문자열 파이썬코드(백트래킹) s = input() s = list(s) su = len(s) count = 0 alphabet = [0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0] for i in range(len(s)): alphabet[ord(str(s[i])) - 97] += 1 def backtracking(l, p): global count if l == 0: count += 1 for i in range(26): if alphabet[i] > 0 and i != p: alphabet[i] -= 1 backtracking(l-1, i) alphabet[i] += 1 else: pass backtracking(su, -1) print(count)
백준 1717번: 집합의 표현 파이썬 코드(유니온파인드, Union-find) import sys n, m = map(int, sys.stdin.readline().split()) parent = [i for i in range(n+1)] def find(x): if parent[x] == x: return x return find(parent[x]) def union(x, y): x = find(x) y = find(y) if x != y: if y > x: parent[y] = x else: parent[x] = y return def same(x, y): x = find(x) y = find(y) if x == y: print("YES") else: print("NO") return for i in range(m): a,b,c = map(int, sys.stdin.readli..
백준 4485번: 녹색 옷 입은 애가 젤다지? 파이썬 코드(다익스트라) import sys import heapq INF = sys.maxsize x = [0,0,-1,1] y = [-1,1,0,0] count = 0 while 1: n = int(sys.stdin.readline()) count += 1 visited = [[0 for _ in range(n)]for _ in range(n)] if n == 0: break graph = [] dist = [[INF for _ in range(n)] for _ in range(n)] for i in range(n): temp = list(map(int, sys.stdin.readline().split())) graph.append(temp) heap = [] heapq.heappush(heap, [graph[0][0],[0..
백준 1261번: 알고스팟 파이썬 코드(다익스트라) import sys import heapq INF = sys.maxsize x = [0,0,-1,1] y = [-1,1,0,0] n,m = map(int, sys.stdin.readline().split()) visited = [[0 for _ in range(n)]for _ in range(m)] graph = [] dist = [[INF for _ in range(n)] for _ in range(m)] for i in range(m): temp = list(input()) temp = [int(i) for i in temp] graph.append(temp) heap = [] heapq.heappush(heap, [graph[0][0],[0,0]]) while heap: cost, now = hea..
파이썬 투포인터 알고리즘 사용하기(Two pointer) 투포인터 알고리즘? 투포인터 알고리즘은 이름에서 알 수 있듯 2개의 포인터를 사용하는 알고리즘이다. 슬라이딩 윈도우 알고리즘과도 많이 비교가 되는데, 그 이유는 밑에서 설명하겠다. 투포인터 알고리즘은 배열의 인덱스를 가르키는 2개의 포인터를 설정하고, 이를 옮겨가면서 내가 원하는 값을 찾는 알고리즘이다. 투포인터는 간단하기도 해서 그냥 바로 예시 상황을 보고 이해하는게 빠를 것이다. 상황 1. 길이가 5인 배열이 하나 있다. 이 안에는 임의의 10미만의 정수가 할당되어있다. 2. 이 배열에서 어느 한 부분을 잘라서 그 부분의 합이 15가 되는 부분을 찾고 출력하라. 1 4 2 5 3 6 순서로 보시면 된다. (S = 보라색포인터와 파란색포인터 사이의 값의 합) 1. 보라색 포인터와 파란색 포인터가 둘다 ..
파이썬 다익스트라 알고리즘 사용하기 다익스트라 알고리즘 다익스트라 알고리즘은 탐색 알고리즘으로 최단경로를 찾는 알고리즘이다. 이름이 다익스트라인 이유는 이 다익스트라 알고리즘을 만든 사람의 이름이 '에츠허르 데이크스트라'라서 라고한다. 이 알고리즘의 핵심은 가중치가 있는 그래프에서 비용(cost)가 가장 적은 경로를 찾는데에 있다. 다익스트라 알고리즘이 네비게이션 같은 GPS 소프트웨어 많이 활용된다. 초기의 다익스트라 알고리즘은 O(V^2)의 시간복잡도를 가졌었지만, 이후 우선순위 큐로 인한 개선으로 O((V+E)LogV)를 가지게 되었다. 과정 (그래프는 인접행렬이든 인접리스트이든 상관없다. 허나 글에선 편의를 위해 인접행렬 사용) 상황은 보라색 정점에서 주황색 정점까지 가야하는데 가장 적은 비용으로 가야한다. (보라색 정점 = 0, ..
파이썬으로 스택 알아보고 구현하기 서론 스택은 자료구조 중 대표적인 선형구조이다. 우리가 흔히 게임이나 일상생활에서 "스택 쌓였다"라는 표현을 사용하는데, 완전히는 아니더라도 어느 정도 비슷한 개념을 가지고 있다. 스택 스택은 선형구조의 자료구조로서 일상생활 속에서 꽤나 많이 볼 수 있다. 예를 들어 프링글스 과자를 생각하면 쉽다. 우리가 프링글스를 먹을 때 가장 먹게 되는 감자칩은 가장 마지막에 넣은 감자칩이지 않을가? 이렇게 가장 늦게 넣은 것이 가장 먼저 나온다는 개념을 가졌다면 스택이다. 다른 예시로는 종이컵 더미가 있겠다. 종이컵 더미도 가장 늦게 쌓은 종이컵이 가장 먼저 나오니 말이다. 이를 가장늦게 넣은 것이 가장 먼저 나온다고 해서, 후입선출이라부른다. 스택은 한 곳에서 삽입과 삭제가 일어난다. 나중에 서술할 큐라는 다른 ..
메모리 영역(코드영역, 데이터영역, 힙영역, 스택영역) 서론 메모리 영역은 총 4가지로 나뉜다.(BSS까지 포함하면 5가지) 그리하여, 코드 영역, 데이터 영역, 힙 영역, 스택 영역이 무엇인지 알아보고 각각 어떤 특장을 지니는 지 서술하려한다. 메모리 영역 프로그램이 실행하려면, 당연히 메모리의 공간을 할당을 받아야하고 이 공간을 메모리 영역이라 지칭한다. 코드 영역 이름 그대로 우리가 작성한 코드를 저장하는 공간이다. 텍스트영역이라고도 불리며, 이 공간은 컴파일 할 때 Read-Only이다. 어찌보면 당연한데, 우리가 파이썬을 실행할 때 컴파일할 당시에 코드로 실행하지, 컴파일한 후에 코드를 수정해도 적용되지 않는 이유가 이 때문이다. 데이터 영역 데이터 영역은 전역변수, 정적변수, 배열, 구조체를 저장한다. 이러한 것들은 프로그램이 실행되는 와중에 값이..
반응형

티스토리툴바