넘치게 채우기

https://www.acmicpc.net/problem/2178BOJ - 미로 탐색문제 유형: 행렬, bfs문제 난이도: Silver I시간 제한: 1초메모리 제한: 192MB 문제N×M크기의 배열로 표현되는 미로가 있다.101111101010101011111011미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다. 입력첫째 줄에 두 정수..

https://www.acmicpc.net/problem/2606BOJ - 바이러스문제 유형: 그래프, 연결 요소, bfs, dfs문제 난이도: Silver III시간 제한: 1초메모리 제한: 128MB 문제신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때..

https://www.acmicpc.net/problem/2667BOJ - 단지번호붙이기문제 유형: 그래프, bfs문제 난이도: Silver I시간 제한: 1초메모리 제한: 128MB 문제과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 입력첫 번째 줄에는 지도의 크기 N(정사각형..

https://www.acmicpc.net/problem/1697BOJ - 숨바꼭질문제 유형: bfs문제 난이도: Silver I시간 제한: 2초메모리 제한: 128MB 문제수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위..

https://www.acmicpc.net/problem/20303BOJ - 할로윈의 양아치문제 유형: 유니온-파인드, 다이나믹 프로그래밍, 배낭 문제문제 난이도: Gold III시간 제한: 1초메모리 제한: 1024MB 문제Trick or Treat!!10월 31일 할로윈의 밤에는 거리의 여기저기서 아이들이 친구들과 모여 사탕을 받기 위해 돌아다닌다. 올해 할로윈에도 어김없이 많은 아이가 할로윈을 즐겼지만 단 한 사람, 일찍부터 잠에 빠진 스브러스는 할로윈 밤을 즐길 수가 없었다. 뒤늦게 일어나 사탕을 얻기 위해 혼자 돌아다녀 보지만 이미 사탕은 바닥나 하나도 얻을 수 없었다.단단히 화가 난 스브러스는 거리를 돌아다니며 다른 아이들의 사탕을 빼앗기로 마음을 먹는다. 다른 아이들보다 몸집이 큰 스브러스에..

https://leetcode.com/problems/minimum-length-of-string-after-operations/description/leetcode - Minimum Length of String After Operations문제 유형: 문자열 처리, 그리디문제 난이도: Medium 문제You are given a string s.You can perform the following process on s any number of times:Choose an index i in the string such that there is at least one character to the left of index i that is equal to s[i], and at least one ch..

https://www.acmicpc.net/problem/12100BOJ - 2048(Easy)문제 유형: 구현, 시뮬레이션, 백트래킹, 브루트 포스문제 난이도: Gold I시간 제한: 1초메모리 제한: 512MB 문제2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다) 의 경우에서 위로 ..

https://leetcode.com/problems/check-if-a-parentheses-string-can-be-valid/description/leetcode - Check if a Parentheses String Can Be Valid문제 유형: 문자열 처리, 2-pass문제 난이도: Medium 문제A parentheses string is a nonempty string consisting only of '(' and ')'. It is valid if any of the following conditions is true:It is ().It can be written as AB (A concatenated with B), where A and B are valid parentheses..

https://www.acmicpc.net/problem/16724BOJ - 피리 부는 사나이문제 유형: 그래프 이론, 서로소 집합, dfs문제 난이도: Gold III시간 제한: 1초메모리 제한: 256MB 문제피리 부는 사나이 성우는 오늘도 피리를 분다.성우가 피리를 불 때면 영과일 회원들은 자기도 모르게 성우가 정해놓은 방향대로 움직이기 시작한다. 성우가 정해놓은 방향은 총 4가지로 U, D, L, R이고 각각 위, 아래, 왼쪽, 오른쪽으로 이동하게 한다.이를 지켜보던 재훈이는 더 이상 움직이기 힘들어하는 영과일 회원들을 지키기 위해 특정 지점에 ‘SAFE ZONE’ 이라는 최첨단 방음 시설을 만들어 회원들이 성우의 피리 소리를 듣지 못하게 하려고 한다. 하지만 예산이 넉넉하지 않은 재훈이는 성우가..

https://leetcode.com/problems/construct-k-palindrome-strings/description/leetcode - Construct K Palindrome Strings문제 유형: 문자열 처리, 팰린드롬문제 난이도: Medium 문제Given a string s and an integer k, return true if you can use all the characters in s to construct k palindrome strings or false otherwise. 문자열 s와 정수 k가 주어집니다. 만약 s의 글자들로 k개의 팰린드롬 문자열로 만들 수 있으면 true를 아니면 false를 반환하시오. 풀이꽤 트리키해 보일 수 있지만, 문제를 간단하게 만들..