본문 바로가기

전체 글205

데이터베이스 정규화 앞서 이상현상(Anomaly)에 대해 알아보았습니다. 2023.12.07 - [정보관리기술사준비/데이터베이스] - 데이터 베이스 이상현상(Anomaly) 데이터 베이스 이상현상(Anomaly) 데이터 베이스에서 데이터의 중복으로 인해 릴레이션에 대한 삽입, 갱신, 삭제시 발생하는 비합리적인 현상인 Anomaly 즉 이상현상에 대해 알아보겠습니다. Anomaly는 정규화가 제대로 구현된 DB에 davincicoding.co.kr 이상현상을 제거하는 무손실 분해 과정인 정규화(Nomalization)에 대해 알아보도록 하겠습니다. 예제로 컴퓨터 시스템 응용 기술사 111회 3교시 6번 문제로 진행하도록 하겠습니다. 다음은 컴퓨터에서 사용되는 제품에 대해 여러 개의 주문서가 접수된 내용을 보여주는 "주문목록".. 2023. 12. 10.

[백준 1504] 특정한 최단 경로 문제 출처 : https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 문제 설명 최단 경로를 구하는 다익스트라 알고리즘 문제 입니다. 다익스트라 알고리즘에 대해서 잘 모른다면 아래 링크를 통해 확인해 보시기 바랍니다. https://wikidocs.net/206944 01. 다익스트라 알고리즘 # 다익스트라 알고리즘 다익스트라 알고리즘(Dijkstra Algorithm)은 그래프에서 최단 경로를 구하는 알고.. 2023. 12. 9.

데이터 베이스 이상현상(Anomaly) 데이터 베이스에서 데이터의 중복으로 인해 릴레이션에 대한 삽입, 갱신, 삭제시 발생하는 비합리적인 현상인 Anomaly 즉 이상현상에 대해 알아보겠습니다. Anomaly는 정규화가 제대로 구현된 DB에서는 발생하지 않습니다. 가장 흔하게 발생하는 이유는 여러 종류의 릴레이션을 하나의 DB에 표현하려다 발생합니다. 이런 Anomaly 현상이 발생하면 정규화를 실행해야 합니다. 그럼 예시를 통해 알아보도록 하겠습니다. 사번 부서코드 부서명 100 A10 기획부 200 A20 인사부 300 A30 영업부 400 A10 기획부 다음과 같은 부서 DB가 있습니다. 각각의 사원에 대해서 사번과 해당 사원의 부서에 대한 정보가 DB에 저장되어 있습니다. 그럼 이 데이터베이스에 삽입, 갱신, 삭제시 발생하는 Anoma.. 2023. 12. 7.

데이터 베이스의 고립화 단계(Isolation Level) 데이터베이스 트랜잭션의 ACID 속성을 보장하기 위한 Isolation Level에 대해 알아보겠습니다. 데이터베이스를 혼자 사용한다면 아무 문제가 없겠지만 수많은 사람이 같이 사용하다보니 수많은 문제가 발생합니다. 어떤 트랜잭션에서 수정중인 중간 결과를 다른 트랜잭션이 접근하게 되면 Dirty Read, Non-Repeatable Read, Phantom Read등의 문제가 발생할 수 있습니다. 각각 어떤 상황에서 그런 문제가 발생하는지, 위에서 언급한 문제들은 무엇을 뜻하는지 알아보도록 하겠습니다. Read Uncommitted(Level 0) Read uncommitted 상태는 커밋을 하지 않은 데이터에 접근하는 것입니다. 예를 들어 위와 같이 DB에 좋아하는 음식을 저장해 놓았습니다. 홍길동은 .. 2023. 12. 6.

비잔틴 장군 문제 비잔틴 장군 문제란? 블록체인에 대해 공부하면 한 번쯤 들어봤을 비잔틴 장군 문제(# Byzantine Generals Problem)에 대해 알아보겠습니다. 비잔틴 장군 문제는 위와 같이 성을 공략하는 방법에 대한 딜레마 입니다. 적의 성에는 적군이 많이 있기 때문에 한 번에 모두 공격을 해야만 성을 함락할 수 있습니다. 지휘관이 내일 10시에 일제히 성을 공격하자고 각 장군들에게 전령을 보내 공격을 진행 합니다. 이 때 장군들 사이 혹은 소식을 전하는 전령들 중에 첩자가 존재해 10시가 아닌 8시에 공격하자고 전달합니다. 이렇게 되면 어떤 장군은 제대로 전달 받아 10시에 공격하고, 어떤 장군은 첩자에게 속아 8시에 공격하게 됩니다. 이렇게 전력이 분산되어 결국 성을 함락하지 못하게 됩니다. 첩자가 .. 2023. 12. 1.

[백준 10808] 알파벳 개수 문제 출처 : https://www.acmicpc.net/problem/10808 10808번: 알파벳 개수 단어에 포함되어 있는 a의 개수, b의 개수, …, z의 개수를 공백으로 구분해서 출력한다. www.acmicpc.net 이 문제는 어려운 문제가 아니지만 방법을 모르면 귀찮은 문제라 할 수 있습니다. a부터 z까지 해당 문자가 나타날 때 1씩 더해주면 됩니다. 하지만 이렇게 문제를 푼다면 a부터 z까지 26개의 변수를 만들고, 26개의 비교문을 만들어야 합니다. 이럴 때 사용하는 방법이 앞선 포스트에서 배웠던 ord를 이용하여 문자를 숫자로 바꿔주는 방법 입니다. 문자를 숫자로 바꿔서 무엇을 할 수 있을까요? 바로 리스트의 인덱스로 사용하는 것입니다. 문제 이해하기 문자 a를 숫자 0으로 바꿔줄.. 2023. 11. 23.

파이썬의 문자를 숫자로, 숫자를 문자로 바꾸기 파이썬을 사용하다보면 가끔 문자를 숫자로, 숫자를 문자로 바꿔주고 싶은 경우가 생깁니다. 이럴때 문자를 숫자로 바꿔주는 방법에 대해 알아보겠습니다. 문자를 숫자로 나타낸 표를 보통 아스키(ASCII) 코드라고 합니다. 아스키코드의 약자는 다음과 같습니다. ASCII (American Standard Code for Information Interchange, 미국 정보 교환 표준 부호) 아스키코드는 컴퓨터가 나오기 이전 모스 부호 전송기에서 사용하던 통신 방법입니다. a라는 문자를 숫자로 바꿔준 뒤 그 신호를 전달하고 다시 그 숫자를 문자 a로 바꿔주어 정보를 주고받던 시절에 사용하던 방식입니다. 이런 아스키 코드를 지금은 사용할 일이 없지만 알고리즘 문제를 풀다보면 문자를 숫자로 바꿔줘야 하는 테크닉이.. 2023. 11. 20.

[ISO 22301] 비즈니스 연속성 경영 시스템 비즈니스 연속성 경영 시스템의 국제 표준 ISO 22301 에 대해서 소개합니다. 도입배경 러시아 핵 잠수함 침몰사건, 911 테러, 자연재해등 많은 위험이 대두되면서 국제 표준화 기구(ISO)에서 사회안전 분야의 표준화 작업에 착수하여 발간한 국제 표준 입니다. 정의 기업의 비즈니스 연속성을 위해 BCP 수립에서 도입, 운영, 검토까지 지속적인 개선에 대한 요구사항을 규정한 BCMS의 국제 표준 입니다. 기업의 BCM 역량에 대한 평가 지표로 영국 표준인 BS 25999를 기반으로 만들어졌습니다. 목적 조직의 요구사항 및 이해관계자들의 요구사항에 맞는 BCM을 설계하는 것이 목적으로 조직의 업무 연속성에 대한 요구사항 및 의무에 부합한 능력을 평가합니다. BCMS 적용 PDCA 모델 주요 내용 취득 효.. 2023. 11. 16.

[백준 11438] LCA 2 문제 출처 : https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 앞서 풀어보았던 LCA 문제의 심화 버전 입니다. 입력과 출력의 형식이 똑같지만 주어지는 N과 노드의 쌍 M의 수가 늘어나 있습니다. 따라서 기존의 LCA 문제를 푸는 방식으로는 시간초과가 발생합니다. LCA의 풀이 방법을 생각해 보겠습니다. 두 정점의 깊이를 맞춰 준다. 깊이가 같다면 공통 조상이 나올 때까지 하나씩 위로 올라간다. 이 두 가지 방법으로 LCA를 찾아주었습.. 2023. 11. 15.

[백준 24955] 숫자 이어 붙이기 문제 출처 : https://www.acmicpc.net/problem/24955 24955번: 숫자 이어 붙이기 철수는 수를 이어 붙이는 놀이를 좋아한다. 1과 2를 이어 붙이면 12가 되고, 17과 13을 이어 붙이면 1713이 된다. 100과 1000을 이어 붙이면 1001000이 된다. 1과 2를 이어 붙이되, 순서를 반대로 해서 2와 www.acmicpc.net 문제 이해하기 방문한 순서대로 숫자들을 이어 붙여서 출력하는 문제 입니다. 사실 이 문제는 LCA 항목에 있어서 LCA를 연습하려고 풀어본 문제인데 단순한 DFS로 해결되는 문제였습니다. 다만 이 문제에서 신경 쓸 부분은 두가지 입니다. 숫자들 더해주는 것이 아니라 이어 붙이는 것입니다. 답을 숫자가 아닌 문자열로 관리해야 합니다. 숫자.. 2023. 11. 10.

[백준 11812] K진 트리 문제 출처 : https://www.acmicpc.net/problem/11812 11812번: K진 트리 첫째 줄에 N (1 ≤ N ≤ 1015)과 K (1 ≤ K ≤ 1 000), 그리고 거리를 구해야 하는 노드 쌍의 개수 Q (1 ≤ Q ≤ 100 000)가 주어진다. 다음 Q개 줄에는 거리를 구해야 하는 두 노드 x와 y가 주어진다. (1 ≤ x, y www.acmicpc.net 문제 이해하기 최소 공통 조상(LCA)를 찾는 문제 입니다. 다만 일반적인 방법으로 풀 수 없습니다. 왜냐하면 메모리 사용을 최소로 해야 풀리는 문제이기 때문입니다. 그냥 LCA를 푸는 방식으로 풀게되면 메모리 초과를 경험하게 됩니다. 결국 이 문제는 K진 트리의 특성을 이용하여 각 노드의 부모와 깊이를 찾아 해결해야 합.. 2023. 11. 6.

디지털 가든 만들기 슬기로운 옵시디언 생활 블로그는 공개적인 글을 쓸 때 사용하고 개인적인 글은 노션을 사용하다가 작년부터인가 옵시디언으로 건너왔습니다. 옵시디언을 사용하면서 좋았던 부분이 로컬로 동작한다는 부분이였습니다. 온라인으로 되어 있으면 언제 어디서나 접속이 가능하다는 장점이 있지만 온라인 한정이라는 단점이 있어 조금은 아쉬웠습니다.(회사에서 노션 접속이 안되서 그렇습니다) 로컬이긴 하지만 아이클라우드를 이용하여 노트북과 아이폰 모두 사용가능해 전혀 불편함 없이 사용해 왔습니다. 회사에서는 회사 업무 용도인 옵시디언을, 개인적인 용도는 핸드폰이나 집의 노트북으로 분리해서 사용해 왔는데 기술사 공부를 하면서 문제가 발생하였습니다. 옵시디언을 통합하라 집에서 기술사 공부했던 내용을 정리한 것을 회사에서 보려면 핸드폰을.. 2023. 10. 31.

지지도, 신뢰도, 향상도 데이터 분석 연관성 규칙을 찾을 때 지지도, 신뢰도, 향상도라는 것을 사용합니다. 이것에 대해 알아보도록 하겠습니다. 정보관리기술사 119회에 나온 문제중 일부로 지지도, 신뢰도, 향상도를 구해 보도록 하겠습니다.문제아래 데이터를 참조하여 '기저귀 -> 맥주'의 지지도, 신뢰도, 향상도를 도출하시오거래번호구매한 상품1003기저귀, 맥주, 빵1056기저귀, 맥주1071기저귀, 빵, 음료수2005빵, 음료수, 커피지지도(Support)A상품과 B상품을 같이 구매한 횟수 / 전체 구매 횟수$$ 지지도 = P(A \cap B) $$지지도는 전체 구매에서 교집합의 비율을 보는 것입니다. 전체 거래 4건과 기저귀와 맥주를 동시에 구매한 1003, 1056번 2건에 대한 비율을 구해줍니다. 2 / 4로 50%가 됩니.. 2023. 10. 27.

ESG 경영 ESG 경영이란? ESG는 환경(Environment), 사회(Social), 지배구조(Governance)의 약자로 기업에서 비재무적 요소들의 지속가능성을 달성하기 위한 3가지 핵심 요소 입니다.기존의 기업들은 얼마를 벌었는가?를 중심으로 한 재무적 지표가 기준이였지만 최근 기후변화등으로 인해 비재무적 지표가 기업의 실질적인 가치평가에 있어 더 중요하다는 인식이 늘어나고 있습니다. ESG 등장배경 ESG 용어는 2004년 UNGC(UN 글로벌 콤팩트)가 발표한 'Who Cares Win'이라는 보고서에서 기업이 발전하기 위해서는 환경, 사회, 지배구조 측면에서 이슈를 관리해야 한다는 개념으로 처음 등장하였습니다. 이후 2006년 국제 투자기관 연합인 UN PRI가 금융 투자 원칙으로 ESG를 강조하면서.. 2023. 10. 26.

Data Mining 이란? Data Mining 이란? 광산에서 금을 채굴하듯이 수많은 데이터들 사이에서 숨겨져 있는 데이터간의 관계나 패턴을 찾아 이를 모형화 하여 업무에 적용할 수 있는 의미 있는 정보로 변환하는 것을 데이터 마이닝이라고 합니다. 기존에 사용하던 통계는 기존 모집단에서 표본을 샘플링하여 가설에 대한 검증/추론이 목적이였다면, 데이터 마이닝은 숨겨진 패턴이나 새로운 상관관계, 추세를 발견하는것이 다른점 입니다. 데이터 마이닝 수행 절차 데이터 마이닝의 방법론중 하나인 KDD(Knowledge Discovery in Database) 수행단계는 다음과 같습니다. Selection 데이터 셋을 선택하는 단계로 비즈니스를 이해하고, 프로젝트의 목표를 설정합니다. 이를통해 데이터를 선택하고 데이터 셋을 생성합니다. Pr.. 2023. 10. 24.

ITSM 이란? Information Technology Service Management의 약자인 ITSM에 대해 알아보겠습니다. 정의 고객과 합의된 SLA 수준에 맞게 품질을 유지하도록 인력, 조직, 기술, 프로세스의 종합적인 관리를 위한 선진 IT 서비스 관리 기법 입니다. 등장배경 예전에는 회사 내부에 IT 내부 운영 조직이 있어 IT를 통합 관리 하였습니다. 이러다보니 급변하는 IT 환경을 통제하기 힘든 수준에 이르렀습니다. 수준에 맞게 서비스를 하려면 IT 조직은 비대해질 수 밖에 없었고 비용이 늘어날 수 밖에 없었습니다. 기업들 입장에서는 TCO를 줄이고 ROI를 극대화 하기를 원할수 밖에 없었습니다. 이러다보니 IT 운영 관리를 아웃소싱하여 외부에서 수행하도록 하는 것이 더 전문적이고 비용이 절감될 수 밖.. 2023. 10. 22.

트리 정렬 129회 정보관리기술사 기출 문제로 트리 정렬을 설명하는 문제가 나왔습니다. 알고리즘 문제를 보니 반가운 느낌이 들었습니다. 트리 정렬은 이진 탐색 트리(Binary Search Tree)로 구성한 후 중위 순회 방법으로 순회하면서 오름차순으로 정렬하는 방법 입니다. 이렇게만 들으면 무슨 말인지 잘 이해가 안될 수 있습니다. 하나하나 정리해 보도록 하겠습니다. 트리(Tree) 구조란? 알고리즘에 익숙하다면 트리가 무엇인지 바로 알 수 있지만 알고리즘에 익숙하지 않다면 갑자기 나무가 나와 당황할 수 있습니다. 이런 식으로 데이터를 구성하는 방법을 트리 구조라고 합니다. 그림은 최소 공통 조상에 설명했던 그래프를 그냥 가져왔습니다. 색깔이 다른것에 대해 의문을 가질 필요가 없습니다. 숫자가 써 있는 부분이 .. 2023. 10. 20.

SOLID 원칙 정보관리 기술사 준비를 하면서 내가 잘 아는 분야부터 시작하기로 마음먹고 많이 들어봤지만 잘 기억나지 않았던 부분부터 정리해보려 합니다. 뭐가 있을까 고민해보니 객체지향 프로그래밍의 5가지 설계 원칙인 SOLID가 떠올랐습니다. 솔직히 SOLID는 기억났지만 SOLID가 뭐였는지 정확하게 기억은 나지 않았습니다. 이렇게 오늘도 또 아는것이 하나 늘어나네요 SOLID란? 로버트 마틴이 The Principles of OOD 에 소개한 객체지향 프로그래밍을 하면서 지켜야하는 5대 설계 원칙 SRP(단일 책임 원칙), OCP(개방-폐쇄 윈칙), LSP(리스코프 치환 원칙), ISP(인터페이스 분리 원칙), DIP(의존 역전 원칙)의 앞글자를 따서 만들었습니다. Single Responsiblity Princ.. 2023. 10. 19.

for else / while else 사용 방법 알고리즘 문제를 풀다보면 이런 형태의 문제를 보게 됩니다. 정답이 있으면 정답을 출력하고, 답이 없다면 "No"를 출력하시오. 즉 답의 출력을 요구하면서 답이 없는 경우에 특정한 값을 출력하는 경우 입니다. 문제 예 입력값 리스트에 1, 9, 25, 49, 81의 숫자가 있습니다. 7의 배수가 있으면 해당 값을 출력하고, 없으면 No를 출력하세요. 아주 간단한 문제 예 입니다. 이 문제를 풀기 위해서 이렇게 답을 작성할 수 있습니다. a = [1, 9, 25, 49, 81] check = True for i in a: if i % 7 == 0: print(i) check = False break if check: print("No") 리스트 a에 있는 값들을 확인하여 출력을 합니다. 문제는 답이 없을 경.. 2023. 10. 16.

[백준 4195] 친구 네트워크 문제 출처 : https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 간단한 유니온 파인드 문제 입니다. 기존의 유니온 파인드와 다른 두 가지 때문에 쉽게 문제를 풀 수 없습니다. 그럼 문제점을 파악해보고 문제를 풀어보도록 하겠습니다. 문제점 이 문제의 가장 큰 문제는 노드가 숫자가 아닌 친구 이름이라는 것입니다. 해결할 수 있는 여러가지 방법이 있겠지만 저는 딕셔너리를 이용하여 해결하였습니다. 다음으로 친구가 몇명이 있는지 알아야 합니다... 2023. 10. 13.

[백준 25405] 2022년 정보 올림피아드 2차 "레벨 업" 문제 출처 : https://www.acmicpc.net/problem/25405 25405번: 레벨 업 여러분은 $N$명의 게임 캐릭터를 육성하려고 한다. $i$ ($1 ≤ i ≤ N$) 번째 캐릭터의 현재 레벨은 $L_i$이다. 캐릭터의 레벨을 올리기 위해 아래와 같은 트레이닝을 총 $M$번 진행할 것이다. 레벨이 www.acmicpc.net 이 문제는 2022년 정보올림피아드 2차 중등부 4번, 고등부 3번 문제로 출제되었습니다. 레벨의 균형을 맞춰가며 올리는 문제 입니다. 매번 트레이닝 할 때마다 레벨이 낮은 K개의 캐릭터의 레벨을 1씩 M번 올리면 해결 되는 간단한 문제 입니다. 문제는 캐릭터가 총 10만이고, K값의 최대값도 10만이며 올려야하는 레벨의 최대값은 10억이라는 것입니다. 따라서 .. 2023. 10. 11.

[백준 11437] LCA 문제 출처 : https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 가장 기본적인 형태의 LCA 문제 입니다. LCA 알고리즘의 설명은 이전에 게시한 알고리즘 설명으로 대신하겠습니다. 2023.10.06 - [알고리즘 설명] - 최소공통조상(LCA) 최소공통조상(LCA) LCA란? 최소 공통 조상(Lowest Common Ancestor) 줄여서 LCA로 불리는 이 알고리즘은 트리에서 두 정점이 가지고 있는 가장 가까운 공통 조상을 찾는 알고리.. 2023. 10. 10.

최소공통조상(LCA) LCA란? 최소 공통 조상(Lowest Common Ancestor) 줄여서 LCA로 불리는 이 알고리즘은 트리에서 두 정점이 가지고 있는 가장 가까운 공통 조상을 찾는 알고리즘 입니다. 위와 같은 그래프가 있을 때 6번 정점과 9번 정점의 최소 공통 조상은 3번 입니다. 우리는 눈으로 바로 3번이 최소 공통 조상이라는 것을 찾을 수 있지만 알고리즘으로 이를 찾으려면 쉽지 않습니다. 어떻게 찾을 수 있을지 한번 생각해 보고 다음을 읽어보시기 바랍니다. 알고리즘 이해하기 최소 공통 조상을 찾는 방법은 하나씩 자신의 부모를 타고 올라가다가 공통으로 만나는 첫 번째 정점을 찾는 것입니다. 8번과 9번의 최소 공통 조상을 찾는다고 해보겠습니다. 두 정점의 부모를 찾아 올라갑니다. 먼저 8의 부모인 5와 9의 부.. 2023. 10. 9.

[백준 9465] 스티커 문제 출처 : https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 간단한 DP 문제 입니다. DP에 대해 잘 모른다면 어렵게 느껴질 수 있습니다. 스티커의 품질이 좋지 않기 때문에 어떤 스티커를 떼면 그 스티커의 상, 하, 좌, 우에 있는 스티커는 사용할 수 없습니다. 따라서 왼쪽부터 첫 번째 줄의 스티커를 떼었을 때, 두 번째 줄의 스티커를 떼었을 때, 아무것도 떼지 않았을 때, 이렇게 세가지의 경우를 생각해서 문제를 해결해야 합니다... 2023. 10. 5.

[백준 1976] 여행 가자 문제 출처 : https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 여행을 갈 수 있는지, 없는지 확인하는 문제 입니다. 문제를 보면 쉽게 도시들을 DFS를 통해 방문이 가능한지 불가능한지 따지면 해결될 것으로 보입니다. 하지만 이렇게 문제를 풀게 되면 시간초과가 발생할 수 있습니다. 왜냐하면 의도적으로 끝에서 끝으로 이동하는 경로만 입력이 들어온다면 방문하는데 시간이 오래걸릴 수 있습니다. 따라서 이 문제는 DFS가 아니라 유니온 파인드, 즉 분리.. 2023. 10. 4.

[백준 15686] 치킨 배달 문제 출처 : https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 치킨을 배달할 수 있는 치킨 거리가 가장 짧아지는 경우를 구하는 문제 입니다. 여기서 거리를 구하는 방식은 맨하탄 거리(Manhattan Distance)를 구하는 공식 입니다. 좌표간의 거리를 구하는 방식 중 하나로 간단한 계산으로 거리를 구할 수 있습니다. 알고리즘 지도의 크기 N의 최대는 50이고 치킨 집의 개수의 최대는 13입니다. 이정도의 크기라면 브루.. 2023. 9. 27.

[알고리즘]Merge Sort 병합 정렬이라고 불리는 머지 소트(Merge Sort)에 대해 알아보겠습니다. 다양한 정렬 알고리즘이 있지만 다빈치코딩 알고리즘에는 이분 정렬에 대해서만 소개했었습니다. 이유는 어짜피 시간복잡도가 비슷하고 이분 탐색만 알아도 정렬에 관한 문제를 푸는데 큰 어려움이 없기 때문입니다. 하지만 Inversion Counting 에 대해 소개하고 세그먼트 트리로 푸는 방법만 알려주고, 정작 Inversion Counting 으로 풀 수 있는 문제 버블 소트를 풀 때에는 Merge sort 로 해결하였던 것이 생각나 merge sort에 대해서도 설명해야 겠다는 생각을 하였습니다. Merge Sort 란? 위키피디아에 있는 merge sort의 설명 이미지 입니다. 분할 정복과 비슷한 형태로 진행되는 것을 알 수.. 2023. 9. 26.

[Apple Silicon] Stable Diffusion Web UI 설치하기 Stable Diffusion 이란? 스테이블 디퓨전은 2022년 출시된 딥 러닝 모델 입니다. 주로 텍스트 설명에 따라 이미지를 생성하는데 주로 사용 됩니다. 스타트업 회사인 Stability AI 에서 개발한 인공지능으로 엄청난 개발 비용이 들어 갔겠지만 이것을 그냥 무료로 배포하였습니다. 그래서 이것을 우리가 컴퓨터에 설치하고 실행해 볼 수 있는 것입니다. Stable Diffusion을 무료로 공개함에 따라 다양한 사람들이 이것을 응용하여 여러가지 편리한 기능을 추가하였습니다. 그중 하나가 AUTOMATIC111 이라는 사람이 github에 공개한 Stable Diffusion Web UI 입니다. Stable Diffusion Web UI란? 기존의 스테이블 디퓨전을 사용하려면 복잡한 기능에 개.. 2023. 9. 24.

LIS 란? LIS(Longest Inceasing Sequence)란? LIS는 Longest Increasing Subsequence의 약자로 최장 증가 수열 또는 최장 증가 부분수열이라고 합니다. LIS를 이해하기 위해서는 먼저 Increasing Subsequence 한글로 증가 부분수열을 알아야 합니다. 증가 부분수열을 말 그대로 증가하고 있는 부분 수열을 나타냅니다. 가령 [5, 1, 9, 2, 7, 3, 8, 4, 6] 이라는 리스트가 존재할때 여기서 증가하는 부분 수열을 찾아 보겠습니다. [5, 9], [5, 7, 8], [1, 2, 7, 8] 등등 다양한 증가하는 부분수열이 존재합니다. 이중 가장 길이가 큰 최장 증가 부분 수열은 [1, 2, 3, 4, 6]이 됩니다. 이 최장 증가 부분 수열을 찾는.. 2023. 9. 21.

[백준 12015] 가장 긴 증가하는 부분 수열 2 문제 출처 : https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net LIS(Longest Inceasing Sequence)란? LIS는 Longest Increasing Subsequence의 약자로 최장 증가 수열 또는 최장 증가 부분수열이라고 합니다. LIS를 이해하기 위해서는 먼저 Increasing Subsequence 한글로 증가 부분수열을 알아야 합니다. 증가 부분수열을 말 그대로 증가하고 있는 부분 수열을 나타냅니다. 가령 [5, 1,.. 2023. 9. 20.

이전 1 ··· 3 4 5 6 7 다음

티스토리툴바