문제 보러 가기 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 이 문제는 그래프 탐색 + 구현 문제이다. 특별히 신경 써야 될 점은 2가지가 있다. 1. 방향 탐색 순서 2. 4방향 모두 벽 or 이미 청소 완료 일 때 -> 현재 방향으로 후진 문제풀이 - 문제에서 입력받은 청소기의 현재 위치 r, c 방향 d로부터 탐색. - 현재 방향의 왼쪽 칸부터 탐색해야 하므로 반시계 방향 순서대로 탐색 ex) 현재 방향↑ 이면, ← ↓ → ↑방향 순서대로 탐색 - 여기서 주의점 , 문제에서는 처음 d를 0인 경우에는..
문제 보러 가기 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 이 문제는 이진트리 자료구조를 이용하여 너비를 구하는 응용문제이다. 너비를 구하는 부분에서 좀 다른 점이 있다면, 각 level마다 최대 너비를 구해야 한다는 점. 가장 왼쪽 자식이 1번 , 가장 오른쪽 자식이 n번으로 너비를 구한다는 점이다. 아래 트리와 같이 구성된다. 문제풀이 - 자신의 번호와(num) 부모 번호(parent) 왼쪽 자식(left) 오른쪽 자식(right)을 갖는 Node 클래스를 만든다. - Node []..
SQL(Structured Query Language) : 데이터베이스에서 데이터를 조작하거나 조회하기 위해 사용하는 표준 언어. 방법이나 절차를 기술하는 것이 아닌 조건을 기술하여 작성한다. * 각 질의문마다 마지막을 표시하는 세미콜론(;) 써줘야 한다. 분류 용도 명령어 DML (Data Manipulation Language) 데이터 검색 DQL (Data Query Language) SELECT 데이터 조작 INSERT UPDATE DELETE DDL (Data Definition Language) 데이터 정의 CREATE DROP ALTER TRUNCATE RENAME COMMENT DCL (Data Control Language) 데이터 제어 GRANT REVOKE TCL (Transactio..
※ 메모리란? : 메인 메모리, RAM을 뜻한다. 프로그램 실행 시 필요한 주소, 정보들을 저장하고 가져다 사용할 수 있게 만드는 공간. 즉, 작업을 위해 사용되는 공간. 메모리 관리가 필요한 이유는? : 각각의 프로세스는 독립된 메모리 공간을 갖고, 운영체제 혹은 다른 프로세스의 메모리 공간에 접근할 수 없는 제한이 걸려있다. 단지, 운영체제 만이 운영체제 메모리 영역과 사용자 메모리 영역의 접근에 제약을 받지 않기 때문에 운영체제에서 메모리를 관리한다. 또한, 멀티프로그래밍 환경으로 변화하면서 한정된 메모리를 효율적으로 사용해야 했고, 운영체제가 이를 어떻게 관리하는지에 대한 관리방법이 중요해졌다! 운영체제의 역할 실행파일이 로더에 의해 메모리에 올라오고 운영체제는 이 실행파일을 메모리에 어느 부분에..
최소 스패닝 트리(Minimum Spannig Tree) = 최소 신장 트리 : 스패닝 트리 중 가장 작은 가중치의 간선으로 구성된 트리를 의미한다. 조건 본래의 그래프의 모든 노드를 포함 간선의 가중치의 합이 최소여야 한다 모든 노드가 서로 연결되어있다 트리의 속성을 만족 (사이클이 존재하지 않는다) ↓스패닝 트리란? 더보기 스패닝 트리란? : 그래프의 최소 개수의 간선으로 이뤄진 트리 (n개의 노드가 존재한다면 간선은 항상 n-1개이다) 모든 노드가 연결되어야 함 사이클이 존재하지 않음 즉, 최소 스패닝 트리에서 최소 가중치의 합 조건만 빠진 트리를 의미. 이 최소 스패닝 트리 문제를 다루는 알고리즘에는 2가지가 있다. 1. 크루스 칼(Kruskal) 알고리즘 : 두 노드 간 제일 작은 가중치의 간선..
최소 스패닝 트리 2가지 알고리즘 내용 문제 보러 가기 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 이 문제는 최소 스패닝 트리의 가장 기본적인 구현을 다루는 문제이다. 최소 스패닝 트리는 스패닝 트리 중(그래프 내의 모든 정점을 포함하는 트리) 연결된 간선 가중치가 가장 작은 것들로 구성된 트리를 의미한다. 모든 정점을 포함하기 위해서는 하나의 트리로 연결돼야 하는데 이때 사용하는 알고리즘이 크루스칼, 프림 2가지의 방법이 있다. 이 중 크루스칼을 이용하여 풀이하였다. 문제풀이 크루스칼 알고리즘은 Union-Find를 사용하여 구현할 수 있다. -> Union-Find 설명 - 간선의 정보를 ..
문제 보러 가기 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 이 문제는 유니온 파인드라는 알고리즘을 이용하여 합집합을 만들고, 판단하는 문제이다. 자료구조를 코드로 만들어 표현하는 부분을 더 연습해야겠다고 생각했다! 유니온 파인드(Union-Find) 알고리즘이란? 그래프 알고리즘 중 하나이다. 분리 집합, 합집합 찾기의 의미를 갖는다. parent [] 배열로 각 노드가 어떤 부모 노드 아래에 있는지 그래프로 만든다. x 1 2 3 parent[x] 1 2 3 -..
문제 보러 가기 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 이 문제는 기본 트리구조를 생성하고 트리의 순회 방법인 전위, 중위, 후위 순회를 해보는 트리 자료구조의 기본 문제라고 볼 수 있다. 재귀를 사용하여 구현하였다. 트리는 다양한 방법으로 구현할 수 있다. 나의 경우 트리 클래스를 따로 만들어서 사용하였다. Node [] 배열로 만들어서 구현하는 방법도 존재한다. 문제풀이 -tree 자료구조에 입력받은 각 노드를 위치에 맞게 insert()한다. -전위 순회(preOrder) : 루트 -> 왼..
- Total
- Today
- Yesterday
- sockjs
- git
- 삼성 sw역량테스트
- programers
- 분리 집합
- DP
- Baekjoon
- SWEA
- 코딩테스트
- Heap
- 최소 스패닝 트리
- BFS
- 백준
- java
- OS
- JavaScript
- dfs
- Oracle
- 정렬
- websocket
- 자바
- MST
- Stomp
- 완전탐색
- 프로그래머스
- 알고리즘
- 채팅
- 운영체제
- Spring
- 삼성 sw역량 테스트
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |