Algorithm
[프로그래머스] 튜플
목차 (클릭시 해당 목차로 이동) 문제 설명 셀수있는 수량의 순서있는 열거 또는 어떤 순서를 따르는 요소들의 모음을 튜플(tuple)이라고 합니다. n개의 요소를 가진 튜플을 n-튜플(n-tuple)이라고 하며, 다음과 같이 표현할 수 있습니다. (a1, a2, a3, ..., an) 튜플은 다음과 같은 성질을 가지고 있습니다. 중복된 원소가 있을 수 있습니다. ex : (2, 3, 1, 2) 원소에 정해진 순서가 있으며, 원소의 순서가 다르면 서로 다른 튜플입니다. ex : (1, 2, 3) ≠ (1, 3, 2) 튜플의 원소 개수는 유한합니다. 원소의 개수가 n개이고, 중복되는 원소가 없는 튜플 (a1, a2, a3, ..., an)이 주어질 때(단, a1, a2, ..., an은 자연수), 이는 다음..
[프로그래머스] 불량 사용자
목차 (클릭시 해당 목차로 이동) 문제 설명 개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 사용자라는 이름으로 목록을 만들어서 당첨 처리 시 제외하도록 이벤트 당첨자 담당자인 "프로도" 에게 전달하려고 합니다. 이 때 개인정보 보호을 위해 사용자 아이디 중 일부 문자를 '*' 문자로 가려서 전달했습니다. 가리고자 하는 문자 하나에 '*' 문자 하나를 사용하였고 아이디 당 최소 하나 이상의 '*' 문자를 사용하였습니다. "무지"와 "프로도"는 불량 사용자 목록에 매핑된 응모자 아이디를 제재 아이디 라고 부르기로 하였습니다. 예를 들어, 이벤트에 응모한 전체 사용자 아이디 ..
[프로그래머스] 보석 쇼핑
목차 (클릭시 해당 목차로 이동) 문제 설명 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 개발자 출신으로 세계 최고의 갑부가 된 어피치는 스트레스를 받을 때면 이를 풀기 위해 오프라인 매장에 쇼핑을 하러 가곤 합니다. 어피치는 쇼핑을 할 때면 매장 진열대의 특정 범위의 물건들을 모두 싹쓸이 구매하는 습관이 있습니다. 어느 날 스트레스를 풀기 위해 보석 매장에 쇼핑을 하러 간 어피치는 이전처럼 진열대의 특정 범위의 보석을 모두 구매하되 특별히 아래 목적을 달성하고 싶었습니다. 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매 예를 들어 아래 진열대는 4종류의 보석(RUBY, DIA, EMERALD, SAPPHIRE) 8개가 진열된 예시입니다. 진열대..
![[프로그래머스] 순위 검색](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbaSXnV%2Fbtq2DteLVGT%2FArzXM8TqBg7Hot3Qtjo2yK%2Fimg.png)
[프로그래머스] 순위 검색
목차 (클릭시 해당 목차로 이동) 문제 설명 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 카카오는 하반기 경력 개발자 공개채용을 진행 중에 있으며 현재 지원서 접수와 코딩테스트가 종료되었습니다. 이번 채용에서 지원자는 지원서 작성 시 아래와 같이 4가지 항목을 반드시 선택하도록 하였습니다. 코딩테스트 참여 개발언어 항목에 cpp, java, python 중 하나를 선택해야 합니다. 지원 직군 항목에 backend와 frontend 중 하나를 선택해야 합니다. 지원 경력구분 항목에 junior와 senior 중 하나를 선택해야 합니다. 선호하는 소울푸드로 chicken과 pizza 중 하나를 선택해야 합니다. 인재영입팀에 근무하고 있는 니니즈는 코딩테스트 결과를 분석하여 채용에 참여..
![[프로그래머스] 풍선 터뜨리기](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FyHG4t%2Fbtq2zZZoMPT%2F2EJKPUcwWuwuGKmY5KKOVk%2Fimg.png)
[프로그래머스] 풍선 터뜨리기
목차 (클릭시 해당 목차로 이동) 문제 설명 일렬로 나열된 n개의 풍선이 있습니다. 모든 풍선에는 서로 다른 숫자가 써져 있습니다. 당신은 다음 과정을 반복하면서 풍선들을 단 1개만 남을 때까지 계속 터트리려고 합니다. 임의의 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터트립니다. 터진 풍선으로 인해 풍선들 사이에 빈 공간이 생겼다면, 빈 공간이 없도록 풍선들을 중앙으로 밀착시킵니다. 여기서 조건이 있습니다. 인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 할 수 있습니다. 즉, 어떤 시점에서 인접한 두 풍선 중 번호가 더 작은 풍선을 터트렸다면, 그 이후에는 인접한 두 풍선을 고른 뒤 번호가 더 큰 풍선만을 터트릴 수 있습니다. 당신은 어떤 풍선이 최후까지 남을 수 있는..
위상정렬(Topology Sort) 이론
위상정렬 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것 이 알고리즘이 왜 필요할까? 어느 문제에서 사용할까? 예를들어, 대학교 커리큘럼처럼 선수과목이 있는 과목이 있다고 가정해보자. 고급 알고리즘을 수강하기 위해서는 자료구조 -> 알고리즘 -> 고급 알고리즘의 순서로 수강해야한다. 자료구조 -> 고급알고리즘 -> 알고리즘 의 순서로는 수강할 수 없다. 이와같이, 방향그래프의 방향성에 거스르지 않도록 나열해야하는 문제에서 위상정렬을 사용할 수 있다. 진입차수와 진출차수 위상정렬을 구현하기 위해서 진입차수와 진출차수의 개념을 짚고 넘어가야 한다. 진입차수 : 특정한 노드로 들어오는 간선의 개수 진출차수 : 특정한 노드에서 나가는 간선의 개수 위상 정렬 알고리즘 구현 ..
신장트리와 크루스칼 알고리즘
신장트리 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는 부분 그래프 그렇다면, 신장트리가 왜 필요할까? 어느 문제에서 쓰일 수 있을까? 예를들어 N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓아 전체 도시가 최소비용으로 서로 연결될 수 있게 도로를 설치하는 경우를 생각해보자. N개의 도시를 다 연결하기 위해서 모든 노드가 포함되어야 하고 최소비용으로 연결하기 위해서 사이클이 존재하지 않고, 최소비용의 간선만 존재해야 한다. 그러면 주어진 데이터에서 신장트리를 어떻게 만들 수 있을까? 크루스칼 알고리즘 대표적인 최소 신장 트리를 구할 수 있는 알고리즘이다. 구현방법 간선 데이터를 비용에 따라 오름차순으로 정렬한다. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다..
Union Find 자료구조 이론
Union Find 자료구조 ( 서로소 집합 자료구조 ) 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 여기서 집합은 트리구조를 의미하고, 서로소 부분 집합은 루트노드가 다른 것을 의미한다. 그래서, Union 각자 서로소인 부분 집합을 하나의 집합으로 합치는 연산. ex) union(1, 4) 이면 1의 루트노드와 4의 루트노드를 비교해서 더 큰 루트노드의 부모를 작은 루트노드로 세팅한다. 주의 : 해당 노드가 아닌 루트노드의 부모를 세팅하는 것이다. Find 어떤 원소가 어떤 집합에 속해있는지 (루트노드가 무엇인지) 알려주는 연산 ex) 루트를 찾을 때 까지 (부모가 자기자신인 경우) 부모를 재귀적으로 호출한다. 이라고 보면된다. 동작방식을 그림으로 살펴보자 동작방식 이렇게 ..
![[ACM-ICPC] 화성탐사](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FUXZaS%2Fbtq0MUTkhyG%2FWg7Iiz1VFCvLQjg83nwow0%2Fimg.png)
[ACM-ICPC] 화성탐사
입력 예시 3 3 5 5 4 3 9 1 3 2 7 5 3 7 2 0 1 2 8 0 9 1 1 2 1 8 1 9 8 9 2 0 3 6 5 1 5 7 9 0 5 1 1 5 3 4 1 2 1 6 5 3 0 7 6 1 6 8 5 1 1 7 8 3 2 3 9 8 0 7 6 4 1 5 8 3 2 4 8 3 7 4 8 4 8 3 4 출력예시 20 19 36 초기접근 처음에는 다이나믹 프로그래밍으로 접근했다. 2차원 공간의 왼쪽 위 -> 오른쪽 아래로 가장 빠르게 가는 경우에서 상하좌우로 이동하는 방향에서 좌, 상은 쓸모없는 움직임이라고 생각했다. (한번에 가는것이 돌아가는 것보다 항상 비용이 적을 것이라는 오해) 그래서 우, 하 (오른쪽으로 가기, 아래로 가기) 의 움직임만 고려한 다이나믹 프로그래밍으로 풀었다. 그..
[Google 인터뷰] 못생긴 수
문제 못생긴 수란, 소인수분해 했을 경우 나오는 소인수가 2, 3 그리고 5뿐인 수를 이야기 하며, 이를 수열로 늘어놓으면 다음과 같다. 1, 2, 3, 4, 5, 6, 8, 9, 10, 12... 이는 처음나오는 10개의 못생긴 수이며, 편의상 1을 포함하도록 하자. 정수 n이 주어졌을 때, n번째 못생긴 수를 출력하는 프로그램을 작성하라. 입출력 입력 출력 10 12 4 4 초기접근 1001크기의 리스트를 만들고 각 인덱스에 1이 표시되어있으면 못생긴 수로 판단한다. dp = [0]*1001 dp[1], dp[2], dp[3], dp[5]를 1로 표시한다. 0인 값들을 2,3,5로 나눠보고 나누어떨어지면 1로 표시한다. 1로 표시된 것들의 개수를 세어나가면서 n이 되면 종료하고 해당 인덱스를 출력한다..