알고리즘/BOJ(C++)
-
[백준 / BOJ] 2933 :: 미네랄알고리즘/BOJ(C++) 2021. 2. 6. 22:56
www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 문제 설명 : 막대기를 한번은 왼쪽에서 오른쪽으로, 다른 한번은 오른쪽에서 왼쪽으로 던질 것이다. 이때 각 방향으로 탐색해서 오면서 처음 만나는 미네랄을 캘 것이다.(미네랄이 있는 곳이 0 처리됨) 미네랄은 클러스터(군집)이 있다. 상하좌우로 연결된 미네랄은 같인 미네랄 클러스터이다. 미네랄을 캐면서 하나의 미네랄이 없어지는데, 이 때 기존에 연결되어 있던 클러스터가 서로 분리 될 수도 있다. 그러면 그 두 클러스터 중 하나..
-
[백준 / BOJ] 16988 :: Baaaaaaaaaduk2 (Easy)알고리즘/BOJ(C++) 2021. 1. 2. 21:35
www.acmicpc.net/problem/16988 16988번: Baaaaaaaaaduk2 (Easy) 서기 2116년, 인간은 더 이상 AI의 상대가 되지 못하게 되었다. 근력, 순발력, 창의력, 사고력, 문제해결능력, 심지어 인간미조차 AI가 인간을 앞선다. AI가 온 지구를 관리하며 이미 인류는 지구의 www.acmicpc.net Easy..? 다들 알고리즘 잘하시나봐요..이게 easy라니 ㅠ 문제 : 우선, 앞에 장황한 쓸데없는 설명은 안읽어도 됩니다. 결론적으로 말하면, 우리는 돌 두개를 놓을 것인데, 돌 두개를 놓아서 상대방 돌을 최대한 많이 따먹어야 합니다. 상대방 돌을 딸 수 있는 조건은 Baduk2에서는 일반적인 바둑과 동일하게 자신의 돌로 상대방의 그룹을 빈틈없이 에워싸면 갇힌 돌을..
-
[백준 / BOJ] 1600 :: 말이 되고픈 원숭이알고리즘/BOJ(C++) 2020. 12. 30. 23:03
www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 문제 설명: - 시작 지점(제일 왼쪽, 제일 위 (H,1))에서 도착지점 (제일 오른쪽, 제일 아래(1,W))까지 이동하는 최단 거리를 찾자 - 이동할 수 있는 방법에는 두가지가 있다. 1. 체스판의 나이트 처럼 이동하는 경우(현 자리에서 8가지) 2. 인접한 칸으로 이동하는 경우(현 자리에서 4가지) - 이 때 1번의 방법으로 이동하는 경우는 최대 K번까지 사용 가능하다. 풀이 / 구현 방법 ..
-
[백준] 1025 :: 제곱수 찾기알고리즘/BOJ(C++) 2020. 12. 21. 00:11
www.acmicpc.net/problem/1025 1025번: 제곱수 찾기 첫째 줄에 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 직사각형 격자판에 쓰여 있는 수가 주어진다. 모두 한자리이다. N과 M은 9보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 문제 : 문제 설명 세상 난해해.. 자, 차분히 이해를 해 봅시다. 문제를 읽어보면 행의 숫자가 등차수열이고, 열의 숫자도 등차수열을 이루는 서로 다른 칸의 수열 이라는 문구가 나옵니다. 이게 무슨 뜻이냐 하면 map[i][j] 이렇게 있을 때 (i,j)의 숫자를 뽑는겁니다. 차례로 (x1,y1) , (x2,y2) , (x3, y3) 뭐이런식으로 뽑아 나가겠죠. 이때 x를 나열했을 때도 등차수열, y를 나열했을..
-
[백준] 4458 :: 첫 글자를 대문자로 ( C++ 한 줄 입력받기, getline 함수 , cin.ignore())알고리즘/BOJ(C++) 2020. 12. 19. 16:50
www.acmicpc.net/problem/4458 4458번: 첫 글자를 대문자로 첫째 줄에 줄의 수 N이 주어진다. 다음 N개의 줄에는 문장이 주어진다. 각 문장에 들어있는 글자의 수는 30을 넘지 않는다. 모든 줄의 첫 번째 글자는 알파벳이다. www.acmicpc.net 원래 이 문제는 너무 간단해보여서 포스팅 안하려다가 딱 하나 정리하려고 쓴다. 테스트 케이스 만큼 한 줄 씩 입력받아야하는데, cin>> 이렇게 쓰면 공백을 기준으로 변수가 저장된다. 그래서 "You are lovely" 이런 문장을 쓰게 되면 You 까지만 입력이 된다. 한 줄을 통째로 입력 받으려면 getline을 써야한다. ex) getline(cin,str) 이렇게 쓰게 되면 '\n'을 기준으로 구분하여 입력을 받을 수 있..
-
[백준] 10250 :: ACM 호텔알고리즘/BOJ(C++) 2020. 12. 19. 16:43
www.acmicpc.net/problem/10250 10250번: ACM 호텔 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수 www.acmicpc.net 문제 : 거창한 설명 다 지우고나면 결국, y값이 가장 작고, 그 다음으로 x값이 가장 작을 수 있는 남은 방을 손님에게 배정해라 풀이 : 예를 들어 6, 12, 10 이라면 101 201 301 401 501 601 >>>>>> 102 ... 602 >>>>>>> 103 203 303 403 이런식으로 채워지게 된다. 결국 다음 호수 (1호 다음 2호) 층수만큼 한바퀴를 돌아와야한다는 뜻 그래서 ..
-
[백준] 2583 :: 영역 구하기알고리즘/BOJ(C++) 2020. 12. 19. 16:37
www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 문제 : 영역에 직사각형 그려진 부분 제외하면, 분리 된 부분이 총 몇개 인지, 각 분리된 부분의 영역의 크기는 얼마인지 구해라 풀이 : - MAP에 직사각형이 존재하는 부분 표시 - MAP의 0,0 ~ M,N까지 탐색하면서 색칠되지 않은곳(직사각형이 존재하지 않거나, 이미 탐색되지 않은 곳)이 발견된다면 전체 분리된 개수(ans)에 추가하고, 그 위치에서 BFS 돌리기 - BFS 탐색하면서..
-
[백준] 1024 :: 수열의 합알고리즘/BOJ(C++) 2020. 7. 27. 22:59
https://www.acmicpc.net/problem/1024 1024번: 수열의 합 첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다. www.acmicpc.net 완전 수학수학 스러운 문제이다. 문제를 요약하자면 연속된 l개의 수를 합해 n을 만들 수 있는 수열을 찾으면 된다. 이때 연속된 l개의 수는 l개 부터 최대 100개 까지일 수 있다. 우리는 여기서 힌트를 얻어야 한다. 100개정도는 탐색해 볼 수 있다는 힌트 "연속된 수"라는 힌트가 있기 때문에 우리는 연속된 수의 시작수 (a 라고 하겠다)만 찾으면 된다. 만약 a부터 연속된 l개의 수의 합을 구한다고 가정하자 a a+1 a+2 .....