본문 바로가기

알고리즘 문제77

[백준 - Java] 5567번 : 결혼식 문제 www.acmicpc.net/problem/5567 5567번: 결혼식 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2,3,4 3명의 친구를 결혼식에 초대한다. www.acmicpc.net 설명 ai와 bi가 친구라면, bi와 ai도 친구관계이기에 양방향 그래프로 만들었다. 그리고 친구관계를 인접 리스트를 이용해 표현했다. 상근이는 1번이고, 1번과 인접한 정점(친구). 1번과 인접한 정점의 인접한 정점(친구의 친구) 딱 3번을 거친, 3번까지 BFS 탐색한 정점까지만 결혼식에 초대할 수 있다는 것. 정점의 방문여부를 확인하는 visited배열은 기존에 작성할 때 boolean으로 주로 선언.. 2021. 1. 19.
[백준 - Java] 1325번 : 효율적인 해킹 (자바는 시간초과!!!!) 문제 www.acmicpc.net/problem/1325 1번 정점으로 5번 정점은 해킹될 수 있다. 5번 정점을 시작으로 dfs를 돌면서 인접한 2번 정점에 들렸다. -> 2번 정점으로 5번 정점은 해킹될 수 있다. public static void dfs(int start, boolean[] visited, ArrayList[] list) { visited[start] = true; //System.out.print(start + " "); for (int node : list[start]) { if (!visited[node]) { computer[node]++; dfs(node, visited, list); } } } dfs 재귀 호출 전 총 N개의 크기를 가진 computer 배열에 인접한 정점.. 2021. 1. 18.
[백준 - Java] 7576번 : 토마토 문제 www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 주요 변수 설명 int[][] map : N * M의 2차원 배열을 만들어 토마토의 정보를 저장한다. int mapCount = (N*M) - 빈칸의 총 개수 : 모든 토마토가 익었나 확인을 하기 위해, 전체 공간의 개수를 파악해놓는다. int ripenedCount : 익은 토마토의 총 개수 int day : 익을 때 까지의 날짜 ArrayList ripenedTomato : 매번 익은 .. 2021. 1. 15.
[프로그래머스 - Java] [1차] 뉴스 클러스터링 (2018 KAKAO BLIND RECRUITMENT) 문제 코딩테스트 연습 - [1차] 뉴스 클러스터링 뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브 programmers.co.kr 설명 자카드 유사도 구하기는 아래의 세 가지 순서로 진행된다. 1. 다중 집합 구하기 - 집합의 원소는 대소문자 구분 X / 영문자만 가능 (특수문자, 공백, 숫자 X) - 두 글자씩 끊어서 ArrayList에 추가해 다중 집합을 구할 것 - Character.isLetter() 메소드 (char값이 문자인지 판단해 true/false 반환)를 통해 문자인지 확인 - true일 경우 다중 집합의 원소로 추가 * 아래 코드 처럼 자바 정.. 2021. 1. 15.
[프로그래머스 - Java] 길 찾기 게임 (2019 KAKAO BLIND RECRUITMENT) 문제 programmers.co.kr/learn/courses/30/lessons/42892 코딩테스트 연습 - 길 찾기 게임 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] programmers.co.kr 설명 전체 코드 import java.util.*; class Solution { public static ArrayList nodeList = new ArrayList(); public static int index = 0; public int[][] solution(int[][] nodeinfo) { // node 생성 for(int i = 0; i < nodeinfo.. 2021. 1. 12.
[프로그래머스 - Java] 오픈 채팅방 (2019 KAKAO BLIND RECRUITMENT) 문제 programmers.co.kr/learn/courses/30/lessons/42888 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr 아이디 값을 key로 HashMap을 사용해 아이디와 닉네임을 관리한다. 나는 LinkedList로 했는데 ArrayList든 뭐든 인덱스 없이 저장할 수 있는 자료구조를 이용해 들어오고, 나오고를 저장할 result를 만들어준다. Enter라면 아이디와 닉네임을 저장하고 result에 add Change라면 단순히 닉네임만 업데이트 Exit이라면 result에만 add.. 2021. 1. 11.
[프로그래머스 - Java] 후보키 (2019 KAKAO BLIND RECRUITMENT) 문제 programmers.co.kr/learn/courses/30/lessons/42890 코딩테스트 연습 - 후보키 [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]] 2 programmers.co.kr 1. 모든 후보키 조합 구하기 조합을 구하는 알고리즘을 이용해 모든 후보키가 될 수 있는 조합을 구했다. (백트래킹 이용해 구현함) 조합 포스팅 [Java] 조합 Combination 구해진 후보키 조합은 문자열 형태로 구해진다. 예를 들어 4개의 .. 2021. 1. 11.
[프로그래머스 - Java] 기둥과 보 설치 (2020 KAKAO BLIND RECRUITMENT) 문제 programmers.co.kr/learn/courses/30/lessons/60061 코딩테스트 연습 - 기둥과 보 설치 5 [[1,0,0,1],[1,1,1,1],[2,1,0,1],[2,2,1,1],[5,0,0,1],[5,1,0,1],[4,2,1,1],[3,2,1,1]] [[1,0,0],[1,1,1],[2,1,0],[2,2,1],[3,2,1],[4,2,1],[5,0,0],[5,1,0]] 5 [[0,0,0,1],[2,0,0,1],[4,0,0,1],[0,1,1,1],[1,1,1,1],[2,1,1,1],[3,1,1,1],[2,0,0,0],[1,1,1,0],[2,2,0,1]] [[ programmers.co.kr 1. 기둥과 보를 저장하기 기둥과 보가 같은 (x, y) 좌표에 있을 수 있기에, 둘을 나누.. 2021. 1. 11.
[백준 - Java] 15681번 : 트리와 쿼리 문제 www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 설명 * 입력받을 때 Scanner로 받으면 시간 초과에 메모리 초과까지 난다;;; 꼭 BufferedReader와 같은 Buffer로 입력받아야 함!! * 이건 설명할게 따로 없다... 트리와 쿼리 문제 스크롤하다 보면 힌트라는 카테고리에서 이 문제를 그래프, 트리, 서브 트리 등 아주 자세히 설명해준다... 진짜 나도 어떻게 풀어야 할지 막.. 2021. 1. 6.
[백준 - Java] 15900번 : 나무 탈출 틀렸습니다!!! 나는 결국 다른 사람들의 풀이를 보고 문제를 해결했다ㅠㅠ 처음에 A가 고르고, B가 고르고 모든 경우를 다 따지고, 부모 노드로 바꿨다가. 노드를 삭제했다가 별별일을 다 하다 너무 시간이 오래 걸려서 포기함... 답을 봤더니 너무 허망했음ㅋㅋㅋㅋ역시 사람은 머리를 잘 굴려야함! 풀이는 아래에!! * 아 참 Scanner로 입력받으면 시간 초과!!!! 문제 www.acmicpc.net/problem/15900 15900번: 나무 탈출 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게 www.acmicpc.net 설명 게임은 리프 노드부터 시작되고, 리.. 2021. 1. 5.
반응형

티스토리툴바