개발조아

문제 링크 : https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 예전에 풀었던 걸 MST로 다시 풀어봤다. 예전에는 BFS,DFS로 완탐으로 해결했었다. 이번에는 BFS, MST로 해결했다. BFS로 각 섬에 번호 매기면서 섬의 가장자리를 구한다. 이때 해당 점에서 이동하려는 점이 격자판 안에 있고 물인 경우 가장자리로 판별해서 저장했다. (x,y,방향) 이때 방향은 해당 칸으로 온 방향이다. 구한 가장자리에서 다리를 만들면..

문제 링크 : https://www.acmicpc.net/problem/2479 2479번: 경로 찾기 길이가 같은 두 개의 이진수 코드 A와 B가 있다고 하자. 이 두 코드 사이의 해밍 거리는 A와 B의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 수이다. 예를 들 www.acmicpc.net BFS로 풀이 하였다. 그냥 모든 경우 다 따져도 될 것 같다. BFS 돌면서 현재 점과 방문하지 않은 점들중 해밍 거리가 1인 것만 골라서 BFS를 진행해도 무방할 듯 하다. 30 * 1000 * 1000 = 30,000,000 이므로 다 따져도 충분하다. 그치만 나는 그냥 미리 해밍 거리가 1인걸 구하고 그 녀석들 가지고만 BFS를 수행했다. 그리고 가장 중요한것은 경로를 저..

문제 링크 : https://www.acmicpc.net/problem/1944 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 접근법이 떠오르지 않아 밑에 알고리즘 분류를 보고 해결한 문제이다. MST로 해결하였다. 출발점과 모든 열쇠점을 연결하는데 이때 가중치가 최소가 되어야한다. 그러므로 MST로 해결하면 된다. 이때 주어진 미로를 그래프로 변환해야한다. 이것은 각 지점별로 다른 지점까지 최단경로를 계산해서 만들어주면 된다. 그래서 나는 미로를 좀 수정했다. S를 1로, K..

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/72415 코딩테스트 연습 - 카드 짝 맞추기 [[1,0,0,3],[2,0,0,0],[0,0,0,2],[3,0,1,0]] 1 0 14 [[3,0,0,2],[0,0,1,0],[0,1,0,0],[2,0,0,3]] 0 1 16 programmers.co.kr 문제는 간단하보였지만 구현이 빡셌던 문제이다. 처음에는 무지성으로 다 돌리면 되지 않을가 생각했다. 방문해야하는 그림카드가 최대 6쌍이므로 12개이다. 이것으로 조합만들면 12! 이므로 되지 않을까 했는데 4억7천정도되서 시간초과 나지 않을까 해서 이방법은 접었다. 그래서 비트마스크를 활용해서 BFS로 해결했다. 비트마스크는 현재 뒤집은 카드를 기록한..

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42893 코딩테스트 연습 - 매칭 점수 매칭 점수 프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다. 평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀 programmers.co.kr HTML 파서나 정규식 안쓰고 문자열 처리로 했다. 정규식으로하면 더 쉽게 할 수 있을 것 같긴하다. 일일이 문자열을 검색해서 했기 때문에 설명도 길고 코드도 길어졌다. 근데 코드에 어려운부분이 없어서 코드를 보는게 이해가 빠를수도 있다. 우선 모든 문자를 소문자로 바꾸고 했다. html도 word도 모두 대소문자를 구별하지 않기 때문이다. 우선 딕..

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/17685 코딩테스트 연습 - [3차] 자동완성 자동완성 포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g programmers.co.kr 백준의 휴대폰 자판과 거의 비슷하다. https://westmino.tistory.com/140 [BOJ/백준] 5670 휴대폰 자판 파이썬 문제 링크 : https://www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프..

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 최소 비용으로 목적지에 도달해야하므로 다익스트라로 해결했다. 같은 방향으..

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 투포인터로 해결하였다. 우선 각 보석이 최소 하나가 나와야하므로 보석이 나온 개수를 저장한 딕셔너리를 하나 만들었다. 보석 이름을 키로, 개수를 벨류로 gem_info 딕셔너리를 만들자 다음 이제 투포인터로 정답을 구하자. left,right를 0으로 초기화 후 실행한다. 그리고 count라는 개수 변수를 사용한다. count는 해당 보석이 left, right 사이 구간에서 처음 등장했을 때 값..