오구리의 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) 값이 달라진다. 한마디로 연결 상태가 동적으로..

▶신규 아이디 추천 (Python) : 2021 KAKAO BLIND RECRUITMENT (level 1) ▶문제 자세한 문제 설명은 아래 링크를 참고해주세요. https://school.programmers.co.kr/learn/courses/30/lessons/72410 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1단계 new_id의 모든 대문자를 대응되는 소문자로 치환합니다. 2단계 new_id에서 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)를 제외한 모든 문자를 제거합니다. 3단계 new_id에서 마침표(.)가 2번 이상 연속..

▶1398 - 동전 문제 ▶문제 구사과국은 동전만 사용하고, 동전의 가치는 다음과 같다. 1, 10, 25, 100, 1000, 2500, 10000, 100000, 250000, 1000000... 즉, 식으로 표현하면 K ≥ 0를 만족하는 모든 K에 대해서, 가치가 10K인 동전과 25 × 100K인 동전이 있는 것이다. 구사과국에 살고 있는 구사과는 초콜릿을 하나 구매해 5차원 세계로 이사 가려고 한다. 초콜릿의 가격이 주어졌을 때, 이를 구매하기 위해 필요한 동전 개수의 최솟값을 구해보자. 각 동전의 개수는 무한하고, 구매할 때는 정확하게 초콜릿의 가격만큼만 지불해야 한다. ▶입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 둘째 줄부터 T개의 줄에 초콜릿의 가격이 주어진다. 가격의 1015보..

▶1563 - 개근상 ▶문제 백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독특하다. 출결사항이 기록되는 출결은 출석, 지각, 결석이다. 개근상을 받을 수 없는 사람은 지각을 두 번 이상 했거나, 결석을 세 번 연속으로 한 사람이다. 한 학기가 4일이고, O를 출석, L을 지각, A를 결석이라고 했을 때, 개근상을 받을 수 있는 출결 정보는 OOOO OOOA OOOL OOAO OOAA OOAL OOLO OOLA OAOO OAOA OAOL OAAO OAAL OALO OALA OLOO OLOA OLAO OLAA AOOO AOOA AOOL AOAO AOAA AOAL AOLO ..

▶2133 - 타일 채우기 ▶문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. ▶입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. ▶출력 첫째 줄에 경우의 수를 출력한다. ▶예제 ▶힌트 아래 그림은 3×12 벽을 타일로 채운 예시이다. ▶풀이 dp를 이용해서 푸는 문제이다. N이 홀수일 때는 짝이 맞지 않기 때문에 항상 0이 된다. 그럼 N이 짝수일 때만 생각해주면 된다. 2, 4, 6일 때 규칙이 어떻게 되는지 가장 먼저 생각해주었다. n = int(input()) dp = [0 for _ in range(31)] dp[2] = 3 for i in range(4, n+1, 2): dp[i] = dp[2] * dp[i - 2] for j in range(4, i, ..

▶2655 - 가장높은탑쌓기 ▶문제 밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래에서 위로 쌓으면서 만들어 간다. 아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프로그램을 작성하시오. 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다. 밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다. 벽돌들의 높이는 같을 수도 있다. 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다. 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다. ▶입력 첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이,..

▶1328 - 고층 빌딩 ▶문제 상근이가 살고 있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼쪽에 서서 빌딩을 몇 개 볼 수 있는지 보았고, 집에 돌아오는 길에는 가장 오른쪽에 서서 빌딩을 몇 개 볼 수 있는지 보았다. 상근이는 가장 왼쪽과 오른쪽에서만 빌딩을 봤기 때문에, 빌딩이 어떤 순서로 위치해있는지는 알 수가 없다. 빌딩의 개수 N과 가장 왼쪽에서 봤을 때 보이는 빌딩의 수 L, 가장 오른쪽에서 봤을 때 보이는 빌딩의 수 R이 주어졌을 때, 가능한 빌딩 순서의 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어, N = 5, L = 3, R = 2인 경우에 가능한..

▶1256 - 사전 ▶문제 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어진 사전을 만드는 것이다. 사전에 수록되어 있는 모든 문자열은 N개의 "a"와 M개의 "z"로 이루어져 있다. 그리고 다른 문자는 없다. 사전에는 알파벳 순서대로 수록되어 있다. 규완이는 사전을 완성했지만, 동호는 사전을 완성하지 못했다. 동호는 자신의 과제를 끝내기 위해서 규완이의 사전을 몰래 참조하기로 했다. 동호는 규완이가 자리를 비운 사이에 몰래 사전을 보려고 하기 때문에, 문자열 하나만 찾을 여유밖에 없다. N과 M이 주어졌을 때, 규완이의 사전에서 K번째 문자열이 무엇인지 구하는 프로그램을 작성하시오. ▶입력 첫째 줄에 세..

▶2293 - 동전 1 ▶문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. ▶입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. ▶출력 첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다. ▶풀이 2, 3, 4번째 행은 각각 1, 2, 5에 해당하는 money를 나타낸 것이다. dp[1] dp[2] dp[3] dp[4] d..

▶2887 - 행성 터널 ▶문제 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. 행성은 3차원 좌표 위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다. 민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오. ▶입력 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌..

▶1238 - 파티 ▶문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N) 번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다. 이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라. ▶입력 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으..