본문 바로가기

프로그래밍/알고리즘 문제풀이32

[백준] [c++] 4179번 불! ​ https://www.acmicpc.net/problem/4179 4179번: 불! 문제 지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자! 미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다. #include #include #include #include using namespace std; int r, c; char arr[1002][1002]; queue q;//불 int time[1002][1002]; int dx[] = { 1,0,-1,0 }; int dy[] = { 0,1,0,-1 }; int bfs(void) { while (!q.empty()) { pair p; p.. 2020. 8. 6.
[백준] [c++] 11053번 가장 긴 증가하는 부분 수열 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. ​ https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 11053번 제출 맞은 사람 숏코딩 재채점/수정 채점 현황 강의 가장 긴 증가하는 부분 수열 분류 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 45454 17145 11564 37.071% 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = { 10 , 20 , 10, 30 , 20, 50 } 이고, 길이는 4이다. 입력 첫째 줄에 수열 .. 2020. 8. 6.
[백준] [C++] 2631번 줄 세우기 lis문제 #include #include using namespace std; int dp[201]; int main() { vector vec; int n, tmp; cin >> n; vec.push_back(0); for (int i = 1; i > tmp; vec.push_back(tmp); } int top = 0; for (int i = 1; i 2020. 8. 6.
[프로그래머스] [C++] 완주하지 못한 선수 완주하지 못한 선수 ​ ​ 문제 설명 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. 참가자 중에는 동명이인이 있을 수 있습니다. 입출력 예 participant completion retu.. 2020. 8. 6.
[백준] [c++] 4963번 섬의 개수 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러쌓여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정... 단지번호붙이기(https://www.acmicpc.net/problem/2667).. 2020. 8. 6.
[백준] [c++] 2206번 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 2206번 제출 맞은 사람 숏코딩 풀이 풀이 작성 풀이 요청 재채점/수정 채점 현황 강의 벽 부수고 이동하기 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 192 MB 22689 5172 3222 23.100% 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작... www.acmicpc.net ​ ​ 일반 bfs인데, 배열에 벽을 부쉈.. 2020. 8. 6.
[백준] [c++] 15685번 드래곤 커브 https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 문제 드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다. 시작 점 시작 방향 세대 0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다. 1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다. 끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 ... www.acmicpc.net ​ 1) 걍 시뮬레이션??? -> 구현실패 &.. 2020. 8. 6.
[백준] [c++] 2589 번 보물섬 https://www.acmicpc.net/problem/2589 2589번: 보물섬 2589번 제출 맞은 사람 숏코딩 풀이 풀이 작성 풀이 요청 재채점/수정 채점 현황 강의 보물섬 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 128 MB 11528 4609 3304 40.068% 문제 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데... www.acmicpc.net 보물섬 성공 시간 제한 메모리 제한 제출 정답 맞은 사.. 2020. 8. 6.
[백준] [c++] 7569 번 토마토 (3차원) https://www.acmicpc.net/problem/7569 7569번: 토마토 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마... www.acmicpc.net 토마토 성공 시간 제한 메모리 제한 제출 정답 맞은 사.. 2020. 8. 6.
[백준] [c++] 1931 번 회의실배정 https://www.acmicpc.net/problem/1931 1931번: 회의실배정 1931번 제출 맞은 사람 숏코딩 풀이 풀이 작성 풀이 요청 재채점/수정 채점 현황 강의 회의실배정 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 29402 8148 6076 28.732% 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것... www.acmicpc.net 회의실배정 성공 시간 제한 메모리 제한 제출 정답 .. 2020. 8. 6.