본문 바로가기

전체 글191

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.

[백준 1725] 히스토그램(세그먼트 트리) 문제 출처 : https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자 www.acmicpc.net 히스토그램은 다양한 풀이 방법으로 유명한 문제 입니다. 스택, 분할정복, 세그먼트 트리로 풀 수 있습니다. 여기서는 세그먼트 트리의 다양한 응용에 대해 배우기 위해 세그먼트 트리로 푸는 방법을 알아보겠습니다. 문제 이해하기 문제 풀이를 위한 개념은 이렇습니다. 아래와 같은 히스토그램이 있습니다. 처음부터 끝까지를 모두 포함하는 직사각형은 가장 낮은 높.. 2023. 9. 18.

Homebrew 설치하고 사용하기 Homebrew 란? Homebrew(홈브루)란 맥스 호웰(Max Howell)이라는 개발자가 만든 MacOS 용 패키지 관리 프로그램 입니다. 원래의 뜻은 집에서 만든 물건, 수제품을 뜻하는 단어 입니다. 특히 직접 담근 술을 뜻하는데 그중에서도 맥주를 지칭할 때가 많습니다. 그래서 홈브루의 로고도 사과(apple)로 만든 맥주의 형태입니다. 맥북을 사용하는 개발자라면 필수적으로 사용하는 프로그램중 하나로 프로그램을 설치하기 위해 해당 프로그램의 웹사이트에 방문하고, 다운로드 버튼을 찾아서 다운로드하고, 다운로드 된 프로그램을 설치하는 복잡한 단계를 터미널에 단 몇줄의 명령으로 해결할 수 있게 해줍니다. Homebrew 설치하기 homebrew를 설치하기 위해 homebrew 홈페이지에 접속합니다. 홈.. 2023. 9. 17.

[백준 28325] 2023 정올 "호숫가의 개미굴" 문제 출처 : https://www.acmicpc.net/problem/28325 28325번: 호숫가의 개미굴 KOI 호숫가에 여러 개미가 모여 사는 개미굴이 있다. 개미굴은 둥근 호수의 둘레를 따라 $1$부터 $N$까지의 번호가 붙은 $N$개의 방이 차례대로 원형으로 배치되어 있으며, 모든 $i$ ($1 \le i \le N-1$)에 www.acmicpc.net 이 문제는 2023년 정보올림피아드 2차 대회 초등부 3번, 중등부 2번 문제입니다. 이 문제를 풀기 위해서 생각해야 하는 부분을 알아보겠습니다. 쪽방 사용 개미굴에 쪽방이 있다면 쪽방을 이용하는 것이 최선 입니다. 그림과 같이 여러 개미굴이 있는 곳의 일부를 보도록 하겠습니다. 2번 개미굴에 쪽방이 하나 연결되어 있습니다. 쪽방인 4번을 선.. 2023. 9. 15.

파이썬 lambda 함수 활용 팁 lamda 함수란? 파이썬의 lambda(람다)함수는 활용성이 많아 많이 사용합니다. 하지만 이제 막 배운 입장에서는 도대체 이것을 어떻게 활용할 지 몰라서 사용이 꺼려지는 것이 사실입니다. 람다 함수에 대해서 잘 모른다면 아래 링크를 통해 확인 부탁 드립니다. https://wikidocs.net/197106 01. lambda 함수 # key 만들기 우리는 max 함수에 어떤 값을 비교해서 뽑아야 하는지 알려줘야 합니다. max 함수에 key라는 매개변수를 사용하면 max 함수에게 어떤 기준의 최댓값을 선… wikidocs.net lambda 함수의 활용 lamda 함수를 가장 많이 활용하는 몇가지 방법을 뽑아 보았습니다. 개인적인 생각이니 다른 유용한 사용법이 있으면 댓글로 소개 부탁 드립니다. 1.. 2023. 9. 14.

[백준 1517] 버블 소트(merge sort로 풀기) 문제 출처 : https://www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다. www.acmicpc.net 이 문제의 이름은 버블 소트이지만 버블 소트로 문제를 풀려고 한다면 시간초과로 문제를 해결할 수 없습니다. 이 문제는 앞에서 배운 Inversion Counting 으로 해결할 수 있습니다. 앞에서 세그먼트 트리로 푸는 방법을 배웠다면 이번에는 merge sort를 사용하여 문제를 풀어보도록 하겠습니다. 세그먼트 트리의 문제점 세그먼트 트리로 풀 수 있지만 머.. 2023. 9. 13.

Inversion Counting 알고리즘 Inversion Counting 이란? Inversion Counting 이란 역순으로 되어 있는 순서쌍의 개수를 세는 유명한 알고리즘 입니다. 쉽게 예를 들면 아래와 같은 숫자가 있습니다. 3 2 5 4 1 이렇게 5개의 숫자가 있습니다. 하나씩 비교해보면 (3, 2)는 3이 더 크기 때문에 역순으로 되어 있습니다. (3, 5)는 역순이 아닙니다. (3, 4) 역시 역순이 아닙니다. (3, 1)은 역순으로 되어 있습니다. 이런식으로 모든 순서쌍을 비교해보면 아래와 같은 순서쌍을 찾을 수 있습니다. (3, 2), (3, 1), (2, 1), (5, 4), (5, 1), (4, 1) 이렇게 6개의 순서쌍을 찾을 수 있습니다. 이것은 버블 정렬을 진행할 때 몇 번이나 교환을 진행하는지의 숫자와 같습니다. .. 2023. 9. 11.

Gradio 기초(Colab에서 사용하기) 파이썬을 배우고, 머신러닝을 배우고나면 내가 만든 것을 다른 사람들에게 소개하거나 공유하고 싶은 생각이 듭니다. 문제는 이것을 쉽게 보여줄 수 없다는 점입니다. 그럴 경우 Gradio(그라디오)를 사용하여 친구들이나 지인들에게 쉽게 공유가 가능합니다. Gradio란? gradio는 파이썬으로 만든 머신러닝이나 데이터 사이언스로 만든 프로그램을 웹 어플리케이션으로 만들어주는 역할을 합니다. 기본적으로 웹 어플리케이션을 만들기 위해서는 웹에 대한 지식도 있어야하고, 자바스크립트, HTML, CSS로 프론트 부분을 만들고, 장고(Django), 플라스크(Flask)등으로 서버를 만들어 배포를 해야 합니다. Gradio는 이런 복잡한 과정을 생략하고 바로 배포가 가능하다는 장점이 있습니다. 그럼 Colab에 간.. 2023. 9. 11.

파이썬 입력 빠르게 받기 백준 문제를 풀다보면 입력이 많아서 시간초과가 발생하는 경우가 종종 있습니다. 이때 readline을 사용해서 input의 속도를 빠르게 하는 방법은 많이 알려져 있습니다. import sys a = sys.stdin.readline() 이런식으로 기존의 input()을 모두 sys.stdin.readline()으로 바꿔주면 됩니다. 이 방법은 모든 input을 바꿔줘야 하는 귀찮음이 존재합니다. 이럴때 딱 한 번만 readline을 사용하여 모든 input문을 바꿔줄 수 있습니다. 함수를 변수처럼 사용하기 바로 함수를 변수처럼 사용하면 됩니다. 간단한 예를 들어 보겠습니다. def say_hello(): print("Hello World!") a = say_hello a() Hello World!를 출.. 2023. 9. 8.

백준 파이썬 RecursionError 재귀함수 문제를 풀다보면 가끔 RecursionError라는 것이 발생 합니다. 재귀함수가 계속 실행되면 파이썬 입장에서는 무한루프에 빠진것이 아닌가하는 생각을 하게 됩니다. 그래서 일정 수준의 재귀함수가 호출된다면 에러가 발생하게 됩니다. 재귀 최대 깊이 확인하기 파이썬이 정한 최대 재귀 함수의 깊이는 아래 코드로 확인할 수 있습니다. import sys print(sys.getrecursionlimit()) DFS, 다이나믹 프로그래밍등을 재귀로 구현했다면 파이썬이 정한 최대 깊이로는 에러가 발생할수 밖에 없습니다. 따라서 이 문제는 재귀함수가 많이 호출될 거라는 것을 알려주어야 RecursionError가 발생하지 않습니다. 재귀 최대 깊이 수정하기 재귀의 최대 깊이를 수정하는 방법은 아래와 같습니.. 2023. 9. 7.

[백준 2579] 06 정올 초등부 "계단 오르기" 문제 출처 : https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 이 문제는 2006년 정보올림피아드 시. 도 지역 본선 초등부 4번 문제 입니다. 지금으로 따지면 1차 대회에서 초등부 가장 어려운 문제 였습니다. 지금이라면 2~3번 수준의 문제이지 않나 생각합니다. 시간이 흐르면 흐를수록 문제가 어려워지고 있는것 같습니다. 계단을 오르는 규칙을 지키면서 얻을 수 있는 점수의 최댓값을 구하는 문제 입니다. 이런 유형의 문제는 다이나믹 프로그래밍(DP)로 해결할.. 2023. 9. 6.

[백준 14428] 수열과 쿼리 16 문제 출처 : https://www.acmicpc.net/problem/14428 14428번: 수열과 쿼리 16 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값의 인 www.acmicpc.net 세그먼트 트리를 조금 응용한 문제 입니다. 기존에는 리스트의 값을 출력 하였다면 이 문제에서는 해당 인덱스를 출력하는 문제 입니다. 이처럼 세그먼트 트리를 어떤 값을 찾는 것이 아니라 보조적인 수단으로 사용하는 문제가 많이 출제되니 이런 케이스의 문제를 많이 풀어봐야 합니다. 이 문제를 푸는 방법은 .. 2023. 9. 5.

[백준 10972] 다음 순열 문제 출처 : https://www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net permutations 함수를 사용하면 쉽게 해결 가능한 문제로 보입니다. permutations에 대해 잘 모른다면 다빈치코딩 알고리즘 브루트포스를 확인 바랍니다. 하지만 막상 해결이 쉽지 않습니다. 무작정 해보기 for문을 통해 순열들을 호출해서 입력된 배열과 비교하여 같은 것이 나올 때까지 찾습니다. 같은 것이 나오면 마지막 순열이면 -1을 출력하고, 아니면 다음 순열을 출력하면 됩니다. 하지만 막상 이렇게 풀면 시간초과가 됩니다. 시간.. 2023. 9. 4.

[백준 2517] 2012 정올 고등부 2차 "달리기" 문제 출처 : https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 www.acmicpc.net 이 문제는 2012년 정보 올림피아드 고등부 문제 입니다. 앞에서부터 자신보다 실력이 높은 사람의 수를 세어 자신의 최고 등수를 찾는 문제 입니다. 단순한 문제이지만 입력의 숫자가 많아 문제를 풀기는 단순하지 않습니다. 등수 찾기 맨 첫 번째 선수는 무조건 1등을 할 수 있습니다. 그리고 다음 선수는 첫 번째 선수보다 실력이 높다면 1등, 실력이 낮다면 2등 입니다. 즉 어떤 .. 2023. 8. 31.

[백준 1865] 웜홀 문제 출처 : https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 웜홀은 시간이 거꾸로 가는 곳입니다. 따라서 최단 경로를 구할 때 음의 가중치를 가진 간선이라 생각하면 됩니다. 이 문제에서는 음의 사이클이 존재하는지 존재하지 않는지 확인하는 문제입니다. 벨만 포드 알고리즘을 사용하여 음의 사이클이 있다면 YES를, 음의 사이클이 없다면 NO를 출력하는 문제입니다. 다빈치코딩 알고리즘에 벨만포드 알고리즘을 설명해 놓았습니다. 벨만포드 .. 2023. 8. 30.

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

티스토리툴바