분류 전체보기

그래프란그래프는 아이템들과 이들 사이의 연결 관계를 표현한다.- vertex: 연결점, edge: 연결된 간선 의 수 그래프는 정점들의 집합과 이들을 연결하는 간선들의 집합으로 구성된 자료 구조- V개의 정점을 가지는 무향 그래프는 최대 V*(V-1)/2 간선이 가능 ex) 5개 정점이 있는 무향 그래프의 최대 간선 수는 10 (5*4/2)개이다. 선형 자료구조나 트리 자료구조로 표현하기 어려운 N:N관계를 가지는 원소들을 표현하기에 용이하다. 그래프 유형무향 그래프, 유향 그래프, 가중치 그래프, 사이클 없는 방향 그래프(DAG) 완전 그래프- 정점들에 대해 가능한 모든 간선들을 가진 그래프 부분 그래프- 원래 그래프에서 일부의 정점이나 간선을 제외한 그래프 트리도 그래프이다- 각 노드는 최대 하나의 ..

#3109 빵집문제보러가기 문제이해1열에서부터 마지막 열까지 도착해야한다.한번 방문한 곳은 다시 방문할 수 없다오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선을 방문할 수 있다.해결 방법 고안1. dfs라고 생각했다. 그 이유는 경로를 찾는거여서 한길을 찾으면 마지막 열에 도착할 수 있는 길을 계속해서 찾아야 했다.2. 방문 처리가 필요하다. 한번 선택하면 다시 선택할 수 없어서 visited를 true로 놓으면 된다.3. 백트래킹은 필요없다. 마지막 열에 도착하면 바로 return 한다. 코드더보기import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTok..

아아앗악아아악 발표에 걸렸다. 자세히 정리해보도록 하자,, 문제 이해1. 사용자 A와 B가 있다. 두 사용자는 동시에 움직인다.2. 매초마다 이동 한다. 만약 이동한 좌표의 위치가 BC에 들어오면 접속이 가능하다.3. 이렇게 BC에 들어올 때마다 충전량을 합한 최대값을 찾아야한다.첫 번째 시도사용자가 두 명밖에 없어서 사용자가 m만큼 움직일 때마다 저장되는 충전량을 더하려고 했다.그래서 이차원 배열 map을 만들어서 BC의 성능을 저장하려고 했다.맨해튼 거리를 이용해서 충전 범위에 들어오는 map의 좌표값에 P(성능)을 저장하는 것이다.c >= Math.abs(x-i) + Math.abs(y-j)    두 번째 시도근데 생각을 해보니 BC가 겹칠 수가 있었다. 그래서 이차원 배열을 이용하는 게 아니라는 ..

#17826 공주님을 구해라문제로가기문제이해용사에서 공주까지 갈 때 최단 거리를 구해야한다.용사은 상하좌우 이동할 수 있다.벽은 이동할 수 없다. 빈칸만 이동할 수 있다.1칸당 이동하는데 1시간이 소요된다. T 시간이 넘어가면 fail을 출력해야 한다.* 조건 * 그람 위치에서 그람을 만나면 벽도 이동이 가능한다.   해결 방법 고안1. 최단거리 임으로 bfs를 이용한다.2. 검의 위치에 도달하면 que를 사용하지 않고 바로 그 거리에서 공주까지의 직선 거리를 구한다. 약간의 삽질처음에 검이 위치까지 가기전에 거리를 구했고, 검의 위치에서 다시 que를 사용해서 최단거리를 구하려고 했다.그럴 필요 없이 그냥 검의 위치에서 직선방향으로 (x , y)에서 공주의 위치 ( n-1, m-1)를 구하면 됐었다. ..

#18428 감시피하기문제로가기문제이해장애물, 선생님, 학생이 있고 장애물이 학생이 있는 row나 column에 있게 되면 선생님은 학생을 발견하지 못한다.선생님이 상하좌우에서 학생을 발견한다면 no를, 발견하지 못한다면 yes를 출력단 장애물은 3개까지 설치할 수 있다.해결방법 고안장애물을 설치하는 건 - dfs선생님이 상하좌우에서 학생이 있는지 탐지하는 건 - bfs로 생각했다. 지금 생각해보면 bfs는 필요없는 듯 하긴 하다.dfs로 장애물 3개를 추가한 map을 만든다 -> 그 map에서 바로 check 함수로 bfs를 호출한다.check 함수에는 일단 선생님의 위치를 que에 넣어두고 그 위치에서 열과 행을 다 검사해서 학생을 발견하면 false를 하고, 장애물을 발견하면 반복문을 break하고..

#8275 햄스터문제로가기 문제 이해,  해결 방법 고안    이 문제는 중복 순열 (순서가 있어야 하고, 숫자가 중복으로 들어갈 수 있음)이다.중복 순열 중에서 m에 맞는 조건들을 다 만족하는 것을 출력하는 구현 문제이기도 하다. 처음 푸는데 1시간 이상 걸렸고, 한번 더 풀어보는데도 30분 이상은 걸렸다. 마지막에 출력에 신경 써야 TestCase를 다 만족시킬 수 있다.어차피 순열로 나오는 배열들은 오름차순으로 나오기 때문에 이 조건은 신경쓰지 않아도 됐었다!그리고 나는 마지막에 최종 나오는 (출력해야 하는) 후보를 res 배열에 담았는데 n이 1이 될 수 있기도 때문에 초기화를 null로 해주는 것도 처리해줘야 한다 ~! 애증의 햄스터 코드는 아래에 있다.더보기import java.io.*;imp..

OS 범위는 넓고 넓어서 하나씩 카테고리별로 정리하고자 한다.우선 메모리에 대해서 정리를 해보겠다 Memory Hierarchy메모리 계층의 구조1. Register레지스터는 CPU 내부에 존재하는 가장 빠른 메모리이다. 이 메모리는 극히 제한된 용량 (수십 바이트)만을 가지며, CPU가 데이터를 즉시 처리하기 위해 사용된다. 2. Cache MemoryCPU와 RAM 사이에 위치한 고속 메모리이다. 캐시 메모리는 자주 사용되는 데이터를 저장하여 CPU가 빠르게 접근할 수 있도록 도와준다. 캐시 메모리는 속도와 용량에 따라 L1, L2, L3 캐시로 구분되며 각 계층은 다른 캐시보다 느리지만 더 큰 용량을 가진다. 3. Main Memory, RAM시스템에서 실행되는 프로그램과 데이터를 저장하는 기본 메..

#14502 연구소문제이해0, 1, 2 숫자가 있고 벽(1)을 3개 추가로 세워서 바이러스(2)가 퍼지는 수를 막아서 최대한 빈칸(0)의 개수가 큰 걸 찾아야 한다.   해결 방법 고안- 벽을 3개 세우고 -> 바이러스 퍼지고 -> 0개수 세기- 위에 로직을 계속 반복해야 하는 구조이다.- 그래서 벽을 세우는 건 dfs, 바이러스 퍼지는건 bfs, 개수 세는 함수 이렇게 총 3개의 함수를 만들기로 하였다.- 최종으로 최대한 큰 max_value를 찾아서 결과를 출력해주면 끝이다.코드설명아래 코드에 주석으로 달아놓았다.import java.io.*;import java.util.*;public class Main { private static BufferedReader input = new Buffe..