본문 바로가기
반응형

백준14

[cpp 알고리즘] 백준 13565 침투 [백준] 13565 침투 cpp 풀이알고리즘: 그래프 이론, 그래프 탐색, 너비우선탐색(bfs), 깊이우선탐색(dfs)https://www.acmicpc.net/problem/13565문제 요약- 2차원 격자가 주어지고, 각 격자는 0(전류 흐름)과 1(전류 차단)로 구성되어있다.- 각 전류는 상하좌우로 이동할 수 있다.- 이 때, 격자의 위쪽(outer side)에서 아래쪽(inner side) 까지 전류가 올 수 있는지 YES/NO를 출력해주면 된다.풀이 정리- 완전 기본적인 dfs 문제였다. M*N 격자 안에 있고 아직 방문하지 않은 점이면서 전류가 흐를 수 있는 0의 칸이라면 dfs로 더 탐색해주었다.- 상하좌우 4방향에 dx와 dy배열을 이용했다.- 격자의 맨 위(행=0)인 지점에서 모두 시작했.. 2024. 7. 19.
[cpp 알고리즘] 백준 2422 한윤정이 이탈리에아 가서 아이스크림을 사먹는데 [백준] 2422 한윤정이 이탈리에아 가서 아이스크림을 사먹는데 cpp 풀이알고리즘: 브루트포스 알고리즘https://www.acmicpc.net/problem/2422문제 요약- 아이스크림은 1부터 N까지 N종류의 아이스크림이 있다.- M은 섞어 먹으면 안 되는 조합의 개수이다.- 아이스크림 맛을 3가지 선택할 때, 섞어 먹어도 되는 조합은 몇 가지인지 구하면 된다.풀이 정리1. 조합(nC3)을 이용하여 가능한 모든 경우를 구하고, 섞어 먹어도 되는 조합인지 확인하는 방법을 생각했다.2. 하지만 N의 최대 개수가 200 이었기 때문에, 더 단순하게 삼중 for문으로 구해보았다.3. 3가지 아이스크림이 서로 같이 먹어도 되는 조합인지 확인하기 위해서 vector 안에 배열을 넣어 두어, 두 숫자가 같은 .. 2024. 7. 18.
[cpp 알고리즘] 백준 20152 Game Addiction [백준] 20152 Game Addiction cpp 풀이알고리즘: 수학, 다이나믹 프로그래밍(DP), 조합론https://www.acmicpc.net/problem/20152문제 요약- 집의 좌표(H,H) 에서 PC 방의 좌표(N,N)가 주어진다.- 좌표평면(x,y)에서 y>x인 곳은 갈 수 없다. - 집에서 PC방까지 경로의 개수를 구해야 한다. (단, 상하좌우 방향으로 이동할 수 있고 한 번 이동할 때 거리는 1이다. 또한 항상 최단 경로로 움직인다.)풀이 정리- 최단경로라는 말에 처음에는 bfs로 생각을 하다가, 뒤로 갈 수록 너무 많고 생각보다 규칙이 보여서 dp로 접근했다.- 아래 사진처럼 예제들을 직접 따라 그려보면 어떻게 구하는지 바로 알 수 있다. (지금 보니까 집이랑 PC방 위치를 반대.. 2024. 7. 15.
[cpp 알고리즘] 백준 19844 단어 개수 세기 [백준] 19844 단어 개수 세기 cpp 풀이알고리즘: 구현, 문자열https://www.acmicpc.net/problem/19844 문제 요약문제가 너무... 어렵게 적혀있는 것 같다. 해야하는 것을 쉽게 정리하자면먼저 띄어쓰기와 -(하이픈)을 기준으로 “단어”를 쪼갠다.각각의 “단어”에서, 위처럼 줄어들었을 가능성이 있는 경우(즉, c', j', n', m', t', s', l', d', qu'로 시작하고 어포스트로피 뒤 글자가 모음인 경우) 이 단어들을 한 번 더 분리해 준다.핵심은 여기서 '(어포스트로피) 앞에는 단어(c,j,n,m,t,s,l,d,qu) 가 있어야 하고, '(어포스트로피) 뒤에는 모음(a,e,i,o,u,h)로 시작하는 단어가 오면 된다. =>  ' 앞에는 단어 단위로, ' 뒤에.. 2024. 7. 15.
반응형

티스토리툴바