본문 바로가기

알고리즘

 (117)
[백준] 18223 민준이와마산그리고건우 [JAVA] 문제 링크 : https://www.acmicpc.net/problem/18223 18223번: 민준이와 마산 그리고 건우 입력의 첫 번째 줄에 정점의 개수 V와 간선의 개수 E, 그리고 건우가 위치한 정점 P가 주어진다. (2 ≤ V ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P ≤ V) 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보 www.acmicpc.net 민준이가 최단 경로로 갈 때, 그 경로에 건우가 있다면 SAVE HIM을 출력하는 문제다. 최단 경로이므로 다익스트라를 활용할 수 있을 것이라 생각했다. 문제에서 최단 경로가 여러개이고 그 경로들 중에 건우를 구할 수 있을 때, 민준이는 건우를 구하는 경로를 택한다 하였다. 따라서 X->Y로의 거리가 X->Z->Y의 거리가 같은 경..
[백준] 1613 역사 [JAVA] 문제링크 : https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 문제 분류가 플로이드 워셜 알고리즘이란 것을 알고서 풀이를 시작한 문제다. 그러나 어떻게 플로이드 워셜로 해결되는지 파악이 안됐었다. 그러다가 최단 거리를 어떻게 갱신하는지 생각해봤다. 플로이드 워셜 알고리즘은 어떤 위치 x가 영향력을 끼치는(x를 지나가면 최단거리가 갱신되는) 모든 a->x->b(1 b OR a < x < b를 판단 가능하면 갱신해 나간다. 플로이드 워셜 알고..
[백준] 11562 백양로 브레이크 [JAVA] 문제링크 : https://www.acmicpc.net/problem/11562 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 플로이드 워셜 알고리즘에 대해 이해하고 있어야한다. A 와 B 사이의 간선이 양방향일 경우 거리는 0이며, A->B로 단방향일 경우 A->B의 거리는 0, B->A의 거리는 1이다. X -> Y로 갈 때 최소의 거리(단방향 도로를 양방향으로 바꾸는 비용)를 최대 3만번 구해야 한다. 건물의 수는 최대 250개 이므로 플로이드 워셜 알고리즘을 활용해서 최소 거리를 미리 구해놓고 해결했..
[프로그래머스] N으로 표현 [JAVA] 문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 모든 경우의 수를 리스트에 담아서 계속 결과를 이어갔다. 중복된 결과가 리스트에 담겨서 구현했을 시 시간초과를 예상했지만 시간초과는 나지 않았다. Set 으로 구현하는게 맞는 것 같다. 밑에는 수정 전 코드 => 리스트를 Set으로 바꿔주어야한다. 문제 분류인 dp하고는 맞지 않는것 같다 import java.util.*; class Solution { public static ArrayList adj[]; public static int solution(int N, int number) { adj = new ArrayList[..
[프로그래머스] kakao 2019 겨울 인턴십 / 호텔 방 배정 [JAVA] 문제링크 : programmers.co.kr/learn/courses/30/lessons/64063 코딩테스트 연습 - 호텔 방 배정 programmers.co.kr 기본적인 생각으로 자신이 원하는 방이 없다면 그 방 번호보다 큰 것중 비어있는 방을 탐색하면서 배정하는 방식을 생각할 수 있다. k는 1 이상 10^12 이하인 자연수기 때문에 단순하게 배열로 해당 인덱스가 방이 배정 됐는지 아닌지 판단이 힘들다. 그래서 해시맵을 사용했다. 위 과정에서 문제점은 비어있는 방을 순차탐색 하는건 room_number가 20만이기 때문에 모든 값이 1일 때 약 20만*(20만-1)/2의 시간이 걸린다. 따라서 다른 방법이 필요한데 union find(Disjoint Set)를 사용했다. 어떤 사람이 1번방을 배정..
[프로그래머스] kakao 2019 겨울 인턴십 크레인 인형뽑기 게임 [JAVA] 문제링크 : programmers.co.kr/learn/courses/30/lessons/64061 코딩테스트 연습 - 크레인 인형뽑기 게임 [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]] [1,5,3,5,1,2,1,4] 4 programmers.co.kr 명령어대로 인형을 뽑아서 어떤 공간에 차곡차곡 쌓다가 연속으로 2번 같은 인형이 겹치면 점수를 획득하는 게임이다. 위 한줄을 읽으니 당연 스택으로 구현하면 편해보인다. 그렇게 생각하니 인형이 있는 N*N 공간도 스택으로 구현하는 방법이 생각나서 그렇게 했다. 맵의 최대 열이 30이므로 한 열마다 스택 하나씩 해서 30개를 만들면 될 것 같다. 맵을 구성 후에는 명렁어대로 moves[i]열의..
[백준] 21609번 상어 중학교 [C++] 문제링크 : www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 친구가 빨리풀기 대결하자고 해서 언어를 맞추기위해 오랜만에 C++로 풀었다. 최근 삼성 역량테스트 문제다. 그래서 구현이 조금 까다롭지만 시키는대로 잘 하면 된다. 이런 문제를 많이 풀어보는 게 삼성 역량테스트에서 중요한 것 같다. 메인함수부터 순서대로 설명하면 이렇다. 조건에 해당하는 블럭이 있을 경우(loop==true) 반복한다. 블럭 묶음의 갯수를 파악하기 위해 dfs함수를 호출했다. 0..
[프로그래머스] 2021 dev-matching 다단계 칫솔 판매 [JAVA] 문제링크 : programmers.co.kr/learn/courses/30/lessons/77486 코딩테스트 연습 - 다단계 칫솔 판매 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, programmers.co.kr (전처리) enroll 순서대로 해당 이름을 1~N까지 고유 번호를 HashMap에 저장했다. 또, referral 배열 정보로 해당 유저의 부모의 번호를 par 배열에 저장했다. seller 정보와 amount를 가지고 최초 이득 유저와 돈을 가지고서 다단계 과정을 수행했다. while문이 그것이며, 해당 코인을 본인에게 더하고 부모에게 넘겨주는 식이다. ..

티스토리툴바