지민 개발 블로그

https://www.acmicpc.net/problem/15650 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열고른 수열은 오름차순이어야 한다.입력첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)출력한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다. 풀이 해당 문제에서 경우의 수는 1백트래킹으로 해결할 수 있다. 처음에는 queue를 이용해서 중복없이 M을 구하려고 했는데, 문제에서 요구하는 것은 1부터 N까지 자연수 중에..

📔 문제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://school.programmers.co.kr/learn/courses/30/lessons/258711?language=cpp문제 설명도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프들이 있습니다. 이 그래프들은 1개 이상의 정점과, 정점들을 연결하는 단방향 간선으로 이루어져 있습니다.  위 세가지 그래프가 있는데 이 그래프들과 무관한 정점을 하나 생성하고, 각 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 임의의 정점 하나로 향하는 간선들을 연결했다. 그 후 각 정점에 서로 다른 번호를 매겼다. 이때 우리는 그래프의 간선 정보가 주어지면, 생성한 정점의 번호와 정점을 생성하기 전 도넛의 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수를 구해야한다...

쿼드 트리(QUADTREE)대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리란 것이 있다.주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 위해 쿼드 트리라는 이름이 붙었다. 가장 유명한 예시로 검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현한 사례가 있다. 쿼드 트리는 2**n * 2**n크기의 흑백 그림을 다음과 같은 과정을 거쳐 문자열로 압축한다. 이 그림의 모든 픽셀이 검은 색일 경우 이그림의 쿼드 트리 압축 결과는 그림의 킉에 관계없이 b가 된다.이 그림의 모든 픽셀이 흰 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계 없이 w가 된다.모든 픽셀이 강튼 색이 아니라면, 쿼드 트리는 이그림을 가로 세로로 각각 2등분해 4개의 조각으로 ..

1. 무식하게 풀기공부를 할수록 우아한 답안을 만들고 싶은 마음이 커진다. 그래서 바로 앞에 보이는 쉽고 간단하며 틀릴 가능성이 낮은 답안을 간과하기 쉽다. 이런 실수를 방지하기 위해서 '무식하게 풀 수 있을까?' 라는 생각을 해보아야한다. "brute-force(무식하게 푼다)"컴퓨터의 빠른 계산 능력을 이용해, 가능한 경우의 수를 일일이 나열하며 답을 찾는 방법을 의미한다.이런 알고리즘을 완전 탐색(exhaustive search)라고 한다.  2. 재귀 호출과 완전 탐색컴퓨터가 수행하는 많은 작업들은 대개 작은 조각으로 나눌 수 있다.범위가 작아지면 작아질 수록 각 조각의 형태들은 유사해진다.이러한 작업을 구현할 때 유용하게 재귀 함수(recursive function)/재귀 호출(recursion..

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

알고리즘의 정당성 증명 해결해야 할 문제가 간단할 때는 직관적으로 알고리즘을 설계할 수 있지만, 문제가 복잡해지면 알고리즘이 과연 문제를 제대로 해결하는지 파악하는 것이 힘들다. 물론 단위테스트를 통해서 해결할 수도 있겠지만, 이 방법으로는 턱없이 모자라다. 따라서, 알고리즘의 정확한 증명을 위해서는 각종 수학적인 기법이 동원되어야 한다. 알고리즘에 대한 증명은, 알고리즘을 유도하는 데 결정적인 통찰을 담고 있다. 모든 알고리즘은 치열한 고민과 개선 과정을 거쳐 태어나고 이 과정에서 결정적으로 필요한 깨달음이 증명에 담겨있는 경우가 많다. 또한, 증명을 아는 편이 사용하는 입장에서도 큰 공부가 된다. 1. 반복문 불변식 귀납법은 알고리즘의 정당성을 증명할 때 가장 유용하게 사용되는 기법이다. 대부분의 알..