마코

https://school.programmers.co.kr/learn/courses/30/lessons/43163

문제

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.
   예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

제한사항
각 단어는 알파벳 소문자로만 이루어져 있습니다.
각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
begin과 target은 같지 않습니다.
변환할 수 없는 경우에는 0를 return 합니다.

접근

• 각 단어를 정점으로 한다.
• 인접 리스트로 알파벳 차이가 하나인 것끼리 인접 리스트에 추가한다.
  • 각 문자별로 하나씩 비교해서 다른 것의 개수가 1개 이어야 한다.
• begin부터 bfs탐색으로 target을 찾게되는 최솟값을 찾는다.
  
  • 이미 탐색한 정점은 방문 처리하고 재방문하지 않는다.
  • 정점에 대한 깊이를 저장하고 다음 정점의 깊이는 현재 정점의 깊이 + 1

예외 사항 - words안에 target이 없다면 아예 갈 수 없기 때문에 0을 반환하고 종료해야 하는데 이 처리를 안해주면 words에 없더라도 target 정점을 도달이 가능하여 예상치 못한 값이 나올 수 있다.

문자열이고 중복이 불가능하기 때문에 인접 리스트를 Map<String, List<String>>으로 구현했다. 이 문제에서는 괜찮지만 중복이 존재하는 경우 Map을 사용하면 결과가 달라질 수 있기 때문에 주의하자. (왠만해서는 List로 구현하는 것이 나아 보이고 이 문제도 인덱스로 처리하면 가능하다.)

코드

• https://github.com/aak2075/algorithm-baekjoon/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/lv3/43163.%E2%80%85%EB%8B%A8%EC%96%B4%E2%80%85%EB%B3%80%ED%99%98

https://school.programmers.co.kr/learn/courses/30/lessons/1844

문제

ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.

지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.

위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.
아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.

첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.

두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.

위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.

만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.

게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.

제한사항
maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.

접근

• 최단 경로로 목적지까지 갈 수 있는지와 그 거리를 계산하는 문제.
• 좌표로 계산하여 상, 하, 좌, 우를 갈 수 있는지 판단하고 갈 수 있다면 큐에 좌표를 담아 bfs탐색을 수행한다.
  • 이동할 x, y좌표가 0 미만이거나 m, n이상인 경우는 갈 수 없다
  • 이동할 x, y좌표가 이미 방문했다면 갈 수 없다.
  • 이동할 x,y 좌표에 벽이 있다면(0이면) 갈 수 없다.
  • 갈 수 있다면 큐에 이동할 좌표를 offer한다.
  • 갈 수 있다면 이동할 좌표를 방문 처리 한다.
  • 갈 수 있다면 현재 좌표의 깊이 + 1을 이동할 좌표의 깊이로 설정한다.
• 큐에서 좌표를 꺼낸 좌표가 도착 지점일 경우 해당 좌표의 깊이를 반환.

깊이를 int로 계산해보려다가 헤멨던 문제.

깊이도 depth[nextY][nextX] = depth[y][x] + 1 이렇게 좌표로 표현하여 해결했다.

코드

• https://github.com/aak2075/algorithm-baekjoon/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/lv2/1844.%E2%80%85%EA%B2%8C%EC%9E%84%E2%80%85%EB%A7%B5%E2%80%85%EC%B5%9C%EB%8B%A8%EA%B1%B0%EB%A6%AC

https://school.programmers.co.kr/learn/courses/30/lessons/43162

[프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr](https://school.programmers.co.kr/learn/courses/30/lessons/43162)

문제

문제 설명
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한사항
컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
computer[i][i]는 항상 1입니다.

접근

• 각 연결된 정점들의 부분집합을 컴포넌트라고 부른다.
• 각 정점에서 bfs를 수행하고 그 횟수를 세면 된다.
• 방문한 점은 visited 처리하기 때문에 각 정점마다 bfs를 수행할 때 방문하지 않은, 즉 연결되어있지 않은 정점의 경우에 bfs를 수행한다.

코드

• https://github.com/aak2075/algorithm-baekjoon/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/lv3/43162.%E2%80%85%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC

https://school.programmers.co.kr/learn/courses/30/lessons/43165

[프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr](https://school.programmers.co.kr/learn/courses/30/lessons/43165)

문제

문제 설명

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

접근

• 입력받은 숫자 배열의 각 요소에 +1을 곱하거나 -1을 곱해서 모두 더한 값이 target인 경우의 수를 센다.
• 함수에서 각 dfs 스텝마다 1 또는 -1을 담은 operation 리스트를 add한다.
• 함수에서 base case를 operation size가 숫자 배열이 됐을 때로 설정하고 이때, operation의 모든 값을 각 숫자 배열 요소에 곱해서 모두 더한 값이 target과 일치하면 횟수를 센다.
• 함수마다 +1을 담은 dfs를 재귀 호출하고 -1을 담은 dfs를 재귀 호출하여 하나의 함수에서 총 두 가지 경우에 대해 재귀 호출한다.
• 모든 횟수를 더하면 끝.

코드

• https://github.com/aak2075/algorithm-baekjoon/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/lv2/43165.%E2%80%85%ED%83%80%EA%B2%9F%E2%80%85%EB%84%98%EB%B2%84

문제

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.

예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.

<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.

M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

5 7 3
0 2 4 4
1 1 2 5
4 0 6 2

3
1 7 13

접근

• M x N 의 좌표 평면을 그리고 모두 true로 할당한다.
• 직사각형이 그려진 공간은 false로 변경한다.
• true인 모든 좌표에 대해서 상, 하, 좌, 우로 bfs 탐색을 수행한다.
  • 상, 하, 좌, 우의 좌표가 0 <= x < N, 0 <= y < M 범위를 벗어나는 경우는 탐색하지 않는다. (x좌표가 N에 해당하고 y좌표가 M에 해당함을 주의)
  • 상, 하, 좌, 우의 좌표가 false인 경우는 탐색하지 않는다.
  • 방문한 좌표는 false로 설정하여 더는 방문을 하지 않고 탐색한 넓이를 1씩 센다
  • bfs가 한 회 끝날 때 마다 width 리스트를 저장한다
• width 리스트를 오름차순 출력하기 위해 마지막에 정렬한다.

코드

• https://github.com/aak2075/algorithm-baekjoon/blob/main/%EB%B0%B1%EC%A4%80/Silver/2583.%E2%80%85%EC%98%81%EC%97%AD%E2%80%85%EA%B5%AC%ED%95%98%EA%B8%B0/%EC%98%81%EC%97%AD%E2%80%85%EA%B5%AC%ED%95%98%EA%B8%B0.java

2
2
0 0
1000 0
1000 1000
2000 1000
2
0 0
1000 0
2000 1000
2000 2000

happy
sad

접근

• 집, 편의점, 페스티벌의 x, y좌표를 정점으로 하는 방향 그래프를 그린다. 
  • 50미터에 맥주 한 병씩 마셔야 이동할 수 있고, 최대 20병을 들고 있을 수 있다.
  • 편의점에 도착하면 무조건 20병을 채우는 것이 멀리갈 수 있기 때문에 편의점을 들르면 20병이 채워진다고 생각한다.
  • 즉, 거리가 1000미터 이하에 편의점이나 페스티벌장이 있으면 갈 수 있고 이를 간선이 연결된 것으로 정한다.
• 완성된 그래프를 bfs 탐색을 수행하고 마지막 지점을 방문했는지 확인해서 방문했다면 happy 아니라면 sad

코드

• https://github.com/aak2075/algorithm-baekjoon/blob/main/%EB%B0%B1%EC%A4%80/Gold/9205.%E2%80%85%EB%A7%A5%EC%A3%BC%E2%80%85%EB%A7%88%EC%8B%9C%EB%A9%B4%EC%84%9C%E2%80%85%EA%B1%B8%EC%96%B4%EA%B0%80%EA%B8%B0/%EB%A7%A5%EC%A3%BC%E2%80%85%EB%A7%88%EC%8B%9C%EB%A9%B4%EC%84%9C%E2%80%85%EA%B1%B8%EC%96%B4%EA%B0%80%EA%B8%B0.java

https://school.programmers.co.kr/learn/courses/30/lessons/42892

문제

전무로 승진한 라이언은 기분이 너무 좋아 프렌즈를 이끌고 특별 휴가를 가기로 했다.
내친김에 여행 계획까지 구상하던 라이언은 재미있는 게임을 생각해냈고 역시 전무로 승진할만한 인재라고 스스로에게 감탄했다.

라이언이 구상한(그리고 아마도 라이언만 즐거울만한) 게임은, 카카오 프렌즈를 두 팀으로 나누고, 각 팀이 같은 곳을 다른 순서로 방문하도록 해서 먼저 순회를 마친 팀이 승리하는 것이다.

그냥 지도를 주고 게임을 시작하면 재미가 덜해지므로, 라이언은 방문할 곳의 2차원 좌표 값을 구하고 각 장소를 이진트리의 노드가 되도록 구성한 후, 순회 방법을 힌트로 주어 각 팀이 스스로 경로를 찾도록 할 계획이다.

라이언은 아래와 같은 특별한 규칙으로 트리 노드들을 구성한다.

• 트리를 구성하는 모든 노드의 x, y 좌표 값은 정수이다.
• 모든 노드는 서로 다른 x값을 가진다.
• 같은 레벨(level)에 있는 노드는 같은 y 좌표를 가진다.
• 자식 노드의 y 값은 항상 부모 노드보다 작다.
• 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
• 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.

아래 예시를 확인해보자.

라이언의 규칙에 맞게 이진트리의 노드만 좌표 평면에 그리면 다음과 같다. (이진트리의 각 노드에는 1부터 N까지 순서대로 번호가 붙어있다.)

이제, 노드를 잇는 간선(edge)을 모두 그리면 아래와 같은 모양이 된다.

위 이진트리에서 전위 순회(preorder), 후위 순회(postorder)를 한 결과는 다음과 같고, 이것은 각 팀이 방문해야 할 순서를 의미한다.

• 전위 순회 : 7, 4, 6, 9, 1, 8, 5, 2, 3
• 후위 순회 : 9, 6, 5, 8, 1, 4, 3, 2, 7

다행히 두 팀 모두 머리를 모아 분석한 끝에 라이언의 의도를 간신히 알아차렸다.

그러나 여전히 문제는 남아있다. 노드의 수가 예시처럼 적다면 쉽게 해결할 수 있겠지만, 예상대로 라이언은 그렇게 할 생각이 전혀 없었다.

이제 당신이 나설 때가 되었다.

곤경에 빠진 카카오 프렌즈를 위해 이진트리를 구성하는 노드들의 좌표가 담긴 배열 nodeinfo가 매개변수로 주어질 때,
노드들로 구성된 이진트리를 전위 순회, 후위 순회한 결과를 2차원 배열에 순서대로 담아 return 하도록 solution 함수를 완성하자.

제한사항

• nodeinfo는 이진트리를 구성하는 각 노드의 좌표가 1번 노드부터 순서대로 들어있는 2차원 배열이다.
  • nodeinfo의 길이는 1 이상 10,000 이하이다.
  • nodeinfo[i] 는 i + 1번 노드의 좌표이며, [x축 좌표, y축 좌표] 순으로 들어있다.
  • 모든 노드의 좌표 값은 0 이상 100,000 이하인 정수이다.
  • 트리의 깊이가 1,000 이하인 경우만 입력으로 주어진다.
  • 모든 노드의 좌표는 문제에 주어진 규칙을 따르며, 잘못된 노드 위치가 주어지는 경우는 없다.

접근

• y좌표가 큰 순서대로 트리에 삽입 연산을 하면 노드의 위치가 바뀔 필요가 없기 때문에 y좌표를 내림차순 정렬하여 순서대로 트리에 삽입한다.
• 트리의 삽입 연산은 현재 노드보다 작으면 left, 크면 rigth에 삽입하는 연산을 재귀로 수행한다.
• 완성된 트리에서 전위 순회와 후위 순회를 수행한다.
• 전위 순회는 현재 노드, 왼쪽 서브트리, 오른쪽 서브트리 순서로 재귀 탐색한다.
• 후위 순회는 왼쪽 서브트리, 오른쪽 서브트리, 현재 노드 순서로 재귀 탐색한다.

코드

• https://github.com/aak2075/algorithm-baekjoon/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/lv3/42892.%E2%80%85%EA%B8%B8%E2%80%85%EC%B0%BE%EA%B8%B0%E2%80%85%EA%B2%8C%EC%9E%84

https://school.programmers.co.kr/learn/courses/30/lessons/42890

문제

프렌즈대학교 컴퓨터공학과 조교인 제이지는 네오 학과장님의 지시로, 학생들의 인적사항을 정리하는 업무를 담당하게 되었다.

그의 학부 시절 프로그래밍 경험을 되살려, 모든 인적사항을 데이터베이스에 넣기로 하였고, 이를 위해 정리를 하던 중에 후보키(Candidate Key)에 대한 고민이 필요하게 되었다.

후보키에 대한 내용이 잘 기억나지 않던 제이지는, 정확한 내용을 파악하기 위해 데이터베이스 관련 서적을 확인하여 아래와 같은 내용을 확인하였다.

• 관계 데이터베이스에서 릴레이션(Relation)의 튜플(Tuple)을 유일하게 식별할 수 있는 속성(Attribute) 또는 속성의 집합 중, 다음 두 성질을 만족하는 것을 후보 키(Candidate Key)라고 한다.
  • 유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.
  • 최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.

제이지를 위해, 아래와 같은 학생들의 인적사항이 주어졌을 때, 후보 키의 최대 개수를 구하라.

위의 예를 설명하면, 학생의 인적사항 릴레이션에서 모든 학생은 각자 유일한 "학번"을 가지고 있다. 따라서 "학번"은 릴레이션의 후보 키가 될 수 있다.
그다음 "이름"에 대해서는 같은 이름("apeach")을 사용하는 학생이 있기 때문에, "이름"은 후보 키가 될 수 없다. 그러나, 만약 ["이름", "전공"]을 함께 사용한다면 릴레이션의 모든 튜플을 유일하게 식별 가능하므로 후보 키가 될 수 있게 된다.
물론 ["이름", "전공", "학년"]을 함께 사용해도 릴레이션의 모든 튜플을 유일하게 식별할 수 있지만, 최소성을 만족하지 못하기 때문에 후보 키가 될 수 없다.
따라서, 위의 학생 인적사항의 후보키는 "학번", ["이름", "전공"] 두 개가 된다.

릴레이션을 나타내는 문자열 배열 relation이 매개변수로 주어질 때, 이 릴레이션에서 후보 키의 개수를 return 하도록 solution 함수를 완성하라.

접근

HashMap으로 index에서 탐색 가능한 경로들을 저장했다. column이 0~3인 경우로 예시를 들어보겠다.

• 백트래킹으로 유일성이 깨지거나 최소성이 깨질 때 까지 탐색하는 것을 column의 개수만큼 반복한다
• 다음과 같이 가능한 decision space가 정의되며 유일성이나 최소성이 깨지기 전까지 탐색하며 완성된 문자열을 저장한다.
• 시작이 0일 때 : 0, 01, 01, 012, 013, 023, 0123
• 시작이 1일 때 : 1, 12, 13, 123
• 시작이 2일 때 : 2, 23
• 시작이 3일 때 : 3
• 이러한 경우 유일성과 최소성 판별이 컬럼의 순서가 유지될 때만 가능하다. ex) 02가 최소인 경우 : ["012", "02"], 03이 최소인 경우 : ["013", "03"]
• 따라서 저장된 결과중에서 다른 문자열을 모두 포함하는 것이 있으면 최소성이 깨지는 문자열이므로 제거한다.
• 백트래킹으로 구했을 때 최소성 판별이 제대로 되지 않아 다시 한번 연산을 해주어야 하기 때문에 더 쉽게 풀 수 있는 방법이 있을것이라 생각한다. 다음에 다시 풀어보자.

코드

• https://github.com/aak2075/algorithm-baekjoon/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/lv2/42890.%E2%80%85%ED%9B%84%EB%B3%B4%ED%82%A4