본문 바로가기

알고리즘(자바)

[프로그래머스] (2018년)KAKAO BLIND RECRUITMENT 오픈채팅방 https://programmers.co.kr/learn/courses/30/lessons/42888 코딩테스트 연습 - 오픈채팅방 | 프로그래머스 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오픈 채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고, 나가는 것을 지켜볼 수 있는 관리자창을 만들기로 했다. 채팅방에 누군가 들어오면 다음 메시지가 출력된다. [닉네임]님이 들어왔습니다. 채팅방에서 누군가 나가면 다음 메시지가 출력된다. [닉네임]님이 나갔습니다. 채팅 programmers.co.kr 해시 알고리즘을 이용해 풀면 쉽게 풀리는 것 같다. 주어진 입력 reco.. 더보기
[프로그래머스] 해시알고리즘 완주하지 못한 선수 https://programmers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수 | 프로그래머스 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 partic programmers.co.kr 포인트는 HashMap을 사용해 복잡도를 O(n)을 넘으면 안되.. 더보기
[백준]BFS 알고리즘 과 토마토 문제 BFS(Breath-First Search, 너비 우선 탐색) 너비 우선 탐색은 그래프의 모든 정점을 방문하는 알고리즘 중 하나입니다. 현재 정점과 인접한 정점들을 하나씩 검사해 아직 방문 하지 않은 정점을 자료구조 큐에 넣습니다. 그리고 검사가 끝나면 큐의 가장 앞에 있는 점을 방문해 위의 과정을 진행하고 Pop합니다. 이 과정을 큐가 비어 있을 때까지 반복 하는 것이 BFS입니다. 저는 BFS 문제로 백준의 토마토 문제를 풀어 보겠습니다. https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄.. 더보기
순열 Permutation 알고리즘 {a, b, c, d} 로 순열을 만드는 것은 4! = 24개 {a, b, c, d}의 모든 순열 = 첫 원소가 a이면서 {b, c, d}의 모든 순열 + 첫 원소가 b이면서 {a, c, d}의 모든 순열 + 첫 원소가 c이면서 {a, b, d}의 모든 순열 + 첫 원소가 d이면서 {a, b, c}의 모든 순열 위의 식을 보면 함수를 recursive 하게 짤수 있다는 것을 알수 있습니다. 첫 원소가 a이면서 {b, c, d}의 모든 순열 = 앞에 고정된 원소 a, b 이면서 {c, d}의 모든 순열 + 앞에 고정된 원소 a, c 이면서 {b, d}의 모든 순열 + 앞에 고정된 원소 a, d 이면서 {b, c}의 모든 순열 여기서 앞에 고정된 원소 들을 prefix string 전체 원소를 set S라고.. 더보기
소수 인지 체크하는 함수 와 최대공약수, 최소 공배수 구하기 소수 인지 체크 어떤수가 소수인지 체크 하기 위해서 2부터 검사값까지 모두 나누어 보면서 나누어 떨어지는 수가 있는지 찾아보면 되지만 2부터 루트(검사값)까지만 모두 나누어 봐도 알수 있다. public static boolean check(int n) { if(n==1) return false; for(int i=2;ib), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. int r=1; val1 은 큰수 val2 는 작은수 while(r>0){ r = val1 % val2; val1 = val2; val2 = r; } L.. 더보기
알고리즘 언어 선택 오랜 기간(2~3년?)을 C++로 알고리즘을 공부해 왔다. 처음 공부한 언어가 C이고 자료구조를 C++로 배웠고 주변 사람도 C++로 알고리즘을 공부하라고 그랬다. 그리고 현재 웹개발 취업에 도전하고 있는 시점에서 웹개발을 하는데 주로 쓰는 언어가 java인데 c++로 공부하는 것이 도움이 될 까라는 생각과 엔테크 인턴 기술면접에서 알고리즘을 풀때 이클립스를 쓰게 했고 물론 이클립스로도 c++을 할 수 있고 나는 c++로 풀었다. 하지만 면접관이 c++로 알고리즘을 푸는 이유가 있나요 라고 질문을 받았을 때 웹 개발자니까 java로 풀기를 선호하는 건가 하는 느낌을 받았고 cafa24 코딩테스트에서는 java로만 시험을 볼 수 있었다. 그래서 cafa24 시험 보기 전부터 java로 알고리즘을 공부 했는.. 더보기
알고리즘 백준 2178번 미로탐색 문제 dfs인줄 알고 풀었는데 깊이 탐색 후에 다른 경로를 탐색 시작 할때 이미 지나간 경로를 방문한것으로 하기 때문에 다른 경로 탐색은 힘들어진다. 최단 경로는 bfs가 거리 계산이 보장되고 속도가 빠르다고 한다. 더보기

티스토리툴바