이 영역을 누르면 첫 페이지로 이동
butter_shower 블로그의 첫 페이지로 이동

butter_shower

페이지 맨 위로 올라가기

butter_shower

알고리즘 Algorithm

  • butter_shower
[Algorithm] 투포인터(Two Pointer) 알고리즘

[Algorithm] 투포인터(Two Pointer) 알고리즘

2021.04.28
알고리즘 문제를 풀다보면 종종 나오는 투포인터 알고리즘! 막 꼬여가지고 ㅋㅋㅋ 저도 중간에 제대로 못짜고 그러는 경우가 많은데요, 많은 코딩테스트 문제에 등장하는 것은 아니지만 잊을만하면 종종 등장하는 투포인터 알고리즘에 대해 알아봅시다! 투포인터 (Two Pointers) 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘 정렬되어있는 두 리스트의 합집합에도 사용됨. 병합정렬(merge sort)의 counquer 영역의 기초가 되기도 합니다. 예제 문제 - 특정한 합을 가지는 부분 연속 수열 찾기 투포인터 알고리즘의 대표적인 문제입니다. 어떤 숫자들의 리스트가 주어질 때, 해당 리스트의 연속 수열의 합이 특정 값을 가지는 것을 확인하는 문제입니다. 시작점과 끝점이 첫..
[Algorithm] DFS와 BFS 기본 개념 및 관련 문제들 (python)

[Algorithm] DFS와 BFS 기본 개념 및 관련 문제들 (python)

2021.04.23
시작하기에 앞서.. 그래프의 표현 방법 그래프는 표현하는 방법을 크게 두가지로 나눌 수 있습니다. 하나는 인접 행렬, 다른 하나는 인접 리스트입니다. 1. 인접 행렬 (Adjacency Matrix) 2차원 배열로 그래프의 연결관계를 표현하는 방식입니다. INF = float('inf') graph = [ [0, 7, 5], [7, 0, INF], [5, INF, 0] ] 2. 인접 리스트 (Adjacency List) 리스트로 그래프의 연결관계를 표현하는 방식입니다. 저의 경우에는 딕셔너리나 collections에 있는 defaultdict를 사용합니다. 둘이 똑같이 키-값의 구조라서 빠른 접근이 가능하다는 점에서 사용하기 편리한 것 같습니다ㅎㅎ 아래는 defaultdict를 사용한 방법입니다. gra..
[Algorithm] 트라이(Trie)와 관련 문제들 (Python)

[Algorithm] 트라이(Trie)와 관련 문제들 (Python)

2021.04.11
트라이란? 문자열을 효과적으로 탐색하기 위한 자료구조로, 문자열을 순차탐색하는 방식이 아닌 트리로 접근하기 위해 만들어진 자료구조입니다. 주로 Prefix Tree, digital search Tre, retrieval tree라고도 불리는데, retrieval tree의 trie를 따와 트라이라고 일반적으로 불립니다. 트라이는 문자열을 key로 사용하는 동적은 set 또는 연관배열을 저장하는 트리의 확장된 구조입니다. 문자열을 탐색할 때 단순하게 하나씩 비교하지 않고 key로 노드들을 탐색해나가기때문에 매우 효율적이라는 장점이 있습니다. 단, 빠르게 탐색 가능하지만 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점이 있습니다. 위 사진을 보시면 아..
[BOJ/백준] 13458. 시험감독

[BOJ/백준] 13458. 시험감독

2020.10.17
문제 링크 : https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 문제 총 N개의 시험장이 있고, 각각의 시험장마다 응시자들이 있다. i번 시험장에 있는 응시자의 수는 Ai명이다. 감독관은 총감독관과 부감독관으로 두 종류가 있다. 총감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 B명이고, 부감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 C명이다. 각각의 시험장에 총감독관은 오직..
[LeetCode] 743. Network Delay Time - BFS

[LeetCode] 743. Network Delay Time - BFS

2020.10.15
문제 링크 : https://leetcode.com/problems/network-delay-time/ Network Delay Time - 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 743. Network Delay Time There are N network nodes, labelled 1 to N. Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is ..
[LeetCode] 542. 01 Matrix - BFS

[LeetCode] 542. 01 Matrix - BFS

2020.10.15
문제 링크 : https://leetcode.com/problems/01-matrix/ 01 Matrix - 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 01 Matrix - LeetCode Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell. The distance between two adjacent cells is 1. Example 1 Input: [[0..
[KickStart] Round F 2020 - ATM Queue

[KickStart] Round F 2020 - ATM Queue

2020.09.29
문제 링크 : codingcompetitions.withgoogle.com/kickstart/round/000000000019ff48/00000000003f4ed8 Kick Start - Google’s Coding Competitions Hone your coding skills with algorithmic puzzles meant for students and those new to coding competitions. Participate in one round or join them all. codingcompetitions.withgoogle.com Problem There areNpeople numbered from 1 toN, standing in a queue to withdraw mon..
[백준/BOJ] 4353. 문자열 제곱

[백준/BOJ] 4353. 문자열 제곱

2020.09.29
문제 링크 : www.acmicpc.net/problem/4354 4354번: 문자열 제곱 알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다� www.acmicpc.net 문제 알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다면, 음이 아닌 정수의 제곱도 정의할 수 있다. a^0 = "" (빈 문자열) a^(n+1) = a*(a^n) 문자열 s가 주어졌..
[백준/BOJ] 4358. 생태학

[백준/BOJ] 4358. 생태학

2020.09.29
문제 링크 : www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 문제 생태학에서 나무의 분포도를 측정하는 것은 중요하다. 그러므로 당신은 미국 전역의 나무들이 주어졌을 때, 각 종이 전체에서 몇 %를 차지하는지 구하는 프로그램을 만들어야 한다. 입력 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가..
[프로그래머스] 후보키 (python에서 pandas를 활용한 방법)

[프로그래머스] 후보키 (python에서 pandas를 활용한 방법)

2020.09.15
문제 링크 : programmers.co.kr/learn/courses/30/lessons/42890 코딩테스트 연습 - 후보키 [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]] 2 programmers.co.kr 문제 프렌즈대학교 컴퓨터공학과 조교인 제이지는 네오 학과장님의 지시로, 학생들의 인적사항을 정리하는 업무를 담당하게 되었다. 그의 학부 시절 프로그래밍 경험을 되살려, 모든 인적사항을 데이터베이스에 넣기로 하였고, 이를 위해 정리를 하던 중..
[프로그래머스] 가장 먼 노드 - BFS/그래프

[프로그래머스] 가장 먼 노드 - BFS/그래프

2020.09.15
문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 문제 n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 so..
[Algorithm] 인프런 강좌 따라하며 배우는 알고리즘! 73장~75장

[Algorithm] 인프런 강좌 따라하며 배우는 알고리즘! 73장~75장

2020.07.08
오늘도 한다 알고리즘!!! 73장. 최대힙(priority_queue : 우선순위 큐) 최대힙은 완전이진트리로 구현된 자료구조입니다. 그 구성은 부모 노드 값이 왼쪽 자식과 오른쪽 자식 노드의 값보다 크게 트리를 구성하는 것입니다. 그렇개 하면 트리의 루트(root) 노드는 입력된 값들 중 가장 큰 값이 저장되어 있습니다. 예를들어 5 3 2 1 4 6 7 순으로 입력되면 최대힙 트리는 아래와 같이 구성됩니다. 최대힙 자료를 이용하여 다음과 같은 연산을 하는 프로그램을 작성하세요. 1) 자연수가 입력되면 최대힙에 입력한다. 2) 숫자 0이 입력되면 최대 힙에서 최댓값을 꺼내어 출력한다. (출력할 자료가 없으면 -1를 출력한다.) 3) -1이 입력되면 프로그램을 종료한다. 입력 첫 번째 줄부터 숫자가 입력..
  • 최신
    • 1
    • 2
    • 3
  • 다음

정보

butter_shower 블로그의 첫 페이지로 이동

butter_shower

  • butter_shower의 첫 페이지로 이동

검색

메뉴

  • All Categories
  • About Me
  • Guest Book

카테고리

  • 전체보기 (223)
    • 💫 주인장 이야기 (17)
    • 🌱 와글와글뻘글 (27)
    • IT Trends (11)
    • 주인장 일상 (0)
    • 📒 내 마음대로 독서 서평 (12)
    • 머신러닝 꿈나무 (30)
      • 기본 개념 (6)
      • Hands-on! (5)
      • Paper Review (5)
      • 캐린이의 Kaggle (1)
    • 알고리즘 Algorithm (33)
      • PS (8)
    • Computer Engineering (75)
      • Python (8)
      • Cloud Computing (9)
      • C (9)
      • C++ (0)
      • Java (6)
      • Django 장고 (4)
      • 임베디드 시스템 (10)
      • 병렬 처리(Parallel Processing) (9)
      • 데이터 통신 Data communication (4)
      • 유닉스 시스템 (Unix System) (3)
      • GitHub (1)
      • 마이크로 프로세서 (micro processor) (1)
      • 데이터 마이닝 (1)
    • Error Note 🚨 (3)
    • 영어 공부 (6)
      • Live Academy (6)
    • HOBBY (2)
      • Film Log (2)

최근 글

정보

_rian의 butter_shower

butter_shower

_rian

나의 외부 링크

  • Github
  • Facebook
  • Instagram
  • LinkedIn
  • Twitter

블로그 구독하기

  • 구독하기
  • RSS 피드

방문자

  • 전체 방문자
  • 오늘
  • 어제

티스토리

  • 티스토리 홈
  • 이 블로그 관리하기
  • 글쓰기
Powered by Tistory / AXZ. © _rian. Designed by Fraccino.

티스토리툴바