목록2017/11 (19)
Inor
n개의 피연산자와 n-1개의 연산자가 주어지면 연산자와 피연산자를 적절히 배치합니다. 적절히 배치해서 수식을 만드는데 수식을 계산해서 나오는 결과들의 최소값과 최대값을 구하는 문제입니다. 저는 재귀를 이용해서 문제를 해결했습니다. 연산자를 기준으로 최대 10번의 메서드 호출로 문제를 해결할 수 있기 때문에 재귀로해도 stackoverflow 에러가 발생하지 않을 것이라고 생각했습니다. 그러나 중복되는 연산을 제대로 처리해주지 못해서 시간이 오래 걸리는 문제가 있었습니다. 아래는 문제의 링크와 코드입니다. - 문제 : https://www.acmicpc.net/problem/14888 - 소스 코드 import java.util.Scanner; public class OperatorInsertion { i..
N명의 사람이 있을때, 사람들의 줄 서는 방법을 계산하는 알고리즘 문제입니다. 예를 들어서 3명의 사람이 있을때 줄 서는 방법은 [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]이 존재하고 줄서는 방법의 총 개수는 3! = 6가지 방법입니다. 문제에서는 2가지 입력(사람의 수, x번째 줄 서는 방법)이 주어집니다. 만약 사람의 수가 3명이고 4번째 줄 서는 방법을 출력할 경우에 [2,3,1]이 출력됩니다. 4명의 사람이 줄서는 직접 방법을 아래와 같이 나열하며 문제에 접근했습니다. 그리고 가장 앞에 있는 숫자를 기준으로 4가지 종류의 배열이 생긴다는 것을 알았습니다. 그래서 가장 앞에 있는 숫자를 차례로 알아내는 방법으로 문제를 해결했습니다. 앞의 자리를 알아..
- 스케줄링 알고리즘 다중 프로그래밍 환경에서 여러 개의 프로세스가 있을때, 어떤 프로세스에게 컴퓨터의 자원을 언제 할당할지 정하는 알고리즘을 스케줄링 알고리즘이라고 합니다. CPU의 응답시간, 처리량, 효율성 등을 증대 시키기 위해서 자원을 효율적으로 할당해야 합니다. 스케줄링 알고리즘은 프로세스가 CPU를 점유하고 있을 때, 다른 프로세스가 CPU를 강탈할 수 있는지 여부에 따라서 비선점, 선점 알고리즘으로 나뉘어집니다. - 비선점 알고리즘 비선점 알고리즘의 특징은 한번 CPU를 사용하면 프로세스가 종료될 때까지 CPU의 사용 권한을 반환하지 않습니다. 일괄 처리 방식에 용이합니다. 하나의 프로세스가 종료될 경우에만 문맥 교환(Context Switch)이 일어납니다. 그래서 문맥 교환(Context..
한 줄로 이어진 톱니바퀴를 회전 시키는 문제입니다. 하나의 톱니바퀴를 회전 시키도록하는 명령어가 들어왔을때, 양 옆의 톱니바퀴에게 영향을 줄 수 있는지를 확인해서 같이 회전 시키도록하는 것이 문제의 핵심입니다. 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가 있습니다..