늦깎이 IT

[백준 3190번] 뱀 1. 뱀의 몸통 좌표를 Deque 자료구조를 활용해서 저장한다. 머리를 움직일 때에는 Deque의 first에 추가하고 뱀의 꼬리를 자를 때는 Deque의 last에서 삭제한다. 2. 뱀의 전체 몸통이 차지하는 부분을 체크하기 위해 visited 배열을 선언하고, 뱀의 몸통이 위치한 자리마다true로 체크한다. 3. 현재 이동방향에 따라 머리를 한칸 전진시킨다.1) 머리를 전진시켰을 때, 이미 visited[row][col] = true이면, 뱀의 머리가 뱀의 몸통 중 일부를 만났다는 것이므로 종료한다.2) 머리를 전진시켰을 때, 사과가 있다면 뱀의 꼬리를 자르지 않는다.3) 머리를 전진시켰을 때, 빈칸이라면 꼬리를 자른다.4) 머리를 전진시켰을 때, 벽이라면 종료한다. 4. 현재..

[SWEA 2105번] 디저트 카페 URL 1. N X N의 Map에서, 가능성이 있는 조합을 모두 찾는다. 예를 들어, 4 X 4의 2차원 배열에서 탐색할 수 있는 칸의 조합은 왼쪽아래, 오른쪽아래, 오른쪽위, 왼쪽위 순서로 탐색했을 때 다음과 같다. 1) 왼쪽아래 2칸 // 오른쪽아래 1칸 // 오른쪽위 2칸 // 왼쪽위 1칸2) 왼쪽아래 1칸 // 오른쪽아래 2칸 // 오른쪽위 1칸 // 왼쪽위 2칸3) 왼쪽아래 1칸 // 오른쪽아래 1칸 // 오른쪽위 1칸 // 왼쪽위 1칸 2. 4 X 4 2차원 배열의 어느 지점에서, 1번에서 구했던 각 방향마다의 이동칸수가 가능하다면, 탐색을 시작한다.탐색할 때에는 디저트의 종류는 1부터 100이므로 boolean형 배열을 선언해서 확인한다. [소스 코드]12..

[SWEA 5644번] 무선충전 URL 1. 10 X 10 Map에 배터리의 해당 정보를 비트마스크를 이용하여 저장한다. 1) 0번 배터리 : (1

[5650. [모의 SW 역량테스트] 핀볼 게임 URL] 1. 입력으로 주어지는 N X N 핀볼 게임판에서, 빈공간에서 4방향 (동, 서, 남, 북)으로 공을 굴려가며 최대 값을찾는다. 2. 이 문제에서 탐색 중단 조건은 블랙홀(-1)을 만났거나, 처음 시작 위치로 되돌아오는 경우이다. 3. N X N의 핀볼 게임판의 가장자리는 "벽"이라고 가정한다. 즉, N이 아닌 N+2만큼의 2차원배열을 선언하고 가장자리에 "5" 짜리 블럭을 세운다. 4. 공을 굴리는 도중, 블럭을 만났다면 방향을 바꿔주고, 웜홀을 만났다면 다른 웜홀 위치로 이동시킨다. [전체 소스코드]1234567891011121314151617181920212223242526272829303132333435363738394041424344454..

이번 포스팅에서는 이진 검색 트리에 대해서 알아봅니다.[전체 구현 소스코드 확인하기][전체 구현 이클립스 프로젝트 확인하기] 우선, 데이터를 저장, 검색, 삭제 등을 할 때 사용되는 자료구조는 대부분 배열과 연결 리스트를 사용합니다.저장, 검색, 삭제 등의 연산(?)을 할 때 배열과 연결 리스트에서 걸리는 시간 복잡도를 우선적으로 확인해봅시다. 1. 데이터가 정렬되지 않은 상태일 때, [배열을 사용할 경우]1) 검색 - 원하는 데이터를 찾기 위해서는 배열의 처음부터 끝까지 모두 확인해야 하므로 O(N)만큼의 시간이 걸립니다. 2) 저장 - 데이터들이 정렬되지 않은 상태이므로, 배열의 맨 마지막에 데이터를 저장하면 되기 떄문에 O(1)만큼의 시간이 걸립니다. 3) 삭제 - 삭제할 데이터를 검색하기 위한 시..

이번 포스팅에서는 이진 트리의 순회 방법에 대해 알아봅니다. [이진 트리] 1. 중위 순회 (Inorder-Traverse)A → B → C → D → E → F → G → H → I1) 왼쪽 자식 노드를 중위 순회한다.2) 루트 노드를 방문한다.3) 오른쪽 자식 노드를 중위 순회한다. [의사 코드]12345INORDER-TRAVERSE(x) if x is not NULL then INORDER-TRAVERSE(left[x]) print key[x] INORDER-TRAVERSE(right[x])cs2. 후위 순회 (Postorder-Traverse)A → C → E → D → B → H → I → G → F1) 왼쪽 자식 노드를 후위 순회한다.2) 오른쪽 자식 노드를 후위 순회한다.3) 루트노드를 방문..

[알고스팟 TSP1 URL] 1. 이 문제는 완전탐색으로 풀었습니다. N개의 도시가 있을 때, 출발 도시를 제외한 나머지 도시들을 방문하는경우의 수는 (N-1)!입니다. 문제에서 N의 입력이 8이하이므로 완전탐색으로 풀어도 시간초과가 나지 않습니다. 2. 시작 도시를 정한 후, 그 도시로부터 순회를 시작합니다. 모든 도시를 돌았다면 최소 값을 갱신해줍니다. [소스 코드]123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384import java.io.BufferedReader;i..

[알고스팟 게임판 덮기 링크] 1. L자 모양의 블럭으로 게임판을 덮는 경우의 수를 구하는 문제인데, 이는 L자 모양의 블럭으로 게임판을덮는 순서와는 상관이 없다. 즉, 순서가 어떻게 되든지간에 게임판을 덮는 모양이 같다면 하나의 경우로 취급한다. 2. 맨 위쪽, 맨 왼쪽부터 게임판이 덮이지 않은 위치를 찾는다. 그리고 그 위치에서 부터 L자 모양의 블럭을 놓는다. - 여기서, 이전의 칸들은 이미 블럭이 덮여있다고 가정해야한다. 즉, L자 모양의 블럭을 해당 위치에 놓을 때,아래쪽 혹은 오른쪽으로만 뻗어나가게 해야한다. - 소스 코드에서, coverDir[][][] 배열을 참고하기 바란다. 3. 해당 위치에서, L자 모양의 블럭을 둘 수 있는지 없는지를 따로 확인하지 않는다. Map의 범위를 벗어나지 않..