오구리의 DevLog

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. 2022.12.09 - [컴퓨터공학/알고리즘2] - [알고리즘2] Shortest Paths on Weighted Digraphs [알고리즘2] Shortest Paths on Weighted Digraphs 복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Content dhalsdl12.tistory.com ▶Seam Carving 이미지의 크기 조절 시 중요한 부분 자동 인식해 최대한 보존하며 ..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Contents WordNet Outcase SCA & SAP WordNet과 outcaset 탐지 구현 ▶WordNet 정점(synset) : 유사어(synonym)의 집합(set) v -> w 간선 : v is a w 관계 (hyponym -> hypernym) 'apple' is an edible fruit 'banana' is an edible fruit WordNet의 특성 Cycle이 없다. (DAG, Directed Acyclic Graph) Root는 하나이다. (entity) 부모가 둘 이상인 경우도 있고, 자..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. import copy import random from queue import PriorityQueue class Board: def __init__(self, tiles): self.n = len(tiles) self.tiles = copy.deepcopy(tiles) self.twinBoard = None # Compute Hamming distance self.hammingDistance = 0 goal = 0 for rowId, row in enumerate(tiles): for colId, t in enumerate(r..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Contents Binary Heap을 사용한 PQ의 구현 Priority Queue 사용 애플리케이션 공통적인 특성 Slider Puzzle and A* Search with PQ ▶Priority Queue insert() 1. complete binary tree 형태를 유지한다. 2. heap order를 유지한다. 3. ~logN 시간에 새 원소를 추가한다. insert(k)하는 새 값을 k라고 할 때, k를 tree 가장 마지막에(배열 끝에) 추가한다. k를 부모 노드와 비교해 heap-order(부모 >= 자식) ..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Collinear Points 4개 이상 점 연결하는 maximal한 직선을 모두 찾는 코드이다. N개 점의 (x, y) 좌표가 입력으로 주어졌을 때, 4개 이상 점을 연결하는 maximal한 직선을 모두 찾으면 된다. ▶Collinear Points 탐지방법 하나하나 비교하면서 하는 Brute Force방식을 사용할 수 있다. 하지만 시간 복잡도 측면에서 좋지 못한 코드가 된다. 정렬을 활용한 더 효율적인 방법을 사용하면 된다. 각 점 p에 대해, p가 다른 모든 점과 이루는 기울기를 계산해, 기울기를 key로 정렬한다. 정..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Contents Bottom-up Merge Sort Sorting Complexity Stability of Sorting Quick Select Duplicate Keys and 3-way Partitioning ▶Merge Sort 인접한 두 조각끼리 Merge(정렬된 순서로 병합)을 반복한다. 총 N개 원소를 병합한다면, 이들을 순서에 맞게 차례로 결과 배열에 옮겨 담으므로 ~N회 작업이 필요하다. 이러한 작업을 ~log(N)회 반복해야 한다. 입력 데이터 크기가 N이라면 결과를 옮겨 담을 ~N의 추가 공간도 필요하다...

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶프로그램 입출력 조건 xy 좌표계에 속한 점의 list(points)를 입력으로 받는 함수 정의 points는 tuple (x, y)의 리스트임 (예: [(3,2), (4,-1), (0,0), (-2,2)]) points에 속한 점은 모두 좌표가 서로 다름 def grahamScan(points): 위 함수는 Graham’s Scan을 사용해 convex hull에 속한 점의 좌표를 구한 후 입력과 같은 형식으로 반환 최초로 convex hull에 포함하는 점 p는 y 값이 가장 작은 점 중 x 값이 가장 큰 점 이후에 con..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Contents Insertion Sort h-Sort Shell Sort Shuffle Sort Convex Hull (Tight boundarry 찾기 위해 정렬 방법 적용) ▶Insertion Sort 이미 정렬된 a[0] ~ a[i-1]에 a[i]를 적절한 위치 (정렬되었을 때의 위치) 찾아 추가한다. 그 결과 a[0] ~ a[i]까지 정렬된 상태가 된다. 입력 데이터의 상태 대소 비교 횟수 swap 횟수 (best case) 이미 정렬된 상태 N - 1 0 (worst case) 반대 방향으로 정렬된 상태 ~N^2 /..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Percolate N × N 개의 객체가 격자를 이룬다 (그림 참조) 각 객체는 두 상태(열림, 닫힘) 중 하나를 가질 수 있으며 가장 윗줄이 가장 아랫줄에 연결되었다면 (열린 격자 통해 이동 가능) 이 격자는 percolate 한다고 한다. ▶simulation 방법 개요 N × N 개의 객체를 닫힌 상태로 초기화 닫힌 객체 중 하나를 (임의로 선정해) 열린 상태로 바꾸고 percolate 하는지 확인 위 -> 아래로 percolate 할 때까지 반복 percolate 할 때 열려 있는 객체의 비율(=열린 객체 수 / (N ..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Contents Union Find Quick Find Quick Union ▶Union Find N개 객체가 주어진다. 0 ~ (N-1)까지 정점(vertex)으로 표현된다. 간선(edge)이 없는 상태에서 시작한다. 2개의 명령 수행이 필요하다. Union(a, b) : 점 a와 b를 간선으로 연결 Connected(a, b) : a와 b를 연결하는 경로 존재하는지 True/False로 응답한다. (Find라고도 한다.) 값이 Union 됨에 따라서 Connected(Find) 값이 달라진다. 한마디로 연결 상태가 동적으로..

▶신고 결과 받기 - 2022 KAKAO BLIND RECRUITMENT (level 1) ▶풀이 신고 당한 횟수가 k번 이상이면 신고한 사람이 몇번이나 신고 성공했는지 출력해주면 된다. 그에 맞는 dictionary를 생성해서 id값들을 넣어준다. result는 사람들이 몇번이나 신고 당했는지 체크해주는 dictionary이고, 신고 횟수를 1씩올려주면 된다. 마지막 for문에선 그 값에 해당하는 key값을 가지고 answer의 값을 1씩 올려주면 된다. 사실 이 문제를 글쓰는 날 푼 문제가 아니라 한참 전에 푼 문제이다. 그래서 설명 자체가 너무 별로일 수도 있다.ㅠㅠ 다음에 다시 풀어보고 설명을 제대로 적어야겠다. def solution(id_list, report, k): answer = [0] ..

▶6086 - 최대 유량 ▶문제 농사꾼 존은 소들이 충분한 물을 마시길 원했다. 그래서 농장에서 우물에서 외양간을 잇는 N개의 배수관의 지도를 만들기로 했다. 존은 아주 다양한 크기의 배수관들이 완전히 우연한 방법으로 연결돼있음을 알았다. 존은 파이프를 통과하는 유량을 계산하고 싶다. 두 개의 배수관이 한 줄로 연결돼 있을 때 두 관의 유량 중 최솟값으로 흐르게 된다. 예를 들어 용량이 5인 파이프가 용량이 3인 파이프와 연결되면 한 개의 용량 3짜리 파이프가 된다. +---5---+---3---+ -> +---3---+ 게다가, 병렬로 연결돼 있는 배수관들은 각 용량의 합만큼의 물을 보낼 수 있다. +---5---+ ---+ +--- -> +---8---+ +---3---+ 마지막으로, 어떤 것에도 연..

▶2098 - 외판원 순회 ▶문제 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP)라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 ..

▶11404 - 플로이드 ▶문제 n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오. ▶입력 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 1..

▶2294 - 동전 2 ▶문제 n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. ▶입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다. ▶출력 첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다. ▶풀이 이번 문제도 학교 알고리즘 1 시간에 교수님이 풀어보라고 주신 문제이다...

▶12865 - 평범한 배낭 ▶문제 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자. ▶입력 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(..

▶2580 - 스도쿠 ▶문제 스도쿠는 18세기 스위스 수학자가 만든 '라틴사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다. 또한 위쪽 가운데 위치한..

▶7662 - 이중 우선순위 큐 ▶문제 이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다. 정수만 저장하는 이중 우선순위 큐 Q가 있다고 가정하자. Q에 저장된 각 정수의 ..

▶11401 - 이항 계수 3 ▶문제 자연수 n과 정수 k가 주어졌을 때 이항 계수 nCk를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. ▶입력 첫째 줄에 n과 k가 주어진다. (1 ≤ n ≤ 4,000,000, 0 ≤ k ≤ n) ▶출력 nCk를 1,000,000,007로 나눈 나머지를 출력한다. ▶풀이 #페르마의 소정리 #(a/b)%p # = (a * b^-1) % p # = (a * b^-1 * b^(p-1)) % p # = (a * b^(p-2)) % p # = (a % p) * (b^(p-2) % p) % p def pow(a,b): if b == 0: return 1 if b % 2 == 1: return (pow(a, b//2)**2*a)%p else: return..

▶1305 - 광고 ▶문제 세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다. 전광판에는 같은 내용의 문구가 무한히 반복되어 나온다. 또, 전광판의 크기는 전광판에서 한 번에 보이는 최대 문자수를 나타낸다. 만약 전광판의 크기가 L이라면, 한 번에 L개의 문자를 표시할 수 있는 것이다. 광고업자는 최대한의 광고효과를 내기 위해서 길이가 N인 광고를 무한히 붙여서 광고한다. 예를 들어, 광고 업자 백은진이 광고하고 싶은 내용이 aaba 이고, 전광판의 크기가 6이라면 맨 처음에 보이는 내용은 aabaaa이다. 시간이 1초가 지날 때마다, 문자는 한 칸씩 옆으로 이동한다. 따라서 처음..