본문 바로가기

코딩테스트

 (17)
[백준 / BOJ] 18809 Gaaaaaaaaaarden (Java) 문제 출처 : https://www.acmicpc.net/problem/18809 18809번: Gaaaaaaaaaarden 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두 www.acmicpc.net N*M크기의 정원에 빨간색 배양액 R개 초록색 배양액 G개를 뿌린다. 배양액을 뿌릴 수 있는 위치는 R+G곳 이며, 배양액을 뿌린 위치는 매 초마다 인접한 영역으로 퍼져나간다. 서로 다른 색의 배양액이 동시에 만나면 꽃이 피며, 배양액은 사라진다. 이때, 피울 수 있는 최대 꽃의 개수를 구하는 문제다 풀이 조합과 BFS로 풀..
[백준 / BOJ] 5875 오타 문제 출처 : https://www.acmicpc.net/problem/5875 5875번: 오타 올바른 괄호쌍을 좋아하는 키파는 최근에 노트북을 샀다. 그런데 키보드의 크기가 너무 작았기 때문에, 키파는 혹시 여는 괄호와 닫는 괄호를 서로 잘못 입력하지 않았는지 걱정되었다. 키 www.acmicpc.net 오타가 '최대 한번' 있는 괄호배열이 주어진다. 이 괄호배열의 괄호를 하나 조작하여 올바른 괄호 배열을 만드는 경우의 수 를 구하는 문제다. 풀이 어려웠던 문제다 누적합으로 풀었는데, 여는 괄호를 +1, 닫는괄호를 -1 이라고 하고 누적합 배열을 만들자. 예를들어, 괄호배열 ( ) 의 누적합배열은 {1, 0}, ( ( ) ) 의 누적합 배열은 {1, 2 ,1, 0}이 된다. 올바른 괄호배열이 여는괄호..
[백준 / BOJ] 20183 골목 대장 호석 - 효율성 2 (Java) 문제 출처 : https://www.acmicpc.net/problem/20183 20183번: 골목 대장 호석 - 효율성 2 첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의 www.acmicpc.net 교차로 N개 교차로를 잇는 골목 M개(단, 골목에는 통행료가 존재한다.)가 주어진다. A교차로에서 B교차로로 갈때, 이 경로의 통행료 합을 C 이하로 만드는 경로중 통행료의 최댓값을 최소로 하는 경로를 구하는 문제다 풀이 전형적인 다익스트라 알고리즘으로 풀리는 문제였다. 알고리즘은 다익스트라를 사용하면 풀리기때문에 따로 설명할게 없고, 최소힙에 ..
[백준 / BOJ] 20955 민서의 응급 수술 문제 출처 : https://www.acmicpc.net/problem/20955 20955번: 민서의 응급 수술 민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서 www.acmicpc.net N개의 뉴런(노드) 와 M개의 시냅스(간선)가 주어진다. 이때, M개의 시냅스를 적절히 끊거나 연결해서 N개의 뉴런을 하나의 '트리'구조로 만들려고한다. 끊거나 연결하는 연산횟수를 구하는 문제다. 풀이 트리의 정의인 '트리는 항상 N-1개의 간선으로 연결된다'를 이용하면 쉽게 풀리는 문제다. 문제 입력의 노드가 항상 전부 연결된상태로 주어지는것이 아니기 때문에, 우선 연결된 그래프..
[programmers/kakao] [3차] 압축 (Java/Trie) 문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/17684 코딩테스트 연습 - [3차] 압축 TOBEORNOTTOBEORTOBEORNOT [20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34] programmers.co.kr 알파벳 'A' - 'Z'로 이루어진 사전과 문자열 msg가 주어진다. 이 msg의 문자중 사전과 최장 일치하는 문자를 찾고, 문자열이 일치하지않는다면, 사전에 추가하며, 일치하는 문자열의 Index(색인 번호)를 출력하는 문제다. 풀이 우선 이 문제에서 msg의 길이는 최대 1,000이다. 완전탐색으로 구현할 경우, 최악의 경우는 (아마)다음과 같을것 이다. msg : ..
[prgrammers / kakao] 외벽 점검 (Java) 문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/60062 코딩테스트 연습 - 외벽 점검 레스토랑을 운영하고 있는 "스카피"는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하 programmers.co.kr 원형으로 되어있는 벽에 취약지점이 있다. "스카피"는 원형으로 되어있는 벽의 취약지점에 친구들을 투입해서, 취약지점을 수리하려고 한다. (단, 친구들은 각자 지정된 거리만 이동할 수 있다.) 이때, 친구들을 최소몇명 투입해야 외벽을 모두 수리할 수 있는지 찾는 문제다. 풀이 백 트래킹에 그리디로 푸는 문제다. weak의 길이가 최대 15, dist..
[programmers / kakao] 무지의 먹방 라이브 (Java) 문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42891?language=java# 코딩테스트 연습 - 무지의 먹방 라이브 programmers.co.kr 각 음식을 먹는데 필요한 시간이 있는 foodTimes[] 배열이 주어진다. 항상 하나의 음식을 1초 먹은후, 다음 음식을 먹어야 하며, 음식은 1초동안 1만큼 먹을 수 있다. (단, 음식의 양foodTimes[] 배열의 원소가 0일 경우에는 음식을 다 먹은것 이라고 판단하고 다음 음식을 먹는다.) 이때, K번째 먹을 음식을 찾는 문제다. (정확히는 K초 후 네트워크 장애가 일어나고, 네트워크 장애가 해결된 후, 먹을 음식의 idx를 출력하는것 인데, 결국 K번째 먹을 음식을 물어보는거랑 똑같..
[programmers/kakao] [3차] 자동완성 (Java) 문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/17685?language=java 코딩테스트 연습 - [3차] 자동완성 자동완성 포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g programmers.co.kr 검색어 자동완성 기능을 만들고, 모든 문자를 찾기위해서 최소 몇번 타이핑해야하는지 찾는 문제다. 풀이 전형적인 Trie 문제였다 모든 단어의 길이를 합쳤을때 최대 1,000,000길이가 나오니 Trie 구조를 만드는데, 1,000,000번 반복하며, 모든 단어의 길이의 합이 최대 1,000,000 이므로 ..

티스토리툴바