본문 바로가기

알고리즘

 (179)
[2019 KAKAO BLIND RECRUITMENT] 무지의 먹방 라이브(시행착오 포함) https://www.welcomekakao.com/learn/courses/30/lessons/42891 코딩테스트 연습 - 무지의 먹방 라이브 | 프로그래머스 www.welcomekakao.com 가장 까다로웠던 문제이다. 정확성은 쉽게 통과할 수 있지만, 효율성에 대해서는 통과하기가 어렵다. 또한, 정답과 유사한 아이디어를 생각한다고 해도, 자료구조를 쓰는 방식에 따라서 효율성 테스트를 통과할 수 있을지 없을지가 결정된다. 이 문제의 정확성 테스트를 통과하기 위해서는, 쉽게 매초마다 Action을 취해주면서 최종적으로 방송 중지 시간 이후에 먹어야 할 음식의 순서를 결정해주면 된다. 이 부분은 간단하게 구현할 수 있다. 하지만, 중요한 것은 효율성 테스트를 통과하기 위해서는 매초마다 Action을 ..
[2019 KAKAO BLIND RECRUITMENT] 후보키 ## 접근 1. 비트마스크를 사용해서, 모든 조합을 탐색하기 시작한다. 조합마다 HashSet 자료구조를 이용해서 유일성을 만족시키는지 검사한다. 2. 유일성을 만족한다면 최소성도 만족하는지 검사해야 하는데, 기존의 정답들을 담아두는 자료구조와 비교하여 최소성 만족 유무 확인한다. ## 해설코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 import java.util.*; import java.io.*; import java..
[2020 KAKAO BLIND RECRUITMENT] 블록 이동하기(Java, 간단한 코드, DFS? or BFS?) ## 접근 1. DFS와 BFS 중 선택, DFS는 구현이 간단하지만 최소 시간을 구할 때는 적합하지 않다. 따라서, Depth(Time)을 확인할 수 있는 BFS를 선택. 2. 방문 표시를 통해서, 재탐색이 이루어지지 않도록 한다.(시간초과방지), 로봇 상태를 구분해서 방문 표시를 해야 하므로 3차원 배열을 사용해야 한다. 2차원 배열 시에, 수직과 수평의 구분이 없어지므로 주의한다. 3. 회전을 한다는 것을, 로봇의 아래, 위, 오른쪽, 왼쪽의 2칸이 모두 비어있어야 함을 의미한다. 코드에서 구현을 확인하도록 한다. ## 유의사항 1. 변수를 사용할 때, x1, y1, x2, y2는 지양한다. 문자에 숫자를 덧붙여 쓰다보니, 실수를 할 수 있다. ## 해설코드 1 2 3 4 5 6 7 8 9 10 1..
[2020 KAKAO BLIND RECRUITMENT] 외벽 점검 (문제접근법, 해설 이해하기) ## 접근 1. 시작점을 잡고, 순열을 통해서 모든 외벽의 취약 지점들을 커버할 수 있는지 확인해야 한다. 함수는 필요한 인원수를 반환하는 것으로 정의한다. 2. 외벽은 원의 형태를 이루고 있으므로, 이동할 수 있는 거리는 시계 방향만 고려하면 된다.(반시계로 된다면 시계로도 가능) 이동할 수 있는 거리가, 외벽의 길이를 넘어가면 검사해야 하는 외벽들의 위치에 외벽의 길이만큼 더해줘야 한다. ## 해설코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 clas..
[삼성 코딩 테스트] 코딩테스트 잘보는법, 자주 실수하는 유형(C++) 이번 글에서는, 코딩 테스트에 대비하여 자주 실수하는 유형에 대해서 소개해드리겠습니다. 제 경험을 기준으로 설명드리는 것이라서, 추가하고 싶은 내용이 있으면 댓글 달아주시면 감사하겠습니다. 시험 전에 읽으시면 많이 도움이 될 '자주 실수하는 유형들'입니다. 인덱스 에러 for문 내부에서 자료 구조를 이용한 탐색을 진행할 때 발생할 수 있다. 채점 시 런타임 에러라고 발생한다. for문을 사용할 때 내부에서 사용하고 있는 인덱스와 for문에 선언한 인덱스가 같은지 꼭 파악한다. for문을 이중 중첩이상으로 사용하다보면, 실수할 수 있는 부분이다. 헤더 파일 에러 시험장에서 긴장을 하게 되면서, #include 해야 할 파일들을 적지 않아서 발생할 수 있는 문제이다. 코드를 아무리 봐도 답이 없어 보일 때,..
5644. [모의 SW 역량테스트] 무선 충전 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제접근법 1. BC의 거리 범위에 맞게 BFS 탐색을 통해서, 2차원 자료 구조에 표시해줘야 한다. 단, 2차원 자료 구조로 배열을 선택할 시에, 한 칸에 하나의 BC밖에 못들어가므로, 벡터 자료구조를 사용한다. 2. A와 B의 위치에 따라서 충전량을 더해줘야 한다. 충전량을 더할 때 케이스 분류가 필요하다. A와 B가 같은 BC에 있을 때, A와 B가 1개의 BC만 가진다면 나눠 쓰는게 맞다. ..
[15686번] 치킨 배달 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 www.acmicpc.net 문제접근법 1. 치킨 집의 위치와 가정 집의 위치를 담을 자료 구조가 필요하다. 치킨 집의 위치와 가정 집의 위치를 통해서 도시의 치..
[15683번] 감시 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다. 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 www.acmicpc.net 문제접근법 1. 카메라들의 위치와 방향을 기억할 자료 구조를 선언한다. 카메라들의 조합을 확인해가면서, 감시되는 지역을 체크하고 남은 사각..

티스토리툴바