목록분류 전체보기 (61)
Inor
한 줄로 이어진 톱니바퀴를 회전 시키는 문제입니다. 하나의 톱니바퀴를 회전 시키도록하는 명령어가 들어왔을때, 양 옆의 톱니바퀴에게 영향을 줄 수 있는지를 확인해서 같이 회전 시키도록하는 것이 문제의 핵심입니다. 4개의 톱니바퀴가 회전해야하는 방향을 담을 수 있는 배열을 선언했습니다. 최초로 회전 명령을 받은 톱니바퀴를 시작으로 배열을 너비 탐색했습니다. 문제의 조건에 따라 너비 탐색으로 탐색된 양 옆의 톱니바퀴의 회전 유무를 판단했습니다. 아래는 문제의 링크와 소스 코드입니다. - 문제 : https://www.acmicpc.net/problem/14891 - 소스 코드 import java.util.LinkedList; import java.util.Queue; import java.util.Scann..
- 빅 오 표기법 빅 오 표기법은 프로그램(알고리즘)의 성능을 분석하는 방법들 중 하나로서 최악의 상황을 고려한 시간 복잡도로 표현됩니다. 시간 복잡도란 프로그램이 시작하여 끝나기까지 걸리는 시간을 의미합니다. 빅 오 표기법은 프로그램의 시간 복잡도를 정확하게 나타내는 방법은 아니고 근사치를 나타내는 방법입니다. 그래서 프로그램은 빅 오 표기법으로 표기된 시간 복잡도보다 빠르거나 같게 종료됩니다. 빅 오 표기법은 최고차항만을 사용해서 표기합니다. - 빅 오 표기법의 종류 빅 오 표기법을 설명하는 가장 좋은 방법은 프로그래밍 학습과 마찬가지로 코드를 통해서 확인하는 것 입니다. 빅 오 표기법은 O(n), O(1) 등과 같이 앞에 대문자 O를 써주고 안에 시간 복잡도를 표기해주면 됩니다. 빅 오 표기법으로 ..
- 배열을 이용한 연결 리스트 구현 연결 리스트는 보통 메모리를 동적으로 할당 받아서 데이터와 주소값을 갖고 있는 노드를 만들고, 그 노드를 이용해서 연결 리스트를 구성합니다. 그러면 메모리의 동적 할당이 안되는 상황에서 연결 리스트를 구현해야 하는 상황이라면 어떻게 해야 될까요? 저는 2개의 배열을 선언해서 하나는 데이터를 담고 다른 하나는 배열의 인덱스(데이터의 임시 주소값)를 담도록 하겠습니다. 위의 그림은 2차원 배열로 구성한 연결 리스트입니다. 여기서 행(가로 축, Row)은 하나의 노드로 표현됩니다. 노드에는 item과 next가 있습니다..
- 연결 리스트 연결 리스트(Linked List)는 배열과 같이 스택, 큐 등 자료 구조들의 기반이 될 수 있는 자료 구조입니다. 연결 리스트는 정보를 담고 있는 노드와 각 노드들의 논리적인 연결로 구성됩니다. 노드는 정보를 구성하는 데이터와 다음 노드와의 논리적인 연결을 지원하는 변수로 구성됩니다. 변수는 C 언어의 포인터와 같은 개념으로 정의 되고 변수에는 다음 노드의 주소값이 할당됩니다. head는 첫 node의 주소값을 갖고 있는 변수입니다. head는 연결 리스트의 각 노드를 방문하기 위한 첫 시작이라고 할 수 있습니다. head의 값을 잃어버린다면 그 리스트에 다시 접근하는 것은 불가능합니다. 그리고 이 연결 리스트는 메모리 어딘가에 표류하게 됩니다. 각 node는 자료 구조(연결 리스트)를..
화재가 발생한 빌딩(2차원 배열)에 갇힌 사람을 탈출 시키는 문제 입니다. 불이 옮기는 시점과 사람을 이동시키는 시점을 잘 분류해서 쉽게 해결하였습니다. BFS를 이용해서 사람이 이동 가능한 위치를 찾아서 이동 시키고 화재가 퍼질 수 있는지 확인하여 불이 번지도록 만들었습니다. 사람이 탈출 할 수 있는 최단경로를 찾아야하기 때문에 BFS를 사용 하였습니다. 아래는 문제 링크와 소스 코드 입니다. https://www.acmicpc.net/problem/5427 import java.util.Iterator; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class EscapeFireBuilding ..
안전 영역 문제는 장마철 비가 어느정도 왔을때 안전영역의 갯수가 최대가 되는지 구하는 문제 입니다. 강수량을 확인해서 침수 영역을 만들어주었습니다. 그 후에는 안전구역을 BFS 알고리즘을 사용해서 확인 했습니다. 더 이상 탐색할 곳이 없다면 안전 구역의 번호를 1 증가 시키고 다음 영역을 탐색하였습니다. 처음에는 안전구역이 가장 넓은 경우를 찾는 문제라고 생각했고 비가 가장 조금 왔을 경우에 안전구역이 넓어질 것이라고 생각했습니다. 그러나 안전 구역의 넓이가 아니라 안전 구역이 만들어진 갯수의 최댓값을 구하는 문제인 것을 확인하고 강수량이 될 수 있는 1부터 100까지 모든 경우에서 확인을 하였습니다. 프로그램의 실행 시간을 조금이라도 줄일려면 입력된 구역에서 가장 높은 위치의 값과 강수량을 비교해서 가..