Algorithm

2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 문제를 처음 봤을 때 이해가 가지 않아서 정리했습니다. 문제 설명을 왜 이렇게 했을까 😞😞 문제 이해하기 회장은 점수가 가장 적은 사람이 됩니다. 점수 계산 방법은 다음과 같습니다. 1점 : A회원이 B회원과 친구 관계 (A-B) 2점 : A회원이 B회원과 친구 관계이면서, B회원의 친구인 C회원과도 친구 관계 (A-B-C) 3점 : A회원이 B회원과 친구 관계이면서, B회원의 친구인 C회원과도 친구 관계이면서, C회원의 친구인 D회원과도 친구 관계 (A-B-C..

루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법 특징 장점 노드 수가 적고 깊이가 얕은 경우 빠르게 동작 가능 단순 검색 속도가 깊이 우선 탐색 (DFS) 보다 빠름 너비를 우선 탐색하기에 답이 되는 경로가 여러 개인 경우 최단 경로임을 보장 최단 경로가 존재한다면 어느 한 경로가 무한히 깊어진다해도 최단 경로를 반드시 찾을 수 있음 단점 재귀 호출의 DFS 와 달리 큐에 다음으로 탐색할 정점들을 저장해야 하므로 저장 공간이 많이 필요함 노드 수가 늘어나면 탐색해야 하는 노두 또한 많아짐 노드 탐색 순서 루트 노드에서 시작한다. 루트 노드와 인접하고 방문된 적 없으며, 큐에 저장되지 않은 노드를 큐에 넣는다. 큐에서 노드를 꺼내어 그와 인접한 노드들 중 방문된 적 없으며, 큐에 저장되지 않는 노..

https://school.programmers.co.kr/learn/courses/30/lessons/64065 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 요약 원소의 개수가 n개이고 중복되는 원소가 없는 튜플(a1, a2, a3,... an)이 주어질 때, 이는 집합 기호 ({ })를 이용해 다음과 같이 표현할 수 있습니다. {{a1}, {a1, a2}, {a1, a2, a3}, ... , {a1, a2, a3,...., an}} 예를 들어 튜플이 (2, 1, 3, 4)인 경우 이는 {{2}, {2, 1}, {2, 3, 1}, {2, 1, 3..

2016번: 미팅 주선하기 태현이는 네 명의 친구와 5대 5 미팅에 참여하게 되었다. 미팅 자리에서 각 사람의 소개가 끝나고, 각자의 짝을 정할 시간이 되었는데, 태현이가 다음과 같은 방법을 제안하였고, 모두 이에 찬성 www.acmicpc.net 문제 미팅 자리에서 각자의 짝을 정하는 방법은 다음과 같습니다. 태현이가 1번, 나머지 남학생이 2-5번, 여학생이 6-10번입니다. 각자 상대에 대한 선호도 순위를 매겨서 씁니다. 이때, 두 명 이상의 상대에게 같은 선호도를 적용하면 안 되고, 5명 모두에 대한 순위를 매겨야 합니다. 6번 여학생부터 가장 좋아하는 남학생에게 프러포즈를 하며, 퇴자 맞으면 다음 순서의 남학생에게 프러포즈를 합니다. 남학생은 현재 짝이 없으면 무조건 프러포즈를 받으며, 두 명 ..

https://programmers.co.kr/learn/courses/30/lessons/64063 코딩테스트 연습 - 호텔 방 배정 programmers.co.kr 호텔에는 방이 총 k개 있으며, 각각의 방은 1번부터 k번까지 번호로 구분됩니다. 배정 규칙 1. 한 번에 한 명씩 신청한 순서대로 배정됩니다. 2. 고객은 투숙하기 원하는 방 번호를 제출합니다. 3. 고객이 원하는 방이 비어있따면 즉시 배정합니다. 4. 고객이 원하는 방이 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다. 문제 풀이 해당 문제는 Union-Find를 활용하여 풀어야 합니다. Union-Find는 여러 노드가 존재할 때, 두 개의 노드를 선택해서 현재 두 노드가 서로 같은 그래..

2615번: 오목 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호 www.acmicpc.net 바둑판에 19개의 가로줄과 19개의 세로줄이 그려져 있을 때, 같은 색의 바둑알이 연속적으로 다섯 알 놓이면 이기게 되는 게임입니다. 여기서 연속적으로는 가로, 세로 또는 대각선 방향을 뜻하며, 여섯 알 이상이 연속적으로 놓은 경우에는 이긴 것이 아닙니다. 바둑판 상태가 주어졌을 때, 검은색은 1, 흰색은 2, 알이 놓이지 않은 자리는 0으로 표시합니다. 검은색이 이기면 1, 흰색이 이기면 2, 아직 승부가 결정되지 않으면 0을 출력합니다. 그리고 검은색 또는..

코딩테스트 연습 - [3차] n진수 게임 N진수 게임 튜브가 활동하는 코딩 동아리에서는 전통적으로 해오는 게임이 있다. 이 게임은 여러 사람이 둥글게 앉아서 숫자를 하나씩 차례대로 말하는 게임인데, 규칙은 다음과 같다. 숫자를 0 programmers.co.kr 이 문제는 n진법을 구하는 방법을 적용하면 쉽게 해결할 수 있는 문제입니다 😎😎 각 숫자의 범위도 크지 않아서 m명의 인원이 t번 동안 진행하면서 나올 수 있는 모든 숫자 리스트를 만들었습니다. 다시 말하자면, [0, 1, 2, 3] 에 대해 2진법으로 말하면 0 → 0 1 → 1 2 → 10 3 → 11 과 같은 방식으로 바꾼 [0, 1, 1, 0, 1, 1]을 저장해두는 방식으로 진행했습니다. 이 때, 리스트에 저장하는게 아닌 n진법 구하는 ..

1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 이 문제는 주어진 C개의 문자를 L 길이의 암호로 만드는 문제이며, 암호는 최소 한 개의 모음과 최소 두 개의 자음을 포함한 정렬된 형태로 만들어야 합니다. 브루트포스를 이용해서 풀면 되는 문제라 편안한 마음으로 풀었네요 😎😎 import java.io.*; import java.util.Arrays; import java.util.StringTokenizer; class Main { static BufferedReader br = new BufferedReader(..

구름LEVEL 코딩테스트에서 가장 높은 비중을 차지하는 알고리즘 문제를 제작하고 풀이할 수 있는 온라인 저지 서비스입니다. 기업에서 선호하는 C, C++, 파이썬(Python), 자바(Java), 자바스크립트(Javascript) 이 level.goorm.io 이 문제는 2의 제곱수의 용량을 가진 램 중에서 파손이 되어 2의 제곱수의 용량을 가지지 않는 램의 수와 번호를 출력하는 문제입니다. 비트 마스크를 이용하면 되게 간단한 문제인데 할 줄 몰라서 열심히 찾아봤네요.. 😂😂 2의 n제곱 수를 2진수로 나타내면 2의 0 제곱 : 1 → 1 2의 1 제곱 : 2 → 10 2의 2 제곱 : 4 → 100 2의 3 제곱 : 8 → 1000 과 같이 1로 시작하여 오른쪽을 모두 0으로 채우는 형태입니다. 만약 ..

코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 이 문제는 모든 섬을 연결하기 위해 필요한 최소 비용을 구하는 문제입니다. Greedy와 Union Find를 적용하여 푸는 문제인데, Union Find 문제는 왜 매번 풀이가 바로 생각이 안 날까요...? 😂😂 아무튼 다음과 같은 규칙을 적용하여 문제를 풀면 됩니다! 😎😎 1. 비용을 기준으로 정렬 2. Union Find 알고리즘을 이용해 모든 섬 연결 (이미 연결된 섬은 넘어감!) import java.util.*; class Solution { // 부모 찾기 public static int find(int[] parent, int x) { if(pa..

import java.io.*; import java.util.*; public class Main { public static String strReverse(ArrayDeque deque, boolean isReverse) { String temp = ""; while(!deque.isEmpty()) { if (isReverse) { // 뒤집어진 상태 temp += deque.pollLast(); } else { temp += deque.pollFirst(); } } return temp; } public static String strRemove(String s, String t) { int sLen = s.length(); int tLen = t.length(); int count = tLen ..

코딩테스트 연습 - [3차] 파일명 정렬 파일명 정렬 세 차례의 코딩 테스트와 두 차례의 면접이라는 기나긴 블라인드 공채를 무사히 통과해 카카오에 입사한 무지는 파일 저장소 서버 관리를 맡게 되었다. 저장소 서버에는 프로그램 programmers.co.kr 이 문제는 파일명을 특정 조건에 맞춰 자른 후 정렬하는 문제로, 처음 등장하는 숫자를 기준으로 HEAD, NUMBER, TAIL로 나눕니다. 그러니까 문자, 처음 등장하는 숫자, 최대 길이 5, 문자로 HEAD, NUMBER, TAIL을 나누는 형태입니다. HEAD 부분 문자를 기준으로 사전순 정렬을 하는데, 이 때 대소문자는 구분하지 않습니다. 만약, HEAD 부분의 문자가 MUZI, muzi와 같은 형태라면 동일한 순서로 취급되므로 NUMBER를 ..