전체 글
-
[백준/BOJ] 2206번 벽 부수고 이동하기 (C++)알고리즘 문제풀이/백준 2021. 10. 29. 15:04
https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 벽 뚫기 사용의 유무를 체크하기 위해 3차원 배열을 이용해야 한다. 해당 아이디어만 잘 떠올린다면 어렵지 않게 해결할 수 있는 BFS 문제였다. #include #include #include #include using namespace std; int N, M; int map[1001][1001]; int visit[2][1001][1001]; int dx[4] = {-..
-
[백준/BOJ] 5014번 스타트링크 (C++)알고리즘 문제풀이/백준 2021. 10. 28. 17:26
https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 1697번 숨바꼭질 문제와 비슷한 BFS 문제였다. 그래서 어렵지 않게 해결 ㅎ (범위 처리만 잘 해주자) #include #include #include #include using namespace std; int F, S, G, U, D; int visit[1000001]; int BFS() { queue q; q.push(S); visit[S] = 0; while(!q.empty()) { int now ..
-
[백준/BOJ] 1543번 문서 검색 (C++)알고리즘 문제풀이/백준 2021. 10. 27. 14:40
https://www.acmicpc.net/problem/1543 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net 간단한 문자열 탐색 문제였다. 풀이를 설명할 필요없이 코드를 보면 이해가 갈 것이다. #include #include using namespace std; int main(void) { freopen("input.txt", "rt", stdin); ios_base::sync_with_stdio(false); cin.tie(0); string str, word; getline(cin, str); getl..
-
[백준/BOJ] 2146번 다리 만들기 (C++)알고리즘 문제풀이/백준 2021. 10. 26. 16:06
www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 구현 부분에서 조금 애먹었지만 풀이 로직은 정확하게 맞은 문제 1년 후에 다시 풀었더니 한번에 맞췄다. ㅎㅎ BFS를 두번 사용해야하는데, 첫번째 BFS는 각 섬의 영역에 번호를 매기기 위해 사용하고, 두번째 BFS는 각 섬에서 다른 섬까지의 최소 거리를 구하는데 사용해서 문제를 해결했다. #include #include #include #include #include #include using namespace s..
-
[백준/BOJ] 2468번 안전 영역 (C++)알고리즘 문제풀이/백준 2021. 10. 13. 17:16
https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net BFS 문제, map의 값이 전부 1일 때 답이 1이 나와야 하는데, 이를 주의해야 한다. (비가 안오는 경우도 있으므로) #include #include #include #include using namespace std; int n, answer; int map[101][101]; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, -1, 0, 1}; bool visit[10..
-
[백준/BOJ] 16506번 CPU (C++)알고리즘 문제풀이/백준 2021. 10. 10. 18:58
https://www.acmicpc.net/problem/16506 16506번: CPU 디지털하드웨어설계 과목의 최종 프로젝트는 16-bit CPU를 설계하고 Verilog 언어로 구현하는 것이다. 본인이 구현한 CPU가 제대로 동작하는지 테스트하기 위해서는 기계어 코드를 입력으로 주어야 www.acmicpc.net 다시 풀기 : 제한시간 20분 빡구현 문제이다. 12~15번 비트 조건 처리를 하는데 조금 애먹었다. 문제 해결 방법 자체는 어렵지 않다. opcode에 해당하는 비트와 4, 5번 비트를 map을 선언해 미리 이진수 값을 넣어줬다. 나머지 입력값을 이진수로 바꿔서 더해주고, 12~15번 비트 처리일 때 4번 비트가 1이면 4개의 비트가 필요하므로, 이에 대한 처리를 따로 진행해줬다. (이때..
-
[백준/BOJ] 3568번 iSharp (C++)알고리즘 문제풀이/백준 2021. 10. 10. 17:20
https://www.acmicpc.net/problem/3568 3568번: iSharp 입력으로 주어진 변수 선언문을 문제의 조건에 맞게 변형한 뒤, 한 줄에 하나씩 출력한다. 변수형과 변수명 사이에는 공백이 하나 있어야 한다. 출력은 입력으로 주어진 변수 선언문에서 변수가 www.acmicpc.net 구현 자체는 어렵지 않은데 고려해야 할 사항이 많아서 까다롭다. 첫 번째로 변수 오른쪽 옆에 붙은 &, *, []을 왼쪽으로 역순으로 옮길 때, []은 모양이 유지 되어야 한다. 두 번째는 변수명이 두 글자 이상일 수 있다. 예를들어 aa, AbCdE 등이 될 수 있다. #include #include #include using namespace std; int main(void) { //ios_bas..
-
[프로그래머스/위클리 챌린지] 9주차 (C++)알고리즘 문제풀이/프로그래머스 2021. 10. 8. 18:03
https://programmers.co.kr/learn/courses/30/lessons/86971 코딩테스트 연습 - 9주차 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 programmers.co.kr BFS와 구현력을 요구하는 어렵지 않은 문제였다. 예전에 네이버에 이와 비슷한 문제가 나온적이 있어서 쉽게 풀었다. 간선을 하나씩 제거한 것을 기록하기 위해 2차원 배열을 이용했다. 그 후 BFS를 이용해 트리를 탐색하는데, 체크한 간선을 구성하고 있는 노드를 탐색하려고 하면 그대로 continue 해준다. 이런식으로 나눠진 트리의 노드 수를 각각 구하고, 이들의 차의 절댓값이..