분류 전체보기
-
BOJ) 녹색 옷 입은 애가 젤다지? (4485 번)알고리즘/백준 2021. 1. 19. 00:33
녹색 옷 입은 애가 젤다지? 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 다익스트라를 알고, 적절하게 이용할 줄 아는가?를 물어보는 문제였다. 좌측 상단에서 우측 하단으로 이동하면서 돈을 가장 적게 뺏겨야하는 문제다. 처음에는 dp로 간단하게 풀 수 있겠다고 생각하고 코드를 작성했지만, 불규칙적으로 왔다갔다하는 경우가 있어서 다익스트라를 추가해줬다. 출발 지점을 우선순위 큐에 담아두고, 상하좌우를 돌면서 돈을 가장 적게 뺏기는 경우들을 저장하면서 큐에 넣어주었다. 이동하면서, 가장 적게 ..
-
BOJ) 트리의 지름 (1967 번)알고리즘/백준 2021. 1. 19. 00:25
트리의 지름 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 이진 트리인줄 알고 시간을 조금 낭비했다. 왜 틀렸는지 잘 모르겠어서 게시판 글을 읽다가, 이진 트리가 아닌 케이스를 보고 해결했다. 풀이 풀이 방법은 간단하다. 각 tree의 연결 정보를 ArrayList에 담아두고 (n이 최대 10,000가 되는데, 배열로는 메모리 초과가 발생할 것임) dp라고 선언한 배열을 통해 각 노드에서 자식 노드의 최대 weight를 메모이제이션 해주었다. 그리고 답을 찾을 때는 우선순위 큐를 통해, ..
-
BOJ) 트리 순회 (1991 번)알고리즘/백준 2021. 1. 19. 00:18
트리 순회 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 이진 트리에 대한 개념을 알고 있다면 어렵지 않은 문제였다. 다만, 트리의 입력 정보가 포화 이진 트리인지, 완전 이진 트리인지, 정 이진 트리인지 보장해주지 않는다. (트리에 대한 개념 설명은 이전 자료구조의 트리 포스팅을 참고) 그래서, 해당 노드의 값에 따라 정보를 입력해주어야 한다는게 핵심이었던 것 같다. 위의 입력 문제를 해결하기 위해서 append라는 메소드를 만들었다. node의 vertex 값이 일치하는 node를 찾아 left, ..
-
BOJ) 뱀 (3190번)알고리즘/백준 2021. 1. 19. 00:03
뱀 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 시뮬레이션 문제로 기억하는 사람이 있을지 모르지만, 피자를 먹으면 뱀의 꼬리가 늘어나는 게임이 있었다. 딱, 그 문제를 구현하는 문제였다. 아무튼, 행과 열을 오랜만에 이용하다보니 이에 대한 개념의 혼동으로 문제를 틀렸었다. 행은 가로에 대한 정보, 열은 세로에 대한 정보다. 따라서, 행은 y축의 index를 가지고 열은 x축의 index를 갖게된다. 풀이 문제의 조건에 머리가 뱀의 몸에 닿거나 벽에 닿으면 종료된다. 벽에 대한 정보를 저장해주려고 맵의 크기를 N+..
-
Nginx 작동 원리CS 지식/기타 2021. 1. 15. 14:33
Nginx apache의 한 시스템에 동시 접속자 수가 1만명이 넘어갈 때, 효율적이지 못한 문제를 해결하기 위해 나온 Event-Driven 구조의 웹 서버 SW 가벼움과 높은 성능을 목표로 탄생 웹 서버, 리버스 프록시, 메일 프록시 리버스 프록시 컴퓨터 네트워크에서 클라이언트를 대신해서 한 대 이상의 서버로부터 자원을 추출하는 프록시 서버의 일종 자원들을 웹 서버 자체에 가지고 있는 것처럼 (origin 처럼) 클라이언트로 반환 목적지에 직접 접근하지 않고 프록시를 통해 데이터를 주고 받는 포워드 프록시와 반대되는 개념으로, 리버스 프록시는 다른 서버의 정보를 프록시를 통해 받아오는 중간 매개체 사용자가 요청하는 Endpoint는 접근하고자 하는 최종 목적지 서버가 아닌, 리버스 프록시 리버스 프록..
-
HashMap과 해시 충돌CS 지식/자료구조 2021. 1. 14. 18:08
HashMap과 HashTable 관계 HashTable JDK 1.0부터 있던 Java의 API Map 인터페이스를 구현하고 있기 때문에 HashMap과 HashTable이 제공하는 기능은 같다. JDK 버전에 따른 구현에 거의 변화가 없다. HashMap Java 2에서 처음 선보인 Java Collections Framework에 속한 API 보조 해시 함수(Additional Hash Function) (~> hashCode) 를 사용 보조 해시 함수를 사용하지 않는 HashTable에 비하여 해시 충돌(hash collision)이 덜 발생할 수 있어 상대적으로 성능상 이점이 있음 JDK 버전에 따라 지속적으로 개선되고 있다. HashTable의 현재 가치는 JRE 1.0, JRE 1.1 환경을..
-
TreeCS 지식/자료구조 2021. 1. 14. 15:46
Tree Tree 스택이나 Queue와 다르게 비선형 & 계층적 관계 자료 구조 트리는 표현에 집중한다 Node, Edge, Root Node, Terminal Node(Leaf Node, 단말 노드) => 하위에 다른 노드가 없는 최하위 노드, Internal Node(내부 노드, 비단말 노드) => 단말 노드를 제외한 모든 노드(루트 포함) Binary Tree 루트 노드를 중심으로 두 개의 서브 트리를 가지는 자료구조 서브 트리 또한 모두 이진 트리여야함 (공집합 포함) 트리의 depth를 숫자로 매겨서 레벨(Level)이라고 함( 0부터 시작 left child key) 부모의 키가 오른쪽 자식 노드의 키보다 작다. (parent key < right child key) 서브 트리도 모두 이진 탐..
-
Array vs LinkedListCS 지식/자료구조 2021. 1. 14. 15:45
Array vs LinkedList Array 논리 저장 순서랑 물리 저장 순서가 일치함 인덱스로 원소에 접근이 가능하기 때문에, O(1)로 엑세스 가능 삭제 or 삽입은 해당 원소에 접근하여 작업을 완료한 뒤(O(1)), 또 한 가지의 작업을 추가적으로 해줘야 하기 때문에, 시간이 더 걸린다. 맨 뒤에 요소를 추가하는 것은 O(1)이지만, 원래 존재하던 요소의 앞쪽에 삽입한다면 뒤에 있는 요소들의 인덱스를 +1씩 해줘야함 삭제의 경우도 뒤에 있는 요소들을 한칸씩 땡겨줘야함 (인덱스 -1) 위의 두 경우 모두 O(n)의 작업이 추가적으로 필요하다 LinkedList 논리 저장 순서와 물리 저장 순서가 일치하지 않음 논리 저장에는 실제 저장되어있는 요소의 주소 값이 들어있다. 각 원소들은 자신의 다음 원소..