지민 개발 블로그

📔 문제https://www.acmicpc.net/problem/3015  오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다. 이 역사적인 순간을 맞이하기 위해 줄에서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해졌다.두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.줄에 서 있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다.사람들이 서 있는 순서대로 입력이 주어진다.출력서..

문제 설명https://www.acmicpc.net/problem/6549 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오. 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사..

문제https://school.programmers.co.kr/learn/courses/30/lessons/258712# 문제 설명선물을 직접 전하기 힘들 때 카카오톡 선물하기 기능을 이용해 축하 선물을 보낼 수 있습니다. 당신의 친구들이 이번 달까지 선물을 주고받은 기록을 바탕으로 다음 달에 누가 선물을 많이 받을지 예측하려고 합니다.두 사람이 선물을 주고받은 기록이 있다면, 이번 달까지 두 사람 사이에 더 많은 선물을 준 사람이 다음 달에 선물을 하나 받습니다.두 사람이 선물을 주고받은 기록이 하나도 없거나 주고받은 수가 같다면, 선물 지수가 더 큰 사람이 선물 지수가 더 작은 사람에게 선물을 하나 받습니다.위에서 설명한 규칙대로 다음 달에 선물을 주고받을 때, 당신은 선물을 가장 많이 받을 친구가 ..

https://school.programmers.co.kr/learn/courses/30/lessons/181188 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 설명최소 미사일 발사 몇번을 통해서 방어할 수 있는가에 대한 문제였다. 풀이이 문제의 경우 또 그래프인가? 탐색문젠가 브루트포스인가 병적으로 ㅎㅎ;; 생각하다가... 알고보니 정렬하면 쉽게 끝나는 문제였다. (s,e)범위라 할 때, e를 기준으로 정렬한 후에, 앞선 범위의 마지막 부분이 이번 부분의 앞부분보다 앞에 있을 경우 새로운 미사일이 필요함을 인지하면 된다.   최종코드def solut..

문제https://www.acmicpc.net/problem/12851 문제 분석해당 문제는 BFS 유형이다.  왜 BFS인가?처음에는 DP라고 생각을 했다. 이상하게 유독 BFS문제를 보면 DP라고 생각할 때가 종종 있는 것 같다... 하지만 이 문제가 BFS유형임에 확실한 것은 (물론 DP로도 풀려고하면 풀 수도 있겠지만) "가장 빠른 시간" 과 "가장 빠른 시간으로 찾는 방법" 이라는 키워드가 있기 때문이다. 가장 빠른 방법 중에서도 특히나 가중치가 없는 그래프의 경우에는 BFS임이 자명하다. 만약 가중치가 있을 경우에는 다익스트라 알고리즘을 사용해야한다. 특히나 트리일 경우에는, BFS는 반드시 "최단경로"를 거칠 수 밖에 없다. 왜냐하면, 해당 노드 간의 경로가 단방향, 또한 하나만 존재하기 때..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사www.acmicpc.net 다음 문제는 dfs와 bfs의 가장 기초적인 문제다.  문제 풀이법은 딱히 중요한건 아닌 것 같고, 이 문제를 사실 9개월 전에 한번 풀었다가 감이 죽은 지금 다시 한번 풀었는데 메모리랑 실행시간이 너무 크게 비교가 돼서...(물론 9개월 전 코드가 더 아름다웠다.) 마음이 아파서 왜 그런지 비교해보도록 하겠다. 9개월 전 똑똑했던 나의 코드#include #in..

https://www.acmicpc.net/problem/11047 11047번: 동전 0첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)www.acmicpc.net풀이과정①문제 바라보기기본적인 그리디 문제다.어렵게 낼 수 있다면 굉장히 어렵게 낼 수 있는 문제인데 이 문제의 경우에는 굉장히 기본기본기본적인 문제같다. ②아이디어 펼치기연산자 %와 //을 활용하면 간단히 풀릴 것이다.몫을 구해서 만약 1 이상이라면 남는 돈은 %한 값이 되는거고 빠져나간 동전의 개수는 //가 되는 것이다.이때 필요한 동..

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주www.acmicpc.net 풀이과정①문제 바라보기간단한 graph이론 문제다. DFS문제고, 이해를 위해서 문제에서 제시한 예제 2개를 간선과 노드로 표현해봤다.위의 그림을 보면 1,2,5가 연결되어있고 3,4,6이 연결되어있음을 확일할 수 있다.  따라서 출력값이 2가 되는 것이며,두번째 그림을 보면 1~6이 모두 어떻게든 연결되어있기에 출력값이 1이 됨을 확인할..

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)www.acmicpc.net풀이과정①문제 들여다보기이 문항은 앞전에 푼 11053문제에서 아주 살짝 업그레이드 된 버전의 문제이다.https://stopmin.tistory.com/46 [백준] 11053번 가장 긴 증가하는 부분수열 (Python)https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 ..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이www.acmicpc.net풀이과정①문제 바라보기N으로 전체 수열의 길이를 받고, 다음줄에 array가 입력된다.array에서 몇 개의 수를 지움으로써 만들 수 있는 가장 긴 증가하는 수열의 길이를 인쇄하는 문제다. ②아이디어 열기이 문제는 동적계획법으로 해결이 된다.이중 for문을 활용하여서 해결되는 문제였다.현재 해당하는 위치의 숫자보다 앞에 있는..