사과를 먹을 땐 사과를 먹어요

문제 프로그래머스 2018 카카오 공채 - 비밀지도 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 배열로 입력받은 10진수들을 모두 2진수로 바꿔줘야한다 -> Integer.toBinaryString() 사용 두 개의 지도를 주어진 조건에 맞게 합쳐야하므로 OR 연산을 실행한다 -> arr1[i] | arr2[i] 그런데 2진수로 바꾸면서 1이 나오기 전의 0들은 사라져버리기 때문에 String.format을 사용해서 사라진 0들을 살려줘야한다 ⭐️map[i] = String.format("%" + n + "s", map[i]); -> n의 크기만큼..

문제 N×M크기의 배열로 표현되는 미로가 있다. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다. 입력 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력..

문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다. ..

문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다. 출력 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 풀이 수빈이가 이동하는 방법은 총 3가지 현재위치+1 현재위치-1 현..

문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다. 토마토를 창고에 보관하는 격자모양의 상자들..

BFS (Breadth-First Search, 너비 우선 순회) BFS 알고리즘은 다음 순서로 노드를 방문 L0 : {s}, 여기서 s는 출발 노드 L1 : L0과 연결된 모든 이웃 노드들 L2 : L1의 이웃들 중 L0에 속하지 않는 노드들 ... Li : Li-1의 이웃들 중 Li-2에 속하지 않는 노드들 큐를 이용한 BFS 출발 노드를 check(방문 표시) 출발 노드를 큐에 넣음 큐가 빌 때까지 while문 반복 맨 앞에 있는 노드를 큐에서 꺼냄 꺼낸 큐의 인접한 노드들 중, 아직 방문되지 않은 노드들을 check한 후 큐에 넣음 큐에 인접 노드를 넣는 순서는 중요하지 않음 다시 맨 앞에 있는 노드, 여기서는 노드 2를 꺼낸 후 노드 2의 인접한 노드들 중 방문하지 않은 노드들을 큐에 넣음 (빨..

무방향 그래프 G = (V, E) V : 노드(node) 혹은 정점(vertex) E : 노드쌍을 연결하는 에지(edge) 혹은 링크(link) 개체(object)들 간의 이진관계 표현 n = |V|, m = |E| 인접 행렬 (adjacency matrix) 노드가 n개인 그래프를 nxn행렬로 표현 가능 인접 리스트 (adjacency list) 노드가 n개인 그래프를 크기가 n인 배열로 표현 가능 노드 개수는 에지의 갯수의 2배 방향 그래프 (directed Graph) G = (V, E) 에지 (u, v)는 u에서 v로의 방향을 가짐 인접 행렬과 인접 리스트 각 에지마다 방향이 있으므로 인접 행렬은 비대칭 인접 리스트는 m개의 노드를 가짐 가중치 그래프 (weighted Graph) 에지마다 가중치..

Comparison sort 데이터들간의 상대적 크기 관계만을 이용해 정렬하는 알고리즘 데이터들간의 크기 관계만 정의되어 있으면 어떤 데이터에든 적용 가능 (문자열, 알파벳, 사용자 정의 객체 등) bubble sort, insertion sort, merge sort, quick sort, heap sort 등 Non-Comparision sort 정렬할 데이터에 대한 사전지식을 이용해 정렬하는 알고리즘 Bucket sort, Radix sort 등 Non-Comparision sort Counting sort n개의 정수를 정렬하라. 단, 모든 정수는 0에서 k사이의 정수이다. (n=8이고, k=5인 경우) 크기가 8인 배열 A에 0부터 5까지의 숫자가 랜덤으로 배열되어있음 배열 C는 각 숫자의 갯수..