관찰과 질문, 그리고 데이터

https://programmers.co.kr/learn/courses/30/lessons/60060 코딩테스트 연습 - 가사 검색 | 프로그래머스 programmers.co.kr 트라이 자료구조를 안 쓰고 푸는 법 / 트라이 사용해서 푸는 법 두 가지 다 시도해 봤다. 트라이를 안 쓰는 경우는 python string의 startswith, endswith 방법을 사용해서 풀 수 있지만, 효율성에서 통과를 못 한다. 트라이를 사용할 경우 이 문제에서 가장 어려웠던 건 '문자열 개수'를 반영하는 것이었다. fro??일 경우 fro로 시작하면서 length가 5인, fro???는 length가 6인 걸 반환해야 하는데 fro까지 도착한 뒤, 아래 노드를 전부 순회하면 시간초과가 났다. 아마 노드를 순회하는..

https://programmers.co.kr/learn/courses/30/lessons/17685 코딩테스트 연습 - [3차] 자동완성 | 프로그래머스 자동완성 포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g 만 입력해도 go를 추천해주므로 o를 입력할 필요가 없어진다! 단, 학습에 사용된 단어들 중 앞부분이 같은 경우에는 어쩔 수 없이 다른 문자가 나올 때까지 입력을 해야 한다. 효과가 얼마나 좋을지 알고 싶은 라이언은 학습된 단어들을 찾을 때 몇 글자를 입력해야 하 programmers.co.kr 트라이 자료구조의 활용을 의도한 문제. 트라이 자료구조의 의미와 ..

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다. 로봇 청소기는 다음 www.acmicpc.net 삼성SW역량평가 A형 기출문제로, 엄청 어려운 문제라기보다는 신중하게 생각해서 코드를 짜야 하다보니 시간이 부족했을 법한 문제. ..

https://programmers.co.kr/learn/courses/30/lessons/12979 코딩테스트 연습 - 기지국 설치 | 프로그래머스 N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5g 기지국은 4g 기지국보다 전달 범위가 좁아, 4g 기지국을 5g 기지국으로 바꾸면 어떤 아파트에는 전파가 도달하지 않습니다. 예를 들어 11개의 아파트가 쭉 늘어서 있고, [4, 11] 번째 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 만약 이 4g programmers.co.kr N 크기가 크길래 이분탐색으로 풀어야 하나 고민했지만, 문제를 푸는 데..

https://programmers.co.kr/learn/courses/30/lessons/42890 코딩테스트 연습 - 후보키 | 프로그래머스 [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]] 2 programmers.co.kr 데이터베이스의 Key 설명이 복잡하게 느껴질 수 있지만, 결국에는 '모든 row를 unique하게 식별할 수 있는 조합을 찾는다'가 된다. key의 조합을 하나하나 만들고, 해당 key가 table row의 개수를 동일하게 ..

https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 | 프로그래머스 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr Greedy 알고리즘 중 하나로, 그래프의 정점을 최소 비용으로 연결하는 알고리즘인 '크루스칼 알고리즘' 문제유형이다.

https://programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 | 프로그래머스 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr 프로그래머스 Level 4에 해당하지만, 단순 BFS로 충분히 해결할 수 있는 유형이다. BFS의 전형적인 문제형태. BFS로 맵을 순회하다가 목표지점인 오른쪽 하단에 도착하면 그곳까지 도달하는 데 걸린 횟수를 count하면 된다.

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. www.acmicpc.net 연구소 3과 접근방법은 동일하다. combinations을 사용할 대상이 '벽 3개'로 바뀐 것일 뿐. BFS에서의 특이점이라면, BFS에..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 www.acmicpc.net 삼성SW역량테스트 기출문제. Brute Force + BFS 형태. 치킨집 중에 M개를 고르는 형태는 '연구소 3' 문제와 마찬가지로..

https://programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 | 프로그래머스 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr 가중치가 들어간 그래프에서, 조건을 충족하는 bfs를 구현하는 문제.