https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다. 이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북 www.acmicpc.net [ 풀이 ] 두차례의 BFS를 이용해서 풀었다. 1. 라벨 번호 붙이기 + 바다와 인접한 섬위치 구하기 : BFS ( bfs_labe..
https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다. www.acmicpc.net [풀이] 전형적인 BFS 문제이다. 먼저 연결된 노드를 노드 관계 리스트로 나타냈다. 7 => 컴퓨터 개수(그래프 노드개수) 6 => 간선의 개수(그래프 연결관계) 1 2 => 노드1번과 노드2번 연결/ 노드2번과 노드1번 연결 2 3 => 노드2번과 노드3번 연결/ 노드3번과 노드2번 연결 1 ..
https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 www.acmicpc.net [풀이] 참고 블로그1: https://blog.naver.com/tjdwns0920/221135677693 참고 블로그2: ht..
https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동 www.acmicpc.net [ 코드] # -*- coding: utf-8 -*- import sys from collections import deque..
https://programmers.co.kr/learn/courses/30/lessons/42898?language=java 코딩테스트 연습 - 등굣길 | 프로그래머스 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = 4, n = 3 인 경우입니다. 가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다. 격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매 programmers.co.kr [풀이] (1) 여기서 주의해야하는게 문제에서 주어..
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net [풀이] 전형적인 BFS 탐색 문제이다. - 먼저 큐에 (시작점 y좌표:0, 시작점 x좌표: 0, 경로수: 시작카운트=1) 넣는다. - 현위치 방문안했으면, 방문을 한다. - 현위치의 상/하/좌/우 중 N행M열 배열원소이고, 아직 방문하지 않은 상태의 '1'(이동할 수 있는칸) - 현위치의 cnt에 1을 더하여 큐에 추가한다. (python) # -*- coding: utf-8 -*- # 2178. 미로찾기 import sys ..
https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다. www.acmicpc.net [풀이] DP와 DFS를 활용한 문제이다. 도착점(M-1, N-1)에 도달할 때까지 경우의 수를 점화식으로 나타내면 DP[M-1][N-1]= DP[M-2][N-1]+ DP[M-1][N-2] 현위치가 (0,0) 인 시작점이라면 1을 리턴한다. 현위치가 (0,0)이 아닌 다른 점이라면 (1) 방문했다는 의미로, ..
- Total
- Today
- Yesterday
- 참고
- 한달어스
- nestjs jest
- 스마트폰중독
- 바이트디그리
- MySQL
- 습관개선
- RDBMS
- 한달독서
- 개발용어
- OS
- 클린아키텍쳐
- jest
- TDD
- 갓생살자
- Mongoose
- 미완
- vscode
- nestjs
- gem
- 나도 할 수 있다
- Jekyll
- MongoDB
- TypeScript
- git
- Nest.js
- typeORM
- 디지털디톡스
- IT용어
- node.js
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |