본문 바로가기

Dev80

[백준] #2583 영역 구하기 파이썬 https://www.acmicpc.net/problem/2583문제눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.예를 들어 M=5, N=7 인 모눈종이 위에 과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 와 같이 3개의 분리된 영역으로 나누어지게 된다.와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작.. 2024. 12. 26.
BFS vs DFS 알고리즘에서 BFS와 DFS 중에 어떤거를 적용할지 헷갈릴때가 많다.정리하는  DFS를 사용하는 경우1.  특정 지점에서 출발해 목적지까지가는 모든 경로를 탐색하는 경우   ex) 미로찾기, 퍼즐문제2. 순열/조합 생성하는 문제   ex) 주어진 숫자로 가능한 모든 숫자 조합 만들기3. 재귀적으로 문제를 해결할때   ex)백트래킹 문제  BFS를 사용하는 경우 1. 최단 경로를 찾는 문제   ex) 미로에서 최단거리 찾기, 특정 도시간 최단 경로 탐색2. 최소 비용 문제   ex) 체스판의 나이트 이동 최소 획수3. Flood fill 문제   ex) 그림판에서 색을 채우는 문제, 섬의 개수 찾기  한눈에 이해하기DFS: "한 가지 길을 끝까지 파고들고 싶다!"BFS: "모든 길을 동시에 살펴보며 가장 .. 2024. 12. 26.
[백준] #10451 순열 사이클 파이썬 문제1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 (1234567832781456)\(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\  3& 2&7&8&1&4&5&6 \end{pmatrix}\) 와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다.순열을 배열을 이용해 (1…i…nπ1…πi…πn)\(\begin{pmatrix} 1 & \dots & i & \dots &n \\  \pi_1& \dots& \pi_i & \dots & \pi_n \end{pmatrix}\) 로 나타냈다면, i에서 πi로 간선을 이어 그래프로 만들 .. 2024. 11. 26.
[백준] #14501 퇴사 파이썬 문제상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.N = 7인 경우에 다음과 같은 상담 일정표를 보자. 1일2일3일4일5일6일7일TiPi35112421020102015402001일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.상담을 하는데 필요한 기간은 1일보다 클 수 .. 2024. 10. 4.
[백준] #2667 단지번호붙히기 파이썬 문제과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.입력첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.출력첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집.. 2024. 10. 2.
[백준] #14719 빗물 파이썬 https://www.acmicpc.net/problem/14719 문제2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?입력첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.출력2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.빗물이 전혀 고이지 않을 경우 0을 출력하여라.복기1. H x W의 array를 만들어서 .. 2024. 10. 2.
[백준] #3085 사탕게임 파이썬 https://www.acmicpc.net/problem/3085문제상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.입력첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, .. 2024. 9. 30.
[백준] 14502 연구소 (파이썬) https://www.acmicpc.net/problem/14502문제인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.2 0 0 0 1 1 00 0 1 0 1 2 00 1 1 0 1 0.. 2024. 8. 22.
[Git] Pull 에러 해결하기 "Please commit your changes or stash them before you merge." git pull 을 했더니 다음과 같은 에러가 나왔다. error: Your local changes to the following files would be overwritten by merge: apps/home/insert.py Please commit your changes or stash them before you merge. Aborting - 원인문제의 원인은 원격 저장소에서 pull 할때 로컬에 수정한 파일이 존재하기 때문이다.예를 들어 팀 프로젝트 파일을 pull 하는 것을 까먹고, 로컬에서 프로젝트 파일을 수정하던 중 원격 저장소 파일을 pull  하게 되면 이런 에러가 나타난다. - 해결방법1. 로컬 내 수정 사항을 임시 공간으로 옮긴다git stash 2. 원격 저장소를 pull .. 2024. 7. 24.
[Git] git branch --set-upstream-to 에러 $ git pull을 했더니 There is no tracking information for the current branch.Please specify which branch you want to merge with.See git-pull(1) for details. git pull If you wish to set tracking information for this branch you can do so with: git branch --set-upstream-to=origin/ main이런 에러가 나왔다. 로컬에 있는 브랜치가 원격저장소의 어떤 브랜치를 참조할지 몰라서 나오는 에러이다  $ git branch --set-upstream-to=origin/main main브랜치를 설정해.. 2024. 7. 10.

티스토리툴바