본문 바로가기

알고리즘, 문제해결103

[프로그래머스] 멀쩡한 사각형 문제 링크: https://programmers.co.kr/learn/courses/30/lessons/62048 코딩테스트 연습 - 멀쩡한 사각형 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 programmers.co.kr w * h 크기의 직사각형이 주어집니다. 좌측 상단에서 우측 하단으로 대각선을 쭉 긋고, 대각선이 닿지 않은 사각형의 개수를 구하는 문제입니다. 문제의 그림을 보면 힌트를 얻을 수 있습니다. 그림을 보시면, 흰색 바탕의 같은 패턴이 총 네 번 반복되는 것을 알 수 있습니다. 각 패턴은 주어진 큰 직사각형과 마찬가지로 좌상단.. 2021. 10. 28.
[백준 2831번] 댄스 파티 난이도: 골드 III 문제 링크: https://www.acmicpc.net/problem/2831 2831번: 댄스 파티 남자 N명과 여자 N명이 상근이가 주최한 댄스 파티에 왔다. 상근이는 모든 사람의 키를 알고있다. 각 남자는 모두 여자와 춤을 출 수 있고, 여자는 남자와 춤을 출 수 있다. 모든 사람은 많아야 한 www.acmicpc.net 약 3개월 전에 도전했다가 틀리고 미뤄뒀던 (...) 문제입니다. 당시에는 막 조합 생각하고 그랬던 것 같은데... 지금 풀어보니 5분만에 금방 풀리네요 ㅎㅎ 주어진 문제를 보면, 남자와 여자의 키가 각각 주어집니다. 이 때 키가 양수로 주어진다면 해당 사람은 본인보다 키가 큰 이성과 춤을 추고 싶은 사람이고, 키가 음수로 주어진다면 해당 사람은 본인보다 키가.. 2021. 10. 28.
[백준 5214번] 환승 난이도: 골드 I 문제 링크: https://www.acmicpc.net/problem/5214 5214번: 환승 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어 www.acmicpc.net 각 노드와 연결 정보가 주어지고, 시작점으로부터 도착점까지 최단 거리를 구하면 되는 문제입니다. 단순하게 접근했다가 틀렸는데, 문제의 조건을 분석해 봅시다. 한 튜브에 최대 1000개의 역이 연결되어 있고, 튜브는 최대 1000개 존재합니다. 이것을 튜브에 연결된 모든 역이 서로 연결되어 있는 방식으로 구현하면, O(n^3)의 공간복잡도를 .. 2021. 10. 26.
[프로그래머스] 피로도 문제 링크: https://programmers.co.kr/learn/courses/30/lessons/87946 코딩테스트 연습 - 12주차 XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던 programmers.co.kr 프로그래머스 위클리 챌린지 마지막 문제입니다. 문제의 난이도가 일정하지 않은 점이나, 작성된 코드가 노출되어 좋아요를 받는 방식, 예전에 본 듯한 문제들 등이 좀 아쉽긴 했지만 이렇게 위클리 챌린지가 종료된다고 하니 이것도 아쉽네요. 문제 조건을 요약하면 다음과 같습니다. 맨 처음 주어진 피로도가 있다. 피로도는 던전을 접근할 때마다 감소한.. 2021. 10. 26.
[백준 2304번] 창고 다각형 난이도: 실버 II 문제 링크: https://www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 단순 구현 문제입니다. 문제에서 주어진 넓이를 구하려면 다음과 같은 과정을 거치면 됩니다. 가장 높은 기둥의 높이를 미리 구해둔다. 이후 모든 기둥을 좌표 순으로 정렬한다. 좌, 우 양 끝에서 다음과 같은 과정을 거친다. 시작점의 위치와 높이를 기록한다. 가장 높은 기둥 방향으로 전진하며, 이전에 기록한 높이보다 더 높은 기둥을 찾은 경우 아래와 같.. 2021. 10. 22.
[프로그래머스] 아이템 줍기 문제 링크: https://programmers.co.kr/learn/courses/30/lessons/87694# 코딩테스트 연습 - 11주차 [[1,1,7,4],[3,2,5,5],[4,3,6,9],[2,6,8,8]] 1 3 7 8 17 [[1,1,8,4],[2,2,4,9],[3,6,9,8],[6,3,7,7]] 9 7 6 1 11 [[2,2,5,5],[1,3,6,4],[3,1,4,6]] 1 4 6 3 10 programmers.co.kr 푸는데 약 5시간 정도 걸린... ㅠ 문제입니다. 글 작성시간 기준 수요일 오후 5시 반 정도 됐는데 지금까지 푼 사람이 총 101명이네요. (제가 101번째) 이 문제를 접근하려면 크게 세 단계로 나눌 수 있습니다. 주어진 좌표를 이용하여 사각형의 테두리 좌표들을 구.. 2021. 10. 20.

티스토리툴바