컴맹에서 개발자 되기

백준 2638 치즈 BFS를 이용한 문제이다. https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net 풀이 방법 1) 외부 공기와 내부 공기를 분리한다. (BFS 사용) - 함수명 outsideBFS() - 문제 조건에 맨 가장자리는 치즈가 놓이지 않는다고 했으니, 0,0을 큐에 넣어서 외부 공기를 체크한다. - 여기에 체크되지 않은 공간은 외부 공기가 아니다. 2) BFS를 통해 녹을 수 있는 치즈를 체크한다. - 함수명 : BFS => m..

1. 들어가며🤗 안녕하세요. 이노베이션 아카데미 인턴 장준영입니다. 제가 두 달 동안 맡은 프로젝트는 로그 분석기였습니다. 맡은 프로젝트에 관련된 내용과 로그에 대해 공부한 내용을 카뎃, 피시너, 이노베이션 아카데미의 관계자 분들께 공유하고 싶어 글을 작성합니다. (글에 내용의 오류가 있거나 틀린 부분이 있다면 언제든지 지적해주세요 !) 2. 로그란?✍️ 저는 얼마 전까지만해도 로그의 중요성에 대해 알지 못했습니다. 하지만 로그에 대해 알아가면 알아갈수록 이 녀석이 정말 중요하다는 것을 느끼게 되었습니다. 혼자만 중요한 사실을 느낄 수 없으니, 여러분도 한번 아래의 질문에 대해 생각해보면서 로그에 대한 중요성을 같이 느껴봅시다 ! Q1. 게임에서 수백 수천만의 아이템이 복사되어서 여러 유저들에게 들어갔다..

백준 1600 말이 되고픈 원숭이 BFS를 이용한 문제이다. 말이 이동하는 경우, 원숭이가 이동하는 경우를 모두 계산해서 풀면 된다. https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있는 곳으로는 이동할 수 없다. 시작점과 도착점은 항상 평지이다. W와 H는 1이상 200이하의 자연수이고, K는 0이상 30이하의 정수이다. www.acmicpc.net 풀이 방법 1) 3차원 배열을 이용해서, 말처럼 이동하는 경우를 고려해야한다. 2) 말 처럼 이동하는 경우만 ..

백준 1629 곱셈 재귀로 풀어야 풀 수 있는 문제이다. 재귀에 약한 나는 고생을 많이 했다 ㅠ https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 풀이 방법 1) 이 문제의 시간제한은 2초이다. 1초에 3~5억 번의 연산을 한다고 가정하면, 2초는 10억 번 안에 연산을 끝내야 한다. 2) 최악의 경우 O(n)이라면, 문제의 주어진 수가 최대 21억이기 때문에 시간 초과가 뜨게 된다. 3) 즉, O(n) 보다 낮은 알고리즘을 이용해한다. 4) b를 짝수 일 때, 홀수 일 때를 나눠서 생각해본다. 2^10이면 b..

백준 2644 촌수계산 완전 탐색 문제이다. https://www.acmicpc.net/problem/2644 문제풀이 1) 주어지는 좌표(촌수)에 대한 그래프를 생성한 후, 시작 좌표(촌수) 끝 좌표(촌수)의 거리를 구하면 되는 문제이기 BFS, DFS 둘 중 하나를 쓰면된다. 2) 나는 BFS가 더 편하기에 BFS를 사용했다.. #include #include #include #include #include using namespace std; int a[102][102]; queue q; int check[102]; int n, s, e, m, x, y; void input_data() { cin >> n >> s >> e >> m; for (int i = 0; i >..

백준 9466번 텀 프로젝트 시간초과에 주의해야되는 문제이다. https://www.acmicpc.net/problem/9466 풀이 방법 1) 한번에 탐색만에 사이클이 있고, 없고를 판단하면서 지나가야한다. 2) 1->2->3->4->5->4 라는 것이 있으면 4,5가 사이클이다. 여기서 4,5가 사이클임을 파악해야되고, 6번으로 바로 넘어가야 시간초과가 뜨지 않는다. #include #include #include #include using namespace std; int ans; int visited[100000]; //방문횟수 담는 배열 bool check[100000]; // 사이클을 찾았다는 뜻 int student[100000]; int T, number; void input_data() ..

백준 6593 상범 빌딩 3차원 bfs문제이다 https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 문제 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서 www.acmicpc.net 풀이 방법 1) bfs로 해결하면 된다. 2) 큐, 배열 초기화 잊지 말자 ! #incl..

백준 2146번 다리 만들기 BFS로만 풀 수 있지만, DFS와 BFS 둘 다 이용할 수 있는 문제이다. https://www.acmicpc.net/problem/2146 풀이방법 1) 각 나라를 구분짓기 위해 bfs나 dfs를 사용한다. 나는 bfs를 사용했다. 2) 각 나라를 구분지은 후, 나라와 나라 사이의 최단거리를 BFS로 구한다. 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 ..

백준 13913 숨바꼭질4 https://skd03052.tistory.com/150 의 응용문제이다. bfs와 역추적이 필요하다. https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 www.acmicpc.ne..

백준 13549 숨바꼭질3 bfs 문제이다. 기존 숨바꼭질과 로직이 살짝 다르다. https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 www.acmicpc.net 풀이방법 1) 순간이동의 시간은 0초니깐 순간이..