Algorithm

출처https://school.programmers.co.kr/learn/courses/30/lessons/87946 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr문제 문제 자체는 이해하기에 어렵지 않다. 데이터 베이스에서 후보키란, 유일성과 최소성을 만족하는 속성이다. 학생들의 인적사항이 주어졌을때, 후보키의 최대 수를 구하면 되는 문제이다.  즉, 유일하기 때문에 식별이 가능해야하고, 불필요한 속성을 포함하지 않고 최소한의 속성만 포함하도록 해야한다. 풀이후보키를 찾기 위해서 특별한 알고리즘이 존재하지 않는다. 결국 모든 속성의 쌍을 보고, 이것이 유일성..

출처https://school.programmers.co.kr/learn/courses/30/lessons/84021 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr문제 game_board의 빈공간에, table에 주어진 도형을 끼워 맞추는 문제이다. 도형은 회전시킬 수 있지만, 뒤집을 수는 없다.이때, 최대 몇칸을 채워넣을 수 있는지 구하는 문제이다. 풀이BFS를 이용하여 풀 수 있는 문제이다. 상당히 코드도 길고 어려울 수 있지만, 다음과 같은 과정을 따라가면 된다. 먼저, BFS 알고리즘을 이용하여 board의 빈 공간과 table에 주어진 모양을 추출한..

출처https://school.programmers.co.kr/learn/courses/30/lessons/42627 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 하드 디스크가 요청을 한번에 하나만 수행할 수 있다고 가정하였을 때, 요청 받은 작업이 완료되는 시간의 평균이 가장 적도록 작업 순서를 정하도록 하는 문제이다. 요청 받은 작업이 완료되는 시간이란, 작업 요청부터 시작되기까지 기다린 시간 + 실제 작업 시간 을 말하며 이는 곧 작업이 끝나는 시간 - 작업 요청 시간이다.풀이이 문제를 해결하기 위해서는 두개의 우선순위가 필요하다. 바로 작업 요..

출처https://school.programmers.co.kr/learn/courses/30/lessons/60057 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 설명이 길다. 하지만 읽다보면 간단하다.만약 aaaabbbb를 1개 단위로 잘라(a, b) 압축하면, a와 b는 각각 네개이기 때문에 4a4b 이렇게 압축되고 , 2개 단위로 잘라서 (aa,bb) 압축하면 2aa2bb 이 되는데, 이렇게 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 구하는 문제이다. 풀이이 문제는 결국, 1개로 잘라 압축할지 부터 문자열의 길이만큼 잘라 압축할지 (이 경..

출처https://school.programmers.co.kr/learn/courses/30/lessons/42579 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 노래의 장르와 재생횟수가 주어진다. 총 재생횟수가 많은 장르부터 출력을 하는데, 한 장르당 가장 많이 재생된 곡 2개를 출력한다. 만약 2개가 아니라면 1개만 출력한다. 만약 곡의 재생횟수가 같으면 고유번호 i가 작은 순서로 출력한다. 풀이이 문제는 복잡하게 생각하지 않고, 내가 만약 코딩이 아니라 손으로 직접 이 과정을 수행한다면 어떤 과정을 통해 수행할까? 라는 생각 아래, 다음과 같은 ..

출처https://www.acmicpc.net/problem/1253 문제 N개의 수가 주어질 때, 어떤 수가 다른 두 수의 합으로 나타낼 수 있다면 그것을 좋은수라고 하는데, 그 갯수를 구하는 문제이다. 풀이먼저, 당연한 말이지만 주어진 N개의 수가 3개 미만이라면, 다른 두 수가 없기때문에 좋은수가 될 수 없다. 다른 두 수를 이용해 합으로 나타낼 수 있는지 알아보려면, 투 포인터 개념을 활용하여 직접 비교해보는 방법 밖에 없다. 하지만 모든 경우를 다 무작정 비교하게 되면, 기준이 되는 원소를 고르는 for문 하나, i j 인덱스를 통해 합이 성립하는지 확인하기 위한 for문이 2개, 총 3개의 반복문을 가진다. N^3 복잡도를 가진 코드는 매우 비효율적인 알고리즘이며 사용하지 않아야 한다. 그렇기..

출처https://www.acmicpc.net/problem/2565 문제 설치된 전깃줄들이 서로 교차하지 않도록 철거하려고 한다. 가장 최소한으로 전깃줄을  모두 교차되지 않게 하기 위해 철거를 할 때, 철거할 전깃줄의 최소 개수를 구하는 문제이다. 풀이교차되지 않는다? 의 개념을 먼저 정립해보려고 한다. 이 문제에서 '교차하지 않는 것'은 왼쪽 A 전봇대에서 번호가 증가하면 할 수록, 연결된 B 전봇대의 번호도 증가해야 한다는 것이다. 즉, A를 기준으로 이전 전봇대와 연결된 전봇대의 번호  현재 전봇대와 연결된 전봇대의 번호인 것이 교차하지 않도록 전깃줄을 설치하는 방법이다. A 전봇대 리스트에서, B에 연결된 전봇대의 번호가 증가하는 가장 긴 수열을 찾으면 되는 문제이다. 최장 증가 부분수열 문제..

출처 https://school.programmers.co.kr/learn/courses/30/lessons/72411 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 개인적으로 처음에 잘 안읽어서 그런지 좀 헷갈렸던 문제였습니다. 문제를 요약하자면, 1. 단품으로 1개씩 파는 레스토랑이 있는데, 2개 이상 묶어서 코스 요리로 만들려고 한다. 2. 단, 코스 요리는 2개 이상의 요리로 구성되어 있으며, 적어도 2명의 손님이 시켜먹은 조합이여야 한다. - 예를들어, 1번 손님은 A, C, D 조합으로 먹었고 2번 손님이 A, D 조합으로 먹었다면, (A..