일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 릿코드
- 다익스트라
- swea
- 네트워크
- 관계형 모델
- Application Layer
- boot sequence
- 응용 계층
- STL
- DB
- 부트시퀀스
- 백준
- baekjoon
- Database
- 문제풀이
- 자료구조
- Transport layer
- C++
- 임베디드
- dp
- leetcode
- 데이터베이스
- Embedded
- BHS
- Djikstra
- BST
- ps
- Network
- 전송 계층
- 프로그래머스
- Today
- Total
목록Algorithm/Problem Solving (26)
BOBO's Note
https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크�� www.acmicpc.net 풀이 방법 1인 칸에 대해서 가능한 모든 색종이 종류를 덮어본다. DFS를 이용해서 1인 칸을 모두 덮은 경우, 사용한 최소 색종이 수를 업데이트해나간다. (i, j)를 왼쪽 꼭짓점으로 덮을 수 있는 모든 색종이 종류는 다음과 같이 구한다. 한 변의 길이가 n보다 큰 색종이는 0인 칸 또는 다른 색종이로 덮은 칸까지 덮는다. for(r=i; r 0){ if(!cover(i, j, k)..
https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 풀이 방법 모든 연산 순서 조합을 구해서 각 순서에 대해 연산을 차례대로 수행한 후, 그 중 최소 배열 값을 반환한다. 우선 연산 순서 조합을 구하는 함수는 min_val()이다. K개의 연산에 대해 순서 조합을 구하면 Arr 클래스의 apply_ops() 메소드를 호출해 배열 값을 계산한다. void min_val(int n, Arr& arr){ static boo..
https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 풀이 방법 파이프의 양 끝의 위치와 놓여진 방향을 pipe라는 구조체에 저장한다. struct pos{ int r; int c; pos(int r_, int c_): r(r_), c(c_) {}; }; struct pipe{ pos start; pos end; int dir; pipe(pos start_, pos end_, int dir_): start(start_), e..
https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안�� www.acmicpc.net 풀이 방법 주어진 시간 내에 답을 찾기 위해서는 이진 탐색에 DP를 사용해 풀어야 한다. 그리고 std::cin/std::cout 보다는 scanf()/printf()를 사용해야 한다. 찾으려는 수를 key로, 존재 여부를 value로 갖는 unordered_map memo를 선언한다. 그 후, 탐색을 하기 전에 memo를 먼저 살펴봐 데이터가 없는 경..
https://www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하� www.acmicpc.net 풀이 방법 체스판의 임의의 칸에 여러 개의 말이 쌓여있을 수 있다. 이 정보를 states라는 unordered_map에 저장하도록 한다. key는 칸의 위치를 1차원으로 변환한 값, value는 그 칸에 존재하는 말들의 ID 벡터로 한다. 이때, 해당 벡터를 v라고 하고 크기가 n이라면, v[i]는 v[i+1]~v[n-1]을 업고 있다. unordered_map ..
https://www.acmicpc.net/problem/5373 5373번: 큐빙 문제 루빅스 큐브는 삼차원 퍼즐이다. 보통 루빅스 큐브는 3×3×3개의 작은 정육면체로 이루어져 있다. 퍼즐을 풀려면 각 면에 있는 아홉 개의 작은 정육면체의 색이 동일해야 한다. 큐브는 각 면 www.acmicpc.net 풀이 방법 큐브의 각 면의 상태와 회전 등을 Cube라는 클래스로 나타냈다. #define CUBE_SIZE 3 enum {UP, DOWN, FRONT, BACK, LEFT, RIGHT}; class Cube{ public: Cube(){ char colors[6] = {'w', 'y', 'r', 'o', 'g', 'b'}; for(int i=0; i
https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세�� www.acmicpc.net 풀이 방법 소요시간을 기준으로 다익스트라 알고리즘을 적용해 풀 수 있다. 이때, 지원비용 내에서 최소 소요시간을 구하는 문제이기 때문에 한번 방문했던 vertex더라도 재방문할 수 있다(소요시간은 짧지만 비용이 커서 해당 경로로 못 갈 수 있기 때문이다). 처음엔 다익스트라 알고리즘에서 인접 vertex에 대해 distance 벡터를 업데이트해줄 때 다음과..
https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 풀이방법 다익스트라 알고리즘을 이용해 풀 수 있다. priority queue로 다음 vertex를 고르지 않으면 시간 초과가 발생한다. 두 vertex 사이에 여러 간선이 존재할 수 있으므로, 그 중 가중치가 최소인 간선만 저장하기 위해 adjacency list를 unordered_map을 이용해 변형했다. 각 vertex는 unordered_map을 갖는데, uno..