문제 참고 (https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 그리디 문제에 맞게 접근 방법을 우선 찾게 되었고, 시간 초과의 문제를 해결하기 위해 많이 고민하였다. 처음 내가 푼 코드이다. import sys N = int(input()) weight_restric = (map(int, sys.stdin.readline().split())) M = int(input()) weight = map(int, sys.stdin.read..

예전 글에서 완전검색(Exaustive Search) 즉, 브루트 포스에 대해서 알아보았다. 경우의 수를 이용하여 문제를 푸는 것이 아닌 저장되어 있는 자료 중에서 원하는 항목을 찾는 작업이다. 검색(Search) 탐색 키(search key) : 자료를 구별하여 인식할 수 있는 키 종류 순차 검색(sequential search) 이진 검색(binary search) 해쉬(hash) 순차 검색 (Sequential Search) 일렬로 되어 있는 자료를 순서대로 검색하는 방법 가장 간단하고 직관적인 검색 방법 배열이나 연결 리스트 등 순차구조로 구현된 자료구조에서 원하는 항목을 찾을 때 유용함 알고리즘이 단순하여 구현이 쉽지만, 검색 대상의 수가 많은 경우에는 수행시간이 급격히 증가하여 비효율 1. 정..

완전검색 기법으로 모든 부분집합 합 문제를 풀기 위해서는, 우선 집합의 모든 부분집합을 생성한 후에 각 부분집합의 합을 계산해야 한다. 어떻게 계산할 수 있을까? 부분 집합의 생성 부분 집합의 수를 우선 구해보자 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 수는 2^n개이다. 이는 각 원소를 부분집합에 포함시키거나 포함시키지 않는 2가지 경우를 모든 원소에 적용한 경우의 수와 같다. 예) {1, 2, 3, 4} -> 2 * 2 * 2 * 2 = 16가지 1. 각 원소가 부분집합에 포함되었는지를 loop를 이용하여 확인하고 부분집합을 생성해보자 bit = [0, 0, 0, 0] for i in range(2): bit[0] = i# 0번째 원소 for j in range(2): bit[1] = j..

https://www.acmicpc.net/problem/1057 1057번: 토너먼트 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 www.acmicpc.net 우리가 흔히 아는 토너먼트에서 서로가 몇 번만에 만나는지를 출력하는 문제이다. 접근 방법 다음 라운드로 진출하는 참가자는 다시 왼쪽부터 1번, 2번.. 순으로 받는다. 즉, (1 2) (3 4) (5 6) (7 8) (9 10) 이렇게 5개의 조가 있을 때 다음 라운드에 받는 번호는 2/2, 4/2, 6/2, 8/4와 같이 변한다. 또한 연속된 수에서 홀수가 작은 수여야만 만날 수 있다. 서로 번호의 차..

저번 글에서는 검색과 순열에 대해서 알아보았다. 이번 시간엔 'Greedy'라고 불리는 최적해를 구하는 방법을 알아보자. 탐욕 최적해를 구하는데 사용되는 근시안적인 방법 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 각 선택의 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여, 그것이 최적이라는 보장은 없다. 일반적으로, 머릿속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 된다. 동작 과정 해 선택 = 선택 절차(Selection Procedure) 현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분해집합(Solution Set)에..

앞에서는 배열을 선언하고 그 배열을 정렬하는 방법에 대해서 배웠다. 이번 글에서는 경우의 수를 이용하여 문제 해결을 하는 검색이라는 것에 대해서 배워보자. 완전 검색(Exaustive Search) 완전 검색 방법은 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법 Brute-force 혹은 generate-and-test 기법이라고도 불림 모든 경우의 수를 테스트한 후, 최종 해법을 도출 일반적으로 경우의 수가 상대적으로 작을 때 유용 특징 모든 경우의 수를 생성하고 테스트하기 때문에 수행 속도는 느리지만, 해답을 찾아내지 못할 확률이 작다. 평가 등에서 주어진 문제를 풀 때, 우선 완전 검색으로 접근하여 해답을 도출한 후, 성능 개선을 위해 다른 알고리즘을 사용하고 해답을 확..

알고리즘이라는 말은 많이 들어봤을 것이다. 나도 단순한 흐름이라고만 알고 있었지 이게 왜 필요한 것인지 알아보자! 알고리즘 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법 주로 컴퓨터 용어로 쓰이며, 컴퓨터가 어떤 일을 수행하기 위한 단계적 방법 즉, 어떠한 문제를 해결하기 위한 절차 컴퓨터 분야에서 알고리즘을 표현하는 방법을 크게 두 가지이다. 의사 코드(슈도 코드, Pseudocode) 순서도 APS(Algorithm Problem Solving) 과정의 목표 중의 하나는 보다 좋은 알고리즘을 이해하고 활용하는 것!! 그렇다면 좋은 알고리즘이란 무엇일까? 정확성 : 얼마나 정확하게 동작하는가 작업량 : 얼마나 적은 연산으로 원하는 결과를 얻어내는가 메모리 사용량 : 얼마나 적은 메모리를 사용하는..

저번 글에서 배웠던 Display와 Position 모두 CSS Layout technique의 종류 중 하나였다! 오늘은 조금은 성격이 다른 float와 flex box를 이용하여 CSS Layout을 다뤄보자. CSS Layout technique 종류 Display Position float Flex box Grid 기타 이전 글들 또는 신문 기사와 같이 이미지를 감싸는 글자들을 많이 보았을 것이다. 또는 이미지가 왼쪽, 오른쪽으로 배치가 되어 있는 것을 보았을 것이다. 이때 사용하는 것이 바로 Float이다. 박스를 왼쪽 혹은 오른쪽으로 이동시켜 텍스트를 포함 인라인요소들이 주변을 wrapping 하도록 함 요소가 Normal flow를 벗어나도록 함 속성 none: 기본 값 left: 요소를 왼..

지난 시간에 네모 박스의 크기 조절 방법을 배웠다면 이번에는 그 박스들의 위치를 지정해줄 것이다. 우선 HTML 시간에 잠깐 지나갔던 인라인/블록 요소라는 것이 기억나는가? 괜찮다. 이번에 다시 배우면 된다. 이전 글과 마찬가지로 CSS원칙 2번째를 알아보고 가자! 모든 요소는 네모이고, 좌측 상단에 배치 Display에 따라 크기와 배치가 달라진다. 여기 나오는 Display의 대표 종류가 block과 inline이다! display: blcok 줄 바꿈이 일어나는 요소 화면 크기 전체의 가로 폭을 차지한다. 블록 레벨 요소 안에 인라인 레벨 요소가 들어갈 수 있음. 대표적인 요소 - div/ ul,ol,li / p / hr / form 등 display: inline 줄 바꿈이 일어나지 않는 행의 일..