알고리즘 문제풀이
-
[백준/BOJ] 4179번 불! (C++)알고리즘 문제풀이/백준 2021. 1. 13. 19:52
www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 조금 색다른 유형의 BFS 문제 유형이었습니다. BFS를 두번 진행해야하는데, 먼저 불의 BFS를 진행하여 불의 확산시간을 fvisit 배열에 기록하고, 다음에 지훈 BFS를 진행하여 불의 확산시간과 비교하면서 이동시간을 기록합니다. 지훈이가 특정 위치에 이동하기 위해선 불의 확산이 진행되지 않은 곳이거나, 그 위치에서의 불의 확산 시간과 지훈이의 이동시간을 비교해 불의 확산시간이 더 커야 이동할..
-
[백준/BOJ] 7576번 토마토 (C++)알고리즘 문제풀이/백준 2021. 1. 13. 18:29
www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net BFS 유형의 문제입니다. 토마토가 있는 위치를 벡터에 담아서 큐에 넣어줬습니다. 큐가 진행되면서 visit 배열에 최소 일수가 기록됩니다. 예외처리만 제대로 해준다면 어렵지 않은 문제였습니다. #include #include #include #include using namespace std; int m, n; int map[1001][1001]; int visit[1001][1001]; in..
-
[백준/BOJ] 2251번 물통 (C++)알고리즘 문제풀이/백준 2021. 1. 13. 17:30
www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net BFS 유형의 문제였습니다. (다시 풀기) 세개의 물통이 있을 때, 한 물통에서 다른 하나의 물통으로 물을 쏟아붓는 경우의 수는 다음과 같습니다. a->b a->c b->a b->c c->a c->b 위의 6가지 경우를 BFS를 탐색해주는데, 이때 두가지 경우를 고려해줘야합니다. 1. 비우는 물통의 물 양 + 채우는 물통의 물 양 > 채우는 물통의 크기 2. 비우는 몰통의 물 양 + 채우는 ..
-
[프로그래머스/Level 2] 이진 변환 반복하기 (C++)알고리즘 문제풀이/프로그래머스 2021. 1. 13. 15:56
programmers.co.kr/learn/courses/30/lessons/70129 코딩테스트 연습 - 이진 변환 반복하기 programmers.co.kr 1. 무한루프 안에서 문자열 s의 모든 0을 제거합니다. 2. 제거할 때마다 제거한 횟수를 더해줍니다. 3. 0이 제거된 문자열의 길이를 2진수로 변환해줍니다. 4. 변환이 끝나고 변환한 횟수를 더해줍니다. 5. 이러한 과정을 문자열의 길이가 1이 될 때까지 반복합니다. #include #include using namespace std; string getBinary(int num) { string strBinary = ""; while(1) { if(num == 0) break; strBinary.insert(0, to_string(num % ..
-
[백준/BOJ] 16947번 서울 지하철 2호선 (C++)알고리즘 문제풀이/백준 2021. 1. 12. 16:46
www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 그래프 + DFS + BFS 유형의 복합적인 문제입니다. (다시 풀기) 먼저 순환선을 이루는 역을 알아내기 위해서 사이클을 만들어내는 정점을 찾아내야 하는데, DFS를 통해 탐색하다가 처음 시작 위치로 돌아오는 경우를 찾으면 됩니다. (16929번 문제와 비슷합니다.) 이러한 탐색을 1번 정점 ~ n번 정점까지 실행하면서 체크를 한 후, 사이클이 아닌 정점만 따로 BFS를 통해 사이클..
-
[백준/BOJ] 16929번 Two Dots알고리즘 문제풀이/백준 2021. 1. 11. 23:49
www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 브루트 포스(완전 탐색) + DFS 유형의 문제였습니다. (다시 풀기) 문제의 조건에서 싸이클의 의미가 무엇인지 아는게 중요한데, DFS 탐색을 진행하면서 처음 탐색을 시작했던 좌표로 다시 돌아오는 것을 의미합니다. 따라서 시작 좌표로 다시 돌아오기 위해서 종료 조건 체크를 방문 체크 전에 해주어야 합니다. 이때 종료 조건에서 cnt >= 3 이 의미하는 것은 지나온 경로가 최소 3개 이상이여야 한다는..
-
[백준/BOJ] 2910번 빈도 정렬 (C++)알고리즘 문제풀이/백준 2021. 1. 11. 03:23
www.acmicpc.net/problem/2910 2910번: 빈도 정렬 첫쨰 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다. www.acmicpc.net 조금 까다로웠던 정렬 문제입니다. (다시 풀기) 빈도 수를 기준으로 내림차순 정렬하고, 빈도 수가 같다면 원래 순서를 유지해야하는 문제입니다. 예를들어, 4 2 2 1 2 1 이 입력값이라면 출력값은 2 2 1 1 이 나와야 합니다. 이를 구현하기 위해서 두 개의 map을 사용했는데, 각각 입력값의 빈도수, 입력값의 순서를 저장합니다. 빈도 수를 저장한 map을 벡터로 값을 옮기고, cmp 함수를 만들어 입력값을 저장한 map을 이용해주었습니다. #in..
-
[백준/BOJ] 10825번 국영수 (C++)알고리즘 문제풀이/백준 2021. 1. 10. 22:02
www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 정렬 유형의 문제입니다. 한 벡터에 많은 입력값을 받아야하는데, 서로 타입도 달라서 따로 Info라는 구조체를 만들어줬습니다. 그 후 입력값을 벡터에 저장하고, cmp함수를 조건에 맞게 구현한 후 정렬해주었습니다. #include #include #include using namespace std; struct Info { string name; int korean, english, mat..