본문 바로가기

전체 글41

[백준 11404번] 플로이드 (파이썬 풀이) https://www.acmicpc.net/problem/11404 문제 문제 이해 Dijkstra로 풀려고 했는데, 시간초과가 났다. 문제의 이름처럼 플로이드 - 위셜 알고리즘을 써서 풀어야 하나보다. chatGPT 에게 그게 뭐냐고 물어봤다. 대답은 잘한다. 코드로 나타내면 이해가 쉽다. 모든 노드 쌍간의 최단경로를 한번의 구할 수 있고 음의 가중치도 가능하다는 장점이 있다. graph는 어떻게 나타내느냐 하면, graph = [ [0, 1, 1, inf, inf], [1, 0, 1, 1, inf], [1, 1, 0, inf, 1], [inf, 1, inf, 0, 1], [inf, inf, 1, 1, 0] ] 이런식으로 나타낸다고 한다. 문제에 적용해 보자. 문제 풀이 import sys input .. 2023. 5. 5.
[백준 1753번] 최단경로 (Python 풀이) https://www.acmicpc.net/problem/1753 문제 문제 이해 먼저, 문제의 제목처럼 최단경로를 구하는 문제이다. 선뜻, BFS (너비우선탐색)이 생각나지만, 이 문제는 가중치가 있다. 1, 0 으로 이루어진 가중치라면 BFS풀이가 가능하나, 1을 초과하는 가중치가 있기 때문에 이 문제는 BFS로 풀지 못한다. 즉, Dijkstra (다익스트라) 알고리즘을 사용한다. 첫째 줄에는 노드 수, 간선 수가 나온다. 여기서 간선이라고 하는 것은 가중치가 있고 방향이 있는 화살표이다. (양쪽을 향하는 화살표가 아니란 말이다.) 예제 입력을 그림으로 나타내면 저런 형태를 가진다. 풀이 방법 1. 먼저 간선(v)과 가중치(e)가 들어가는 edge 배열을 만든다.위의 예제 입력의 edge 배열은ed.. 2023. 5. 4.
[백준 15663번] N과 M (9) {Python 풀이} 이 문제는 itertools 모듈의 permutations 함수를 이용하여 해결할 수 있습니다. permutations 함수는 주어진 iterable에서 지정된 길이의 순열을 구하는 함수입니다. from itertools import permutations import sys input = sys.stdin.readline n, m = map(int, input().split()) numbers = list(map(int, input().split())) # 주어진 수열을 사전순으로 정렬합니다. numbers.sort() # permutations 함수를 이용하여 길이가 M인 순열을 구합니다. # set을 이용하여 중복되는 수열을 제거합니다. result = set(permutations(numbers,.. 2023. 5. 2.
KMP 알고리즘 KMP 알고리즘은 빠른 문자열 검색을 돕는 알고리즘이다. 찾고자 하는 문자열을 pattern 이라고 하고 모든 문장을 all string 라고 하자. KMP 알고리즘을 구현하기 위해 해야할 것이 있다. 1. Pattern 문자열을 이용해 pi(파이)배열을 만들어야 한다. 2. pi 배열을 이용해 빠른 문자열을 검색해준다. pi배열 이란, Pattern 문자열에 있는 접두사 (Prefix) 와 접미사 (Suffix)가 같아 지는 최대 길이를 나열해 놓은 배열이다. 말로 설명하지니 좀 어려우므로 아래 그림을 통해 확인해보자. 예를 들어, pattern이 "abcdabc" 라면 단어의 길이가 7인데, 1개씩 늘려가며 접두사와 접미사가 겹치는 최대 길이를 나타내 보면, pi배열은 [0, 0, 0, 0, 1, 2.. 2023. 4. 26.
리눅스마스터 2급 2차 합격 후기! 2023년 3월 11일 제 2301회 리눅스마스터 2급 2차 시험을 봤다. 준비 기간은 넉넉하게 1달? 정말 빡세게 한건 일주일이었다. 시험장에 가면 저런 시험지와 OMR카드를 준다. 준비물: 컴싸, 볼펜, 신분증, 수검표 수검표는 따로 출력 안해갔고, 핸드폰에 캡쳐해놓은 것이 있었는데, 핸드폰 꺼야되니까 포스트잇을 주시면서 수험번호 미리 적어놓으라고 하셨다. 그리고 컴싸 없는 사람 있으면 빌려준다고도 하셨다. 나는 그것도 모르고 시험 시작 30분전에 마트에서 300원 주고 샀다 ㅋㅋ 준비한대로 아는 것도 많이 나왔고 보기 4개중에 2개가 뭐가 정답인지 헷갈리는 것도 많았다.. 준비 부족이었나보다.. 100분 시험에 80문제이다! 준비과정은 이렇다. 먼저, 이기적 출판사에 있는 책을 샀다. 굳이 필요 없.. 2023. 3. 16.
[LeetCode] 1026. Maximum Difference Between Node and Ancestor (Python) 1026번 문제링크 https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/description/ Maximum Difference Between Node and Ancestor - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제설명 입력: TreeNode 출력: 정수값 트리의 같은 path에서 값이 가장 큰 것과 작은 것의 차이를 구하는 문제 *같은 path란 - 같은 조상을 가.. 2022. 12. 9.

티스토리툴바