PS TIL
1.[PS] 이분탐색(Upper bound, Lower Bound) [11561 징검다리]
BOJ 11561번 징검다리1~N까지의 징검다리 존재한다. 제자리뛰기로 바로 이동이 가능하다.1\. 첫 징검다리는 점프해서 아무거나 밟을 수 있다.2\. 두번째는 이전에 점프한 거리보다 1 이상 긴 거리를 가야한다.3\. N번 징검다리를 반드시 밟음으로써 건너기를 마무
2.[PS] 이분탐색 [입국심사 (프로그래머스)]
입국심사 기다리는 사람 n명이 있고, 각 심사관이 심사하는데 걸리는 시간 times\[]이다. n명이 입국심사를 위해 줄을 서서 기다린다. 한 심사대에서는 동시에 한명만 심사 가능하다. 더 빨리 끝나는 심사대가 있다면 기다렸다가 그곳으로 가서 심사 가능하다.모든 사람이
3.[PS] DFS [24444 알고리즘수업]
N 정점, M 간선 무방향 그래프. 정점 번호는 1~N. 가중치는 모두 1이다.정점 R에서 시작해 DFS할경우 방문 순서 출력한다.문제 이름부터 깊이 우선 탐색(DFS)라고 박혀 있어서 크게 접근을 고민할 일이 없었다. 대신 원래 DFS를 재귀 방식으로 푸는 것을 즐겨
4.[PS] 그리디 [2457 공주님의 정원]
N개의 꽃은 모두 같은 해에 피어서 같은 해에 진다.N개의 꽃 중 두 조건을 만족하는 꽃들을 선택하자.1\. 3/1~11/30까지 매일 꽃이 한가지 이상 피어있도록2\. 정원에 심는 꽃들의 수를 가능한 적게N개의 꽃 중에서 두 조건을 만족하는 꽃들을 선택할 때, 선택한
5.[PS] DFS/재귀 [모음사전(프로그래머스)]
A, E, I, O, U 다섯 글자를 이용해 길이가 최대 5인 단어를 만들 수 있다. 이 단어들만 들어있는 사전이 있다고 해보자. 단어 word가 주어질 때 이것이 사전에서 몇 번째 단어인지 찾아내자.처음에는 word의 글자를 인덱스 순서별로 조사해 규칙성이 있는 수식
6.[PS] DFS [2644 촌수계산]
사람들에 대한 부모 자식 간의 관계가 주어졌을 때, 두 사람의 촌수 계산하자.가계도처럼 사람을 연결해야하니, 딱 봐도 그래프를 활용해야 하는 문제처럼 보였다.생각해보면 DFS나 BFS나 어느 방법으로 탐색을 해도 결국 답은 찾을 수 있을 것이라고 생각했다. 내가 조금
7.[PS] BFS [7562 나이트의 이동]
lxl 체스판에서 나이트의 초기 칸과, 이동하려는 칸이 주어진다. 나이트는 몇번 움직여야 해당 칸으로 이동할 수 있는가?일단 탐색을 진행하면 되겠다고 생각했다. 한 변의 길이 l이 최대 300이므로 체스판은 아무리 커봐야 90000의 칸을 가진다. BFS, DFS 모두
8.[PS] 투 포인터 [1253 좋다]
어떤 수가 주어진 수들 중 다른 두 개의 합으로 나타낼 수 있으면 좋은 수이다.주어진 수들 중 좋은 수는 몇 개인지 출력하라.배열을 정렬해, 한 숫자에 대해서 투 포인터 방식으로 제일 좌측과 우측에서 시작해서 더해보면 어떨까 싶었다. 그 더한 결과가 찾으려는 숫자보다
9.[PS] 그리디 [1461 도서관]
한번에 M권의 책을 들 수 있는데, N개의 책을 원위치로 돌려놔야한다.책의 위치는 정수 좌표이고, 현재 나와 책들은 0에 위치한다.모두 돌려놨을때 드는 최소 걸음수를 출력하자.처음에는 감이 잡히지 않았으나, 테스트케이스들을 보고 직접 한번 정리해보니 금방 규칙을 찾을
10.[PS] 구현/수학 [도넛과 막대 그래프(프로그래머스)]
문제가 좀 길다.. 스크린샷을 두개까지 올려야되는 문제는 처음..도넛 모양, 막대 모양, 8자 모양 그래프가 있다.크기가 n인 도넛 모양 그래프는 n개의 정점과 n개의 간선을 가지고, 순서대로 순환하는 형태이다.크기가 n인 막대 모양 그래프는 n개의 정점과 n-1개의
11.[PS] DFS [30689 미로보수]
미로가 주어지고, 미로의 칸에 있는 화살표대로 움직여야 한다.미로를 탈출하지 못하는 경우에는 칸에 점프대를 설치해 바로 빠져나오게 한다.점프대 설치에는 Cost(i,j) 만큼의 비용이 든다. 최소한의 비용으로 어느 칸에서 시작해도 미로를 탈출하게 하자.미로를 DFS로
12.[PS] 그리디 [미로 탈출 명령어(프로그래머스)]
문제 나의 요약 n x m 미로가 주어진다. (x, y) 점에서 출발해 (r, c) 점으로 이동해 탈출해야한다. 한 번에 상하좌우 중 대신 탈출에는 조건이 세가지 있다. 미로 바깥으로는 못나감 이동하는 거리가 총 k여야 함. 같은 점을 두번 이상 방문해도 됨. 탈
13.[PS] BFS/DFS [2665 미로만들기]
nxn 바둑판 모양으로 총 n2의 방이 있다. 일부는 검은방, 나머지는 모두 흰방. 검은 방은 사면이 벽. 서로 붙어있는 흰방은 문이 있음. 좌상에서 우하로 가려고 하는데, 검은방을 최소 몇개 바꿔야 갈수있는지 DFS로 가장 먼 좌표들을 저장해서 아님 그냥 좌상
14.[PS] Trie [2179 비슷한 글자]
N개의 소문자로 된 단어가 주어진다. 이들 중 접두사의 길이가 가장 긴 두 단어를 찾아 출력하자. 여러개일 경우에는 먼저 위치한 접두사의 단어들부터 출력하자.보자마자 Trie 자료구조가 생각났다. Trie 자료구조의 형태는 다음 사진을 보면 쉽게 알 수 있다만약 'ge
15.[PS] 구현 [2056 작업]
작업 N개가 있다. 걸리는 시간이 정수로 주어진다.작업들 사이에는 선행 관계가 존재한다. 물론 없는 작업들도 존재한다. (1번이 그 경우)선행관계에서 자유로워진 작업들은 동시에 수행 가능하다.작업을 완료하기 위해 필요한 최소 시간을 출력하자.그냥 사람이 직접 이 문제를
16.[PS] 그리디/조합 [상담원 인원(프로그래머스)]
문제 나의 요약 멘토 n명, 상담 유형 k개가 있다. 멘토는 상담 유형 하나 담당한다. 멘토는 한명과만 상담가능하고, 상담시간은 참가자가 요청한 시간만큼 진행한다. 상담 요청 과정은 다음과 같다. 참가자가 요청, 상담 유형 담당하는 멘토 중 상담중이 아닌 멘토와
17.[PS] 구현 [1022 소용돌이 예쁘게 출력하기]
0행 0열에 1, 0행 1열에 2를 쓰는 소용돌이가 거기서부터 반시계 방향으로 시작된다.출력해야하는 좌표는 (r1, c1)가 가장 왼쪽 위, (r2, c2)가 가장 오른쪽아래이다.이때 다음의 조건대로 출력하자.1\. r1부터 r2행까지 차례대로 출력한다.2\. 원소는
18.[PS] DFS/플로이드-워셜 [17182 우주탐사선]
탐색할 행성 개수, 발사되는 행성 위치, 행성간 이동 시간 행렬이 주어진다.모든 행성을 탐사하는데 걸리는 최소 시간 계산하자.행성은 중복 방문이 가능하다.중복 방문이 가능하기 때문에, 단순히 그리디나 순회하는 방식으로는 불가능하다.일단 모든 행성 간의 시간을 다시 계산
19.[PS] DP [산 모양 타일링(프로그래머스)]
2n+1개의 정삼각형을 이어붙이면 윗변이 n, 아랫변이 n+1인 사다리꼴이 만들어진다. 이때 사다리꼴 위쪽에 정삼각형을 붙여 새로운 모양을 만듬. 이 모양을 정삼각형 타일 또는 정삼각형 2개를 이어붙인 마름모 타일로 채움. 이들은 회전이 가능함. 이때 채우는 경우의
20.[PS] 백트래킹 [15686 치킨 배달]
NxN 도시가 있음 각 칸은 빈칸, 치킨집, 집. 세개중 하나. 치킨거리: 집과 가장 가까운 치킨집사이의 거리. 도시의 치킨거리: 모든 집의 치킨거리의 합 거리는 |r1-r2| + |c1-c2| 이다. 0이 빈칸, 1이 집, 2가 치킨집. 치킨집중 최대 M개만
21.[PS] 그리디 [2437 저울]
양팔 저울로 물건 무게 측정한다.저울의 한쪽에는 저울추, 다른쪽에는 측정하려는 물건만 올려놓을 수 있다.N개의 저울추가 주어질 때, 추들을 사용해 측정할 수 없는 양의 정수 무게 중 최솟값을 출력하자.N이 최대 1000이기 때문에, 조합을 이용한 백트래킹 기법으로는 불
22.[PS] DFS/DP [2169 로봇 조종하기]
NxM 배열로 된 지형이 존재한다. 탐사하는 로봇은 '하, 좌, 우' 방향으로 이동이 가능하다. '상' 방향으로는 이동이 불가하다. 한번 탐사한 지역은 다시 탐사가 불가하다.왼쪽 위에서 출발해, 오른쪽 아래에 도착할 때, 탐사한 지역들의 가치의 합이 최대인 값을 찾아
23.[PS] 백트래킹 [주사위 고르기(프로그래머스)]
A와 B가 n개의 주사위를 가지고 승부한다. 주사위에 쓰인 수의 구성은 모두 다르다.각각 주사위를 굴리고, 점수를 합해 계산한다. 합산 점수가 더 큰쪽 승리하고, 같다면 무승부이다.A는 승리할 확률이 높도록 n/2개의 주사위를 먼저 가져가려고 한다.승리할 확률이 가장
24.[PS] 백트래킹 [1446 지름길]
D 길이의 고속도로를 지난다. 고속도로엔 지름길 존재한다. 지름길은 일방통행이고, 길을 거꾸로 가는 역주행은 불가하다. 이때 운전해야하는 거리의 최솟값을 출력하자.처음엔 그리디로 접근 가능한지 생각했지만, 지름길마다 길이가 또 다르기 때문에 그리디로 한번에 파악할 수는
25.[PS] 백트래킹 [이모티콘 할인행사(프로그래머스)]
행사를 진행하는데, 목표가 다음과 같다.1\. 이모티콘 플러스 가입자를 최대한 늘리기2\. 이모티콘 판매액을 최대한 늘리기n명에게 m개의 이모티콘을 할인한다. 이모티콘마다 할인이 반드시 존재하고, 할인율은 10, 20, 30, 40으로 결정할 수 있다.사용자들은 다음
26.[PS] 벨만-포드 [11657 타임머신]
N개의 도시, M개의 버스가 존재한다. 버스는 시작도시 A, 도착도시 B, 걸리는 시간 C가 주어진다.시간 C는 0으로 순간 이동을 하거나 음수로 시간을 되돌아갈 수도 있다.1번 도시에 출발해 나머지 도시로 가는 가장 빠른 시간을 각각 출력한다. 해당 도시로 갈 수 없
27.[PS] 그리디 [택배 배달과 수거하기(프로그래머스)]
일렬로 나열된 n개의 집에 택배 배달과 빈 상자를 수거하는 작업을 한다. 택배는 모두 택배 상자에 담겨 물류창고에 보관된다. i번째 집은 물류창고에서 거리 i 만큼 떨어져있다.트럭에는 상자 cap개를 보관할 수 있다. 트럭 하나로 모든 배달, 수거 마치고 물류창고 돌아
28.[PS] 다익스트라 [5972 택배 배송]
N개의 헛간, M개의 소들의 양방향 길이 그려져있다.소들의 길은 두 개의 떨어진 헛간 A_i와 B_i를 잇는다.두 개의 헛간은 하나 이상의 길로 연결되어 있을 수 있다.1부터 N으로 가는데 최소 비용을 출력하자.정점 1에서 정점 N으로 가는 최소 비용을 구하는 문제이다
29.[PS] DFS [표현 가능한 이진트리(프로그래머스)]
이진트리를 수를 표현하는 방법은 다음과 같다.1\. 빈 문자열을 생성한다.2\. 더미 노드를 추가해 포화 이진트리로 만든다.3\. 포화 이진트리의 노드를 왼쪽부터 오른쪽까지 순서대로 살펴본다. (왼쪽 자식 -> 부모 -> 오른쪽 자식)4\. 살펴본 노드가 더미 노드면,
30.[PS] 투 포인터 [17609 회문]
회문: 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열유사 회문: 한 문제를 삭제하여 회문으로 만들 수 있는 문자열주어진 문자열이 회문인지, 유사 회문인지, 둘다 아닌지 0, 1, 2로 출력하자.문자열의 시작과 끝에서 검사하며 각각 오른쪽, 왼쪽으로 나아간다.