단단해지기/Algorithm

[프로그래머스] 입실 퇴실 Javascript

https://programmers.co.kr/learn/courses/30/lessons/86048 코딩테스트 연습 - 7주차 사회적 거리두기를 위해 회의실에 출입할 때 명부에 이름을 적어야 합니다. 입실과 퇴실이 동시에 이뤄지는 경우는 없으며, 입실 시각과 퇴실 시각은 따로 기록하지 않습니다. 오늘 회의실에는 programmers.co.kr 한 방의 출입했던 사람들에 대하여 입실 순서와 퇴실 순서가 주어질 때 반드시 만날 수 밖에 없는 사람을 구하는 문제이다. 퇴실은 입실하기 전에는 일어날 수 없는 행동이다. 이에 따라 퇴실 순서와 입실 순서에 각각 인덱스를 두는 투포인터 기법을 사용했다. 퇴실 순서에 해당하는 사람이 입장하기 전까지 입실 순서에 따라 입장시킨다. 1 을 모든 사람이 퇴실할 때까지 반..

[프로그래머스] 복서 정렬하기 Javascript

https://programmers.co.kr/learn/courses/30/lessons/85002 코딩테스트 연습 - 6주차_복서 정렬하기 복서 선수들의 몸무게 weights와, 복서 선수들의 전적을 나타내는 head2head가 매개변수로 주어집니다. 복서 선수들의 번호를 다음과 같은 순서로 정렬한 후 return 하도록 solution 함수를 완성해주세요 programmers.co.kr 복서들의 정보가 주어질 때, 이를 토대로 복서 정보가 담긴 배열을 정렬하는 문제이다. 즉, sort의 compare 함수를 정의하면 된다. Javascript의 sort는 compare 함수에서 음수를 반환하면 1번 파라미터가 앞의 순서에 놓이도록 정렬된다. winRate가 더 높은 요소를 앞에 배치하고 싶다면 co..

[프로그래머스] 모음사전 Javascript

https://programmers.co.kr/learn/courses/30/lessons/84512 코딩테스트 연습 - 5주차_모음사전 사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니 programmers.co.kr 이 모음 사전은 다음과 같은 순서로 단어가 나열된다. 경우의 수를 이용하면 쉽게 해결할 수 있을 것으로 생각했다. 우선, [A, E, I, O, U] 라는 배열을 만들었다. 항상 이 순서대로 단어가 나타나므로 이 배열의 인덱스 를 활용해 몇 번째 단어인지 유추할 수 있다. A로 시작하는 단어는 총 몇개일까? ..

[백준/BOJ 알고리즘] 17845 수강 과목 C++

https://www.acmicpc.net/problem/17845 17845번: 수강 과목 첫줄에 서윤이의 최대 공부시간 N (1 ≤ N ≤ 10,000), 과목 수 K (1 ≤ K ≤ 1,000)이 공백을 사이에 두고 주어진다. 이후 K개의 줄에 중요도 I (1 ≤ I ≤ 100,000), 필요한 공부시간 (1 ≤ T ≤ 10,000)이 www.acmicpc.net 0-1 Knapsack 문제이다. 링크 에서 0-1 Knapsack에 대해 알아볼 수 있다. (필자가 작성한 글임) bottom-up 방식으로 DP를 구성하면 된다. O(NK)의 시간복잡도를 갖는다. #include #include #define MAX_N 10001 #define MAX_K 1001 using namespace std; ..

[백준/BOJ 알고리즘] 10830 행렬 제곱 C++

https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 주어진 행렬 A에 대하여 입력 B만큼 제곱한 행렬을 출력하는 문제이다. B는 100,000,000,000 이하의 값을 갖는다. 즉, A를 B번 제곱하는 방식으로는 해결할 수 없다. 분할정복 을 통해 문제를 해결할 수 있다. A의 거듭제곱은 다음과 같이 나타낼 수 있다. 분할정복을 통해 100,000,000,000번 제곱한 값을 찾는다면, 약 36~7번의 연산으로 찾을 수 있다. 최종적으로 시간복잡도는 다음과 같..

[백준/BOJ 알고리즘] 16236 아기상어 C++

> www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 아기 상어가 바다에서 엄마 상어 없이 얼마나 물고기를 잡아먹으며 버틸 수 있는가.. 하는 문제이다. 뚜루뚜두둡. 더 이상 먹을 물고기가 없을 때까지의 시간을 계산하여 출력하면 된다! 문제 조건이 생각보다 까다롭고 이해하기 어려워서 좀 헤맸던 문제이다... 처음엔 좌표와 비용을 갖는 이중pair(?) 자료형을 큐에 넣고 작업했는데, 시간초과가 나서 비용 정보를 갖는 배열을 생성해서 해결했다. 문제의..

[백준/BOJ 알고리즘] 1039 교환 C++

> www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 원래 이 문제를 풀 생각은 없었는데, 한 친구가 못 풀겠다고 같이 풀자고해서 풀게 되었다. 기존 그래프 탐색 문제와는 좀 다른 느낌이어서 나름 재밌게 풀었다. 문제의 핵심 N은 최대 999,999 의 값을 갖는다. 즉 최대 6자리 자연수라는 것. K가 10보다 작으니, 전부 구해도 된다. K번 연산을 한 동안 나온 최대값이 아닌, K번째 연산을 했을 때 나올 수 있는 최대값을 구해야한다. 큐를 이용하여 구현했는데, 큐에 담기게 될 것은, 각 자리의 숫자가 아닌 i (0 k) b..

[백준/BOJ 알고리즘] 2573 빙산 C++

> www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 � www.acmicpc.net 오랜만에 알고리즘 풀다가 마음대로 안되서 화가 났던 문제이다..... 그래도 맞아서 기분 좋다. 기본적인 그래프 탐색을 통해 해결할 수 있는 문제이다. 난 DFS를 통해 구현했다. 문제의 핵심 빙산 높이가 담긴 배열의 가장자리는 모두 0 이므로, 탐색대상에서 제외해야한다. 각 빙산의 높이가 1년마다 얼만큼 녹을 지 상하좌우의 빙산을 탐색하여 모든 빙산의 녹는 정도를 구한 후에 빙산을 녹여야한다. 빙..

[백준/BOJ 알고리즘] 3190 뱀 C++

> https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제 설명이 잘 돼 있어 재밌게 풀었던 문제이다. 좌표를 나타내기 위해 pair를 사용하였다. 뱀이 차지하고 있는 공간(?)의 좌표를 큐에 담도록 한다. 기본적으로 뱀이 이동할 때 머리가 한칸 전진하고, 꼬리가 따라온다. 사과를 먹었다면 머리만 전진한다고 생각하면 이해가 쉽다. 머리가 한칸 전진 : 새로운 좌표를 큐의 front에 PUSH 꼬리가 따라옴 : 큐의 end 값을 POP 사과를 먹을 때 뱀..