[Silver I] 쉬운 최단거리 - 14940문제 링크성능 요약메모리: 41792 KB, 시간: 680 ms분류너비 우선 탐색, 그래프 이론, 그래프 탐색제출 일자2024년 10월 31일 11:54:41문제 설명지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.입력지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.출력각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래..

[Silver I] 회의실 배정 - 1931문제 링크성능 요약메모리: 56780 KB, 시간: 312 ms분류그리디 알고리즘, 정렬제출 일자2024년 10월 30일 14:43:57문제 설명한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.입력첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주..

[Silver I] 숨바꼭질 - 1697문제 링크성능 요약메모리: 35092 KB, 시간: 136 ms분류너비 우선 탐색, 그래프 이론, 그래프 탐색제출 일자2024년 10월 30일 13:54:13문제 설명수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.입력첫 번째 줄에 수빈이가 ..

이진 트리의 삭제 조건이진 트리의 remove는 3가지 조건을 따로 살펴보아야한다.삭제되는 노드가말단(leaf) 노드인 경우자식을 하나만 가지고 있는 경우자식을 둘 가지고 있는 경우1. 말단(leaf) 노드인 경우말단 노드가 위치하는 부모노드의 참조를 (left or right) None으로 변경해주기만 하면됨.즉, 말단 노드가 왼쪽에 있는지 오른쪽에 있는지 확인 후 부모 노드의 참조값만 None으로 변경.2. 자식을 하나만 가지고 있는 경우삭제되는 노드 자리에 그 자식을 대신 배치즉, 자식이 왼쪽에 있는지 오른쪽에 있는지 확인 후 부모 노드에 자식을 배치3. 자식을 둘 가지고 있는 경우삭제되는 노드(A)보다 바로 다음 큰 key를 가지는 노드(B)를 찾는다.삭제하고자 하는 노드(A)와 key를 가지는 ..

[Silver II] 좌표 압축 - 18870문제 링크성능 요약메모리: 144340 KB, 시간: 1852 ms분류값 / 좌표 압축, 정렬제출 일자2024년 10월 29일 00:16:14문제 설명수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.입력첫째 줄에 N이 주어진다.둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.출력첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.  풀이 impor..

넓이 우선 탐색의 원칙수준 (level) 이 낮은 노드를 우선으로 방문한다.같은 수준의 노드 사이에서는부모 노드의 방문 순서에 따라 방문왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문  한 노드를 방문했을 때, 나중에 방문할 노드들을 순서대로 기록해두어야한다. → 큐(queue)를 이용해보자.넓이 우선 순회 알고리즘 설계A를 큐에 넣고 dequeue()A의 자식 노드를 왼쪽에서 부터 enqueue() | B , C |B를 dequeue()B의 자식 노드를 왼쪽 부터 enqueue() | C , D , E |C를 dequeue() | D , E |C의 자식 노드를 왼쪽 부터 enqueue() | D , E , F , G |… 반복 , 큐에 남은 노드가 없으면 종료결과넓이 우선 순회 알고리즘 구현(빈 리스트 초..

트리트리들은 데이터베이스 시스템 또는 검색 엔진 등에서 아주 많이 이용된다.트리를 딱딱하게 말하면, 순환하는 길이 없는 그래프 (graph) 로 정의된다.트리 용어노드 (nodes)간선 (edges)루트 노드 (root node), 리프 노드 (leaf nodes), 내부 노드 (internal nodes)부모 (parent) 노드와 자식 (child) 노드노드의 수준 (level)노드의 차수 (degree)트리의 높이 (height) - 또는, 깊이 (depth) -부분 트리 (서브트리; subtrees)이진 트리 (binary trees)포화 이진 트리 (full binary trees)완전 이진 트리 (complete binary trees)트리 종류포화 이진트리완전 이진트리 (리프 노드 위는 모두..

경로 표현식경로 표현식: .(점)을 찍어 객체 그래프를 탐색하는 것select m.username(상태필드) from Member m join m.team t(단일값 연관필드) join m.orders o(컬렉션 값 연관필드)where t.name = '팀'경로 표현식 세가지 필드상태 필드 : 단순히 값을 저장하기 위한 필드(참조의 끝값) , 경로탐색의 끝을 의미한며 단순 값이기 때문에 더이상 탐색이 불가하다단일값 연관필드 : @ManyToOne, @OneToOne, 대상이 엔티티컬렉션 값 연관필드 : @OneToMany, @ManyToMany : 대상이 컬렉션연관필드 : 연관관계를 위한 필드(참조를 이어가는 부분)상태 필드String query = "select m.username..

우선순위 큐무조건 선입선출의 개념에 의한 것이 아닌, 우선순위가 높은 순서대로 dequeue 되는 것을 의미한다.이는 운영체제에서 CPU 스케줄러를 구현에서 사용하고 전공 강의에서 접해본 적이 있다. 우선순위 큐는 크게 두가지 접근 방법이 있다.큐에 원소를 넣을 때 (enqueue 할 때) 우선순위 순서대로 정렬해 두는 방법큐에서 원소를 꺼낼 때 (dequeue 할 때) 우선순위가 가장 높은 것을 선택하는 방법1번, enqueue할 경우 우선순위 순서대로 정렬해 두는 방법이 복잡도 차원에서 좀 더 유리하다. 그 이유는 이미 큐를 정렬 상태로 두기 때문에 우선순위에 따라 큐를 정렬하기 위한 삽입 연산을 줄일 수 있기 때문이다. 즉, 이미 정렬 되어 있기에 큐의 모든 원소의 우선순위를 조회할 필요가 없기 때..