본문 바로가기

Algorithm98

2021 Kakao blind - 신규 아이디 추천(문자열 파싱) javascript, Java 풀이 https://programmers.co.kr/learn/courses/30/lessons/72410 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 programmers.co.kr - 정규표현식을 안다면 굉장히 쉽게 풀 수 있는 문제이다. 만약 모른다면 시험시에 시간낭비가 크므로 정규표현식을 익히고 가는게 좋을 것 같다. 조건 중에 알파벳 소문자, 숫자, '-' '_' '.' 만 아이디로 사용할 수 있다는 조건이 있는데 그중 소문자, 숫자, 언더바는 \w 표현식으로 검사할 수 있다. word 를 표현하며 알파벳, 숫자, _ 중의 한.. 2021. 9. 6.
BOJ 1948 - 임계영역(그래프, 위상정렬) https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net - 문제에서 2가지를 요구하는데 하나는 DAG가 주어지고 시작노드부터 끝노드까지 가야하는데 여기서 가장 긴 경로를 찾는 것, 다른 하나는 그 경로에 포함된 엣지의 갯수를 찾는 것이다. * 위상정렬 구현 방식(bfs로 구현할 때) - dfs나 스택도 가능함 1. 각 노드들의 진입 차수 계산 2. 진입 차수가 0인 노드들을 큐에 삽입 3. 큐에서 노드를 꺼내 연결된 간선을 .. 2021. 8. 20.
BOJ 12865 - 평범한 배낭(dp, knapsack) https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net - 가방에 넣는 물품의 갯수가 최대 100개여서 dfs로 풀면 넣고 안넣고의 경우의 수가 2^100 이기 때문에 O(N^2)가 아닌 다른 방식으로 풀어야한다. 이런 경우 greedy 방식이나 dp 메모이제이션 방식을 고민해볼 수 있다. 조건에서 가방의 제한무게가 10만이하로 주어졌기 때문에 d[i][j] = max(i번째 물건까지 .. 2021. 8. 19.
2020 Kakao blind 60062 - 외벽점검(완전탐색, 구현) https://programmers.co.kr/learn/courses/30/lessons/60062 코딩테스트 연습 - 외벽 점검 레스토랑을 운영하고 있는 "스카피"는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하 programmers.co.kr - 제한사항에 주어진 배열들 길이가 다 짧아서 바 로 완전탐색 로직을 생각해냈다. 다만 취약지점을 순회하는 방식을 생각해내기가 좀 어려웠던 문제이다. - weak의 길이를 2배로 늘리고 기존 weak.size()+1부터 기존의 값 + n인 값을 넣어주고 이 안에서 weak.size() 개수만큼 취약지점을 순회하게 되면 순회를 종료하는 식으로 로직을 짰다. - 친.. 2021. 8. 17.

티스토리툴바