AndroidTeacher

www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 설명 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단..

www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 설명 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 문제이다. 풀이 과정 풀이 ① - 그래프를 인접리스트로 구현 graph[a].append(b)의 의미는 a번에 b번을 연결시키는 뜻이다. 즉 1번에 2, 3, 4 가 연결되어 있으면 graph의 1번째 행에 2,3,4를 추가하게 된다. 그리고 문제에서, 번호가 작은것 부터 탐색하라고 했으므로 정렬을 ..

programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 문제 설명 문제의 설명이 위 링크에 상세하게 나와있습니다. (0,0) 칸 부터 (N-1, N-1)칸 ..

www.acmicpc.net/problem/15658 15658번: 연산자 끼워넣기 (2) N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 연산자의 개수 www.acmicpc.net 문제 설명 주어진 숫자와 연산자로 만들 수 있는 수식의 결과값 중 최대값과 최소값을 구하면 됩니다. 풀이 과정 DFS의 백트래킹을 이용해서 풀어도 되고, 아래의 코드처럼 변수로 변하는 변수를 넘겨주어도 됩니다. 핵심은 주어진 숫자와 연산자로 조합할 수 있는 모든 경우의 수를 따져야 합니다. 백트래킹을 이용한 코드는 https://hongcoding.tistory.com..

programmers.co.kr/learn/courses/30/lessons/43163# 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 문제 설명 두개의 단어 begin과 target이 주어지며 단어의 집합 words가 주어집니다. begin은 words에 있는 단어 중 하나로 변경 가능하며, 한 번에 하나의 알파벳만 변경가능합니다. 이러한 과정을 통해 target까지 가는데 몇 단계의 과정을 거쳐야 하는지를 출력하면 됩니다. 문제의 자세한 설명은 위 링크에 나와있..

문제 설명 www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 체스판 위의 나이트가 최소 몇번을 움직여 도착지까지 이동할 수 있는지를 구하는 문제이다. 풀이 과정 나이트가 이동할 수 있는 경로는 체스의 나이트와 똑같이 가로2칸 이동후 세로1칸 혹은 가로1칸 이동 후 세로1칸 이기 때문에 8가지 상황이 발생한다. visited의 각 칸에는 그 칸까지 오는데 필요한 횟수가 저장되어 있으며 초기는 모두 0으로 저장되어 있다. 즉, 아직 밟지않은 칸은 모두 0으로 초기화..

문제 설명 www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net N×M의 행렬로 표현되는 맵에서 0은 이동할 수 있는칸, 1은 벽(이동할 수 없는 칸)을 나타낸다. 단, 벽을 부수고 이동할 수 있는 기회가 1번 주어지므로 부셨을 때 이동경로가 짧아진다면 부셔도 된다. (1, 1)에서 시작하여 (N,M)까지 가는데 최단거리를 출력하면 된다. 풀이 과정 전형적인 BFS 의 경로찾기 문제에 벽을 부술 수 있다는 특징이 포함된 문제이다. 중간에 ..

www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 설명 수빈이는 동생과 숨바꼭질을 한다. 수빈이의 좌표는 N, 동생의 좌표는 K이다. 수빈이의 위치가 X일 때, 1초 후에 X+1, X-1 X*2 중에 하나로 이동할 수 있다. 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초인지를 구하면 된다. 풀이 과정 BFS를 이용하여 풀었다. 변수에 대해 먼저 설명하자면, count는 일 수, flag는 찾은 여부를 나타내는 변수이다...

www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 문제 설명 가로 M, 세로 N 의 토마토 상자가 H높이만큼 쌓여져 있다. 즉 3차원 배열의 형태로 쌓여져 있다. 이 토마토는 보관 후 하루가 지나면 익은 토마토들의 인접(상하좌우위아래)한 토마토들이 모두 익게 된다. 이 토마토들이 모두 익게되는데 며칠이 걸리는지 최소 일수를 구하면 된다. 풀이 과정 토마토들의 좌표는 graph[x][y][z]로 나타낼 수 있다. 기존 문제들과의 차이점이라..

www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제 설명 R x C 크기의 보드판이 있다. 이 보드판의 각 칸에는 대문자 알파벳이 하나씩 적혀있으며, 이 보드판을 움직이는 말은 현재 (1,1)에 위치하고 있다. (시작점에 위치) 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있으며, 새로 이동하는 칸에 적힌 알파벳은 지금까지 지나온 알파벳과 겹쳐서는 안된다. 즉, 같은 알파벳 칸을 두 번 이상 지나갈 수 없다. 좌측 상단부터 시작하여 말이..