본문 바로가기

Algorithm/Programmers37

[고득점 Kit (DFS/BFS)] 단어 변환 (python, swift) 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 풀이 문제에서 가장 짧은 변환 과정이라고 했으므로 최단 거리를 찾기 위해 bfs를 활용했다. 큐에는 총 3가지 정보를 넣어줬다. (현재 단어, 변환 횟수, 현재 단어의 인덱스)이다. 초기에는 인덱스에 -1을 넣어줬다. 인덱스의 경우는 checked 배열에서 사용하기 위해 넣어줬다. 주어진 words의 for문을 돌면서 현재 단어에서 다음 단어로 변환을 한 적이 있는지를 체크한다. 큐를 돌면서 target 단어를 만나면 .. 2021. 10. 11.
[고득점 Kit (완전탐색)] 카펫 (swift) 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 programmers.co.kr 풀이 먼저 갈색 격자의 수에서 모서리에 있는 4개를 제거해준다. (갈색 격자의 수 - 4)는 (노란색 격자의 가로 길이 * 2) + (노란색 격자의 세로 길이 * 2)가 된다. 그럼 이제 for문을 돌면서 노란색 격자의 가로 길이와 세로 길이를 구한다. 문제에서 카펫의 가로 길이가 세로 길이보다 길거나 같다고 했으므로 항상 가로 길이 > 세로 길이임을 알 수 있다. 위의 그림은 노란색 격자가 총 24개 있는 상태다. for문을 돌 때 노란색 격자 개수의 제곱.. 2021. 10. 11.
[고득점 Kit (완전 탐색)] 소수 찾기 (swift) 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 풀이 먼저 입력 받은 numbers 문자열을 Int형 배열로 만들어준다. let intArray: [Int] = numbers.map { Int(String($0)) ?? 0 } 순열을 이용해서 만들어 낼 수 있는 모든 숫자 조합을 찾은 후에 각각의 숫자를 소수인지 판별하여 셋에 저장한 후에 마지막에 셋에 있는 숫자의 개수를 카운트한다. 코드 import Foundation var res: Set = [] func isPrime(_ num: Int.. 2021. 10. 11.
[고득점 Kit (완전탐색)] 모의고사 (swift) 코딩테스트 연습 - 모의고사 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 programmers.co.kr 풀이 각각의 수포자의 정답 패턴을 배열에 담아둔다. answers 배열을 for문으로 돌면서 각각의 수포자가 정답을 맞췄는지 체크 후에 가장 많은 문제를 맞힌 사람을 체크하여 res 배열에 담아 return 해준다. 코드 import Foundation var first: [Int] = [1, 2, 3, 4, 5] var second: [Int] = [2, 1, 2, 3, 2, 4, 2, 5] var third: [Int] = [3, 3, 1, 1, 2, 2, .. 2021. 10. 11.
[고득점 Kit (DFS/BFS)] 네트워크 (swift) 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 풀이 네트워크 확인 여부를 위한 Bool형 배열을 하나 만들어준다. 만약 컴퓨터 번호에 해당하는 Bool 값이 true이면 이미 하나의 네트워크에 포함된 컴퓨터임을 의미한다. for문으로 모든 컴퓨터 번호를 체크해서 만약 해당 컴퓨터 번호가 아직 어떤 네트워크에도 속하지 않았다면 dfs 함수를 호출해서 모든 연결되어있는 컴퓨터 번호를 체크하는 과정을 거친다. dfs가 호출될때마다 네트워크 개수를 하나 증가시켜주고 최종적으로 해당 개수를 return 해주면 .. 2021. 10. 11.
[고득점 Kit (DFS/BFS)] 타켓 넘버 (swift) 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 풀이 DFS를 활용해서 해결하는 문제 입력 받은 numbers 배열의 처음부터 끝까지 돌면서 한 번은 더하고 한 번은 빼준다. 끝까지 다 계산한 값과 타겟 넘버를 비교해서 둘의 값이 같으면 경우의 수를 1 증가시킨다. 마지막에 경우의 수를 return한다. dfs(idx:len:sum:) idx : numbers 배열에서 이번에 계산해야 할 인덱스 번호 len: numbers 배열의 길이 sum: number.. 2021. 10. 11.

티스토리툴바