본문 바로가기

개발68

자료구조 - 힙(Heap) 힙(Heap) 이란 힙은 특별한 종류의 이진트리인데, 주로 우선순위 큐(Priority Queue)를 구현하는 데 사용됩니다. 힙은 다음과 같은 특성을 가지고 있습니다. 1. 부모 노드의 값이 항상 자식 노드의 값보다 크거나 작음(최대 힙 또는 최소 힙). 2. 완전 이진 트리(Complete Binary Tree) 구조를 가짐. 이는 트리의 모든 레벨이 완전히 채워져 있고, 가장 아래 레벨은 왼쪽부터 채워져야 함을 의미합니다. 힙은 주로 다음과 같은 작업에 사용됩니다. 최댓값 또는 최솟값을 빠르게 찾아내는 작업 (O(1) 시간 복잡도로 가능). 데이터의 삽입과 삭제(최대 또는 최소 요소에 대한)를 빠르게 수행하는데 효율적. 최대 힙은 부모 노드가 자식 노드보다 크거나 같은 값을 가지며, 최소 힙은 부모.. 2024. 1. 16.
[React] 웹 접속 시 특정 경로 고정 연결 - 로컬 스토리지 웹 페이지에 접속하면 보통 첫 번째 메뉴가 자동으로 선택되어 있는 웹 사이트를 많이 볼 수 있습니다. 이런 식으로 가장 첫 번째 메뉴가 선택(실행)되어 있는 상태로 페이지가 오픈되는 경우가 있습니다. 해당 웹 사이트의 메뉴는 사용자가 직접 뉴스 클리핑 그룹을 추가 및 삭제하여 구성된 메뉴입니다. 그룹별로 id가 있어서 첫 번째 메뉴의 id는 사용자마다 다를 수 있습니다. 이때 메뉴 가장 첫번째가 웹 사이트가 열리면 고정적으로 선택되어 있는 상태가 되도록 코드를 짜보겠습니다. 1. DB에서 사용자의 그룹 키워드를 가져오는 함수에서 가장 첫 번째 id를 따로 추출 2. 첫 번째 그룹 ID를 로컬 스토리지에 저장합니다. 3. 페이지가 다시 로드될 때, 로컬 스토리지에서 저장된 그룹 ID를 가져와 초기 경로를 .. 2024. 1. 15.
최단경로 - 다익스트라 알고리즘 구체적인 설명 다익스트라 알고리즘은 하나의 출발 노드로부터 모든 노드까지의 최단 경로를 찾는 알고리즘입니다. 알고리즘의 원리를 간략히 설명하면 다음과 같습니다. 1. 출발 노드를 설정한다. 2. 최단 거리 테이블을 초기화한다. 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다. 5. 위에 3번과 4번을 반복한다. 눈으로 읽어보면 해당 원리를 이해하기엔 쉽지 않습니다. 예시를 들어서 원리를 설명드리겠습니다. 예시 그래프입니다. 노드 개수 (n) = 6 간선 개수 (m) = 9 시작 노드 (start) = 1 간선 정보: 1 -> 2 (비용: 2) 1 -> 3 (비용: 5) 2 -> 3 (비용: 2) 2 -> 4 .. 2024. 1. 13.
[이코테] 효율적인 화폐 구성 - 구체적 풀이 문제 N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다. 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다. 입력 조건 첫째 줄에 N,M이 주어진다(1 2024. 1. 12.
[이코테] 바닥 공사 문제 가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1 X 2의 덮개, 2 X 1의 덮개, 2 X 2의 덮개를 이용해 채우고자 한다. 이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 2 X 3 크기의 바닥을 채우는 경우의 수는 5가지이다. 입력 조건 1. 첫째 줄에 N이 주어진다. (1 2024. 1. 11.
[이코테] 개미 전사 개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 합니다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있습니다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 선택적으로 약탈하여 식량을 빼앗을 예정입니다. 이때 메뚜기 정찰병들은 일지선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있습니다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 합니다. 예를 들어 식량창고 4개가 다음과 같이 존재한다고 가정하자. {1, 3, 1, 5} 이때 개미 전사는 두 번째 식량창고와 네 번째 식량창고를 선택했을 때 최댓값인 총 8개의 식량을 빼.. 2024. 1. 11.
[백준] 1로 만들기 다이나믹 프로그래밍(동적 계획법) 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있습니다. 대표적인 방법이 다이나믹 프로그램 기법으로 동적 계획법이라고도 합니다. 대표적인 문제는 피보나치 수 입니다. 6번째 피보나치 수 f(6)을 구하려면 다음과 같이 함수 f를 반복해서 호출해야 할 것입니다. 그런데 f(2)와 f(1)은 항상 1이기 때문에 여기서 호출이 정지되게 됩니다. 또한 그림을 살펴보면 똑같은 호출이 반복적으로 나타납니다. 이러한 반복적인 호출은 불필요하며, 번수가 증가함에 따라 불필요한 호출 횟수는 기하급적으로 증가하게됩니다. 재귀 함수를 사용해서 피보나치 함수 코드를 작성해보겠습니다. def fibo(x): if x == 1 or x == 2: return 1.. 2024. 1. 11.
[이코테] 게임 개발 문제 현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 X 1 크기의 정사각형으로 이뤄진 N X M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다. 맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다. 캐릭터의 움직임을 설정하기 위해 정해 놓은 매뉴얼은 이러하다. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 횐전한 다음 왼쪽.. 2024. 1. 4.
[Python] 구글 뉴스 크롤링하기 오늘은 원하는 키워드를 구글 뉴스에서 크롤링하는 파이썬 코드를 작성해보려고 합니다. https://news.google.com/home?hl=ko&gl=KR&ceid=KR:ko https://news.google.com/home?ceid=KR%3Ako&gl=KR&hl=ko news.google.com url을 자세히 살펴보겠습니다. 구글 뉴스에서 특정 키워드를 검색하면 url이 어떤 형태로 변경되는지 살펴보겠습니다. https://news.google.com/search?q=네이버&hl=ko&gl=KR&ceid=KR%3Ako 검색창에서 "네이버" 라고 검색했는데 url에 변화가 생겼습니다. q=네이버 이라는 텍스트가 추가되었는데 여기서 q는 query의 약자입니다. 원하는 검색어를 url에 q={키워드}.. 2024. 1. 4.
[Linux] 윈도우에서 실행했던 파이썬 파일 옮겨서 실행시키기 먼저 리눅스(우분투) 계정 로그인합니다. 저는 naver_linux 세션으로 로그인하겠습니다. 로그인을 완료하고 윈도우에 있는 파이썬 파일을 옮길 폴더를 생성합니다. 저는 root 폴더에서 test 폴더를 생성하여 이곳에 파이썬 파일을 옮겨보도록 하겠습니다. 이제 윈도우(local)로 돌아옵니다. 윈도우 PowerShell를 실행시킵니다. 실행시켰으면 이동시키고 싶은 파이썬 파일이 있는 폴더로 이동합니다. 저의 파이썬 파일은 Users/LG/Linux_Python/Test.py입니다. 파일이 있는 폴더로 이동했습니다. 명령어를 입력합니다. scp -P [리눅스 포트넌버] [.\옮기고 싶은 파일] [계정이름@IP넌버]: [옮기고자하는 리눅스 폴더 위치] 해당 명령어를 입력하면 리눅스 계정 비밀번호를 입력하.. 2023. 2. 19.

티스토리툴바