목록전체 글 (121)
풀이 보관함
🔗 문제 14500번: 테트로미노 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 🖍 풀이 모든 위치에서 탐색을 한다. 내 위치를 포함한 주변 위치를 총 4개를 모은다. 이게 테트로미노다. DFS로 4개를 만들든 BFS로 만들든 아무튼 인접한 공간 4개를 모으면 된다. 어떤 모양으로 모였나 디버깅하면 알겠지만 ㅗ, ㅜ, ㅏ, ㅓ 모양으로 방문하는게 어렵다는걸 알게 될 거다. BFS로 하면 만들 수 있는 줄 알았는데 안되길래 따로 oh()라는 함수로 방문해 줬다. (저주받은 작명) BFS로 풀면 508ms이고 D..
🔗 문제 16234번: 인구 이동 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다..
🔗 문제 14888번: 연산자 끼워넣기 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 🖍 풀이 +) 1e9를 이용해 최대, 최소를 표현하는 방법을 배웠다. 완전 탐색으로 싹싹 뒤져보면 된다. 인자로 입력받은 연산자의 개수를 집어넣고 함수가 한번 호출될 때마다 각 연산자로 연산해준다. solve(1, A[0], add, sub, mult, div); 💾 소스 #include long long max=-1e9 , min = 1e9; int N = 0, A[1..
🔗 문제 2307번: 도로검문 2307번: 도로검문 그림 1은 어떤 도시의 주요 지점과 그 지점들 간의 이동시간을 나타낸 그래프이다. 그래프의 노드는 주요 지점을 나타내고 두 지점을 연결한 도로(에지)에 표시된 수는 그 도로로 이동할 때 걸리 www.acmicpc.net 🖍 풀이 문제를 하나씩 뜯어보면 일단 범죄자의 도주 경로와 최소 비용을 구해야 한다. 경로는 양의 가중치가 있는 그래프로 주어진다. 시작 지점과 도착 지점이 주어진다. 두 조건을 보아 다익스트라 기법을 이용해야 한다는 감을 잡았다. 어려웠던 점 최대 지연을 위해서는 모든 도로를 다 빼는 건 시간 초과에다가 틀린 접근이다.( 당ㅇ연함) 도주 경로의 도로를 빼야한다는건 알았는데 어떻게 구현할지 모르겠어서 인터넷의 도움을 받았다. dijkst..
🔗 문제 1976번: 여행 가자 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 🖍 풀이 Union-Find로 간단히 풀 수 있는 문제였다. 여행가려는 지점(route)들이 같은 그래프에 속한다면 재방문을 하겠지만 아무튼 갈 수는 있다. 하지만 이어진 곳이 없는 아예 분리된 그래프라면 방문할 수 없다. 그래프 서로소 집합 구하기?.. 바로 유니온 파인드라는 생각이 들어 풀 수 있었다. 1. 연결된 지점을 받을 때마다 merge를 통해 한 그래프로 만들어준다. 한 그래프로 만든다는 건 부모 노드가 같으면 같은 ..
🔗 문제 22868번: 산책 (small) 22868번: 산책 (small) 첫 번째 줄에는 정점의 개수 $N$과 두 정점 사이를 잇는 도로의 개수 $M$이 공백으로 구분되어 주어진다. 두 번째 줄부터 $M + 1$ 번째 줄까지 정점 $A, B$가 공백으로 구분되어 주어진다. 정점 $A$와 www.acmicpc.net 🖍 풀이 다익스트라를 이용해서 최소 길이를 찾으려고 했다. 하지만 문제를 읽어보면 모든 간선간의 이동 비용은 1이므로 단순하게 BFS로 풀면 된다. 위 조건 덕분에 정렬 후에 가장 처음 만난 노드로 이동하는 것이 최소 비용이 된다. S → E까지의 최소 이동 비용을 구한다. E → S 까지 최소 이동 비용을 구한다. 1 + 2 의 비용 합산 비용으로 정답을 찾을 수 있다. BFS(S, E)..
🔗 문제 16918번: 봄버맨 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net 🖍 풀이 가장 처음에 봄버맨은 일부 칸에 폭탄을 설치해 놓는다. 모든 폭탄이 설치된 시간은 같다. 다음 1초 동안 봄버맨은 아무것도 하지 않는다. 다음 1초 동안 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다. 즉, 모든 칸은 폭탄을 가지고 있게 된다. 폭탄은 모두 동시에 설치했다고 가정한다. 1초가 지난 후에 3초 전에 설치된 폭탄이 모두 폭발한다. 3과 4를 반복한다. 폭탄 터지는 조건 설치 후 3초 후 터진다. 터질 때 상하좌우자리도 빈칸..
🔗 문제 https://www.acmicpc.net/problem/13019 13019번: A를 B로 첫째 줄에 A, 둘째 줄에 B가 주어진다. 두 문자열의 길이는 같으며, 길이는 50을 넘지 않는다. 또, 알파벳 대문자로만 이루어져 있다. www.acmicpc.net 🖍 풀이 solve() : A와 B의 구성요소 유무로 가능성 확인 A와 B의 문자열 길이가 같아야 한다. A와 B를 정렬했을 때 서로 같아야 한다. 같은 문자 구성이라면 정렬했을 때 똑같다! 문자열 길이가 짧아서 정렬해도 시간 초과 없음 solve2() A와 B 문자열을 뒤에서부터 같은지 확인하며 다른 문자열이 나오면 ++result 각 A, B의 뒤를 가르키는 포인터 aptr, bptr를 만들고 서로 같을 때까지 aptr을 왼쪽으로 이동..
🔗 문제 16987번: 계란으로 계란치기 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 🖍 풀이 문제 정리 내구도와 무게를 가진 계란 N개가 있다. 왼쪽부터 깨지지 않은 계란을 집어들고 다른 안 깨진 계란을 깰 시도를 한다. 이 때! 내가 깨질 수도 있고 다른 계란이 깨질 수도 있다. 두 계란의 내구도는 상대 계란의 무게만큼 감소한다. 내구도가 음수가 되면 그 계란이 깨진다. 이걸 깰 계란이 없을 때까지 반복한다. 깰 수 있는 계란이 여러 개 있을 때 탐욕 기법을 이용해서 풀어야 하나 고민을 했..
🔗 문제 https://softeer.ai/practice/info.do?idx=1&eid=540&sw_prbl_sbms_sn=158428 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 백준 뿌요뿌요같은 문제인데 아직 시간초과를 해결하지 못 했다. 알고리즘 단톡방에 올렸는데 아무도 대답해주지 않았고 (…) 나처럼 풀었는데 성공한 사람은 꼭 알려주면 좋겠다. 꼭! 🖍 풀이 N*N 구역에서 같은 색깔의 위치로 면적과 몇 대가 있는지 구해야 한다. N*N 구역에서 사라질 수 있는 차량 종류는 여러 가지이므로 DFS를 사용한다. 같은 색깔이 주변에 있는지 탐색하는 것은 BFS를 사용한다. 같은 종류의 차량이 있는 면적을 구해야 하기 때문에 최대 및 최소 좌표와 같은 차량의 ..