반응형

문제 풀이

1. dfs를 이용하여 cards1의 첫번째 요소와 goal의 첫번째 요소가 같은 경우, cards2의 첫번째 요소와 goal의 첫번째 요소가 같은 경우에 대하여 탐색합니다.

2. cards1[2]의 첫번째 요소와 goal의 첫번째 요소가 같은 경우는 cards1[2]과 goal의 첫번째 요소를 제거한 후에 다시 dfs를 호출해줍니다.

3. goal의 모든 요소가 제거되는 경우에는 'Yes'를, cards1과 cards2의 첫번째 요소 중 어느것도 goal의 첫번째 요소와 같지 않은 경우에는 'No'를 반환합니다.

 

JS Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//https://school.programmers.co.kr/learn/courses/30/lessons/159994
 
function solution(cards1, cards2, goal) {
    return dfs(cards1, cards2, goal);
}
 
function dfs(cards1, cards2, goal){
    if ( goal.length == 0){
        return 'Yes'
    }
    if ( cards1[0] == goal[0]){
        return dfs(cards1.slice(1), cards2, goal.slice(1));
    }
    if ( cards2[0] == goal[0]){
        return dfs(cards1, cards2.slice(1), goal.slice(1));
    }
    return 'No'
};
 cs

 

문제 링크

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

반응형

'알고리즘 > 프로그래머스' 카테고리의 다른 글

[프로그래머스] 바탕화면 정리 JS  (0) 2023.03.05
[프로그래머스] 미로 탈출 JS  (1) 2023.03.05
[프로그래머스] 대충 만든 자판 JS  (0) 2023.03.01
[프로그래머스] 보석 쇼핑 Python  (0) 2022.03.05
[프로그래머스] 후보키 Python  (0) 2022.03.01
반응형

2019 카카오 개발자 겨울 인턴십 문제입니다.

문제풀이

1. 정규표현식에서 '.'은 모든 문자 1개를 의미합니다. 따라서 banned_id의 모든 '*'을 '.'으로 바꾼 후 이를 컴파일러로 사용합니다.

2. user_id의 아이디 하나 u가 banned_id의 하나 b에 해당되기 위해서는 b로 만든 컴파일러에 u가 걸리고, b와 u의 길이가 같아야합니다. 저는 정규표현식의 match를 활용하였는데, match를 활용하면 'a.b'로 만든 컴파일러에 'aabb' 또한 매칭되므로 두번째 조건이 필요합니다.

3. 2 과정을 통해 모든 b에 해당하는 u의 리스트를 만듭니다.

user_id banned_id
["frodo", "fradi", "crodo", "abc123", "frodoc"] ["fr*d*", "abc1**"]

이 예를 사용하면 3의 결과는 다음과 같습니다.

{0: ['frodo', 'fradi'], 1: ['abc123']}

여기서 key값인 숫자는 b의 index입니다.

4. 3의 결과인 dictionary를 dfs 하여 최종 결과를 만들어냅니다.

 

*말로는 설명이 잘 안되어 아래 코드에서 자세히 다시 설명하겠습니다.

Python Code

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
import re
 
def solution(user_id, banned_id):
    # 가능한 제재id
    global answer
    answer = []
    # key : banned_id의 id의 index, value : 아래의 checked
    candidate = {}
    for i, b in enumerate(banned_id):
        # re.sub를 활용하여 b의 모든 *을 .으로 변환
        checker = re.compile(re.sub('\*','.',b))
        # banned_id 중 하나인 b에 매칭되는 user_id
        checked = []
        for u in user_id:
            # match가 안되면 결과가 None으로 두번째 조건 만족x
            if len(u) == len(b) and checker.match(u):
                checked.append(u)
        candidate[i] = checked
    # candidate를 활용하여 dfs
    for x in candidate[0]:
        dfs([x],candidate,len(banned_id))
 
    return len(answer)
 
'''
selected는 list로 selected[i]는 candidate[i]의 원소 중 하나. 즉 i번째 banned_id에 매칭되는 user_id 중 하나.
n은 banned_id의 길이.
dfs의 탈출 조건은 selected에 들어있는 원소의 수가 n이 되는 것이다.
'''
def dfs(selected,candidate, n):
    # 탈출조건
    if len(selected) == n:
        global answer
        # 중복을 제거하기 위해 selected를 정렬한 후 비교
        tmp = sorted(selected)
        if tmp not in answer:
            answer.append(tmp)
        return ;
    '''
    <selected의 원소 수가 n이 아닌 경우.>
    selected의 원소 수는 다음 banned_id의 index를 의미한다.
    ex) selected에 한개가 들어있으면 banned_id[1](banned_id의 두번째 요소)에 매칭되는 user_id의 집합인 
        candidate[1]의 원소 중 하나를 selected에 넣는다.
    '''
    for x in candidate[len(selected)]:
        if x not in selected:
            dfs(selected+[x],candidate,n)
 
 cs

문제링크

 

코딩테스트 연습 - 불량 사용자

개발팀 내에서 이벤트 개발을 담당하고 있는 무지는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량

programmers.co.kr

 

반응형

'알고리즘 > 프로그래머스' 카테고리의 다른 글

[프로그래머스] 신규 아이디 추천 - Python  (0) 2021.04.03
[프로그래머스] 3진법 뒤집기 - Python  (0) 2021.02.08
프로그래머스 캐시  (0) 2020.12.01
프로그래머스 튜플  (0) 2020.11.30
프로그래머스 n진수 게임  (0) 2020.11.10
반응형

문제 풀이

dp와 dfs를 함께 사용해야하는 문제이다.

1. dp 배열에 해당 칸을 방문한 적이 없으면 -1, 있으면 해당 칸부터 (0,0)까지 갈 수 있는 현재까지 발견한 경로의 수를 담는다.

2. 위의 dp 배열과 지도를 기반으로 dfs를 진행한다.

  2-1) 이동 가능한 칸의 dp값이 -1이라면 방문한다.

  2-2) 이동 가능한 칸의 dp값이 0이라면 방문하지 않는다. 해당 칸에서는 (0,0)까지 갈 수 없다.

  2-3) 이동 가능한 칸의 dp값이 1이상이라면 현재 칸의 dp값에 이동 가능한 칸의 dp값을 더해준다. 현재 칸에서 (0,0)까지 갈 수 있는 방법의 수는, 현재 칸에서 이동할 수 있는 칸들에서부터 (0,0)까지 갈 수 있는 경로의 합이다.

 

Python Code

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
import sys
sys.setrecursionlimit(10000)
# 0: 상, 1: 좌, 2: 하, 3: 우
a = [0,-1,0,1]
b = [-1,0,1,0]
def dfs(x,y):
    if dp[y][x] == -1 : 
        dp[y][x] = 0
    if x<0 or x>n-1 or y<0 or y>m-1: return 0
    for i in range(4):
        nx = x + a[i]
        ny = y + b[i]
        if (0 <= nx <= n-1 and 0 <= ny <= m-1) and maps[ny][nx] > maps[y][x] :
            if dp[ny][nx] > 0:
                dp[y][x] += dp[ny][nx]
            # 방문한 적 없으면 dfs
            elif dp[ny][nx] == -1 :
                dp[y][x] += dfs(nx,ny)
    return dp[y][x]
        
if __name__ == '__main__':
    m,n = map(int,sys.stdin.readline().split())
    maps = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]
 
    dp = [[-1] * n for _ in range(m)]
    dp[0][0] = 1
    dfs(n-1,m-1) 
    print(dp[-1][-1])
 
 cs

Line 9 : 지도를 벗어나면 0을 반환한다.

Line 13 : 새로운 좌표가 지도를 벗어나지 않으며 이동가능하면, 새로운 좌표를 dfs하거나(Line 17, 과정 2-2) 현재 칸의 dp 값에 새로운 좌표의 dp값을 더해준다(Line 14, 과정 2-3).

 

문제 링크

 

1520번: 내리막 길

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으�

www.acmicpc.net

 

반응형

'알고리즘 > 백준' 카테고리의 다른 글

백준 11057 오르막 수 Python  (0) 2020.12.03
백준 4358 생태학  (0) 2020.10.21
백준 1152 단어의 개수  (0) 2020.08.31
백준 2884 알람 시계  (0) 2020.05.08
백준 9465 스티커  (0) 2020.04.18
반응형

문제풀이

 N개의 퀸을 하나씩 가능한 자리에 놓는 dfs 문제이다.

 1. N*N 체스판에 N개의 퀸을 놓으므로 한 열에 퀸을 하나씩 놓으면 된다.

 2. answer를 static 변수로 선언해 둔다.

 3. depth가 i 일 때, i번째 열의 퀸의 위치를 결정하며, depth를 1씩 증가시켜간다.

 3-1. i번째 열의 퀸의 위치를 결정할 때는 j<i인 j 열의 퀸들의 위치를 참고한다. i번째 퀸과 j번째 퀸의 행이 같으면 안되며 대각선에 있어도 안된다.(row_i - row_j != col_i - col_j)

 4. depth가 N이 되면 2에서 선언한 answer에 1을 더해준다.

 5. 가능한 모든 경우에 대하여 3 ~ 4 를 반복한 후 answer를 반환한다.

 

Java Code

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
class Solution {
    static int answer = 0;
    static int combi = 0;
    public int solution(int n) {
        int[] coord = new int[n];
        
        for(int i=0; i<n ; i++) {
            coord[0] = i;
            explore(coord, 1 , n);
        }
        
        return answer;
    }
    
    public void explore(int[] coord, int depth, int n) {
        if(depth==n) {
            answer+=1;
            return ;
        }
        for(int i = 0 ; i < n ; i++) {
            coord[depth] = i ;
            if(check(coord, depth)) {
                explore(coord, depth+1 , n);
            }
        }
    }
    
    public boolean check(int[] coord, int depth) {
        for(int i = 0 ; i< depth ; i++) {
            if(!checkPair(coord,i,depth)) {
                return false;
            }
        }
        return true;
    }
    public boolean checkPair(int[] coord, int i, int j) {
        if(coord[i]==coord[j]) {
            return false;
        }else if(Math.abs(i-j)==Math.abs(coord[i]-coord[j])) {
            return false;
        }else {
            return true;
        }
    }
}
 cs

Line 4 의 solution method가 main method로, 첫번째 열의 퀸의 위치를 결정한 후 dfs(explore method)를 호출한다.

Line 15 의 explore method가 dfs를 실행하는 부분으로, depth가 n이 되면 answer에 1을 더해주며, depth가 n보다 작은 경우에는 depth 열의 퀸의 위치를 결정한다. depth 열의 퀸의 가능한 모든 위치에 대하여 depth+1로 다시 explore method를 호출한다.

Line 28의 check method와 line 36의 checkPair method로 과정 3-1의 조건을 구현한다. checkPair는 두 개의 퀸의 위치를 비교하며, check에서 마지막 퀸의 위치와 이전 퀸들의 위치를 비교한다. 이전 퀸들 간의 위치는 이전 depth에서 고려했을 것이므로 다시 할 필요는 없다.

 

문제 링크

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

반응형

'알고리즘 > 프로그래머스' 카테고리의 다른 글

프로그래머스 SQL 중성화 여부 확인하기  (0) 2020.03.23
프로그래머스 Lv2 압축  (0) 2020.03.22
프로그래머스 Lv3 타일 장식물  (0) 2020.03.22
프로그래머스 Lv3 베스트앨범  (0) 2020.03.20
프로그래머스 Lv3. 야근 지수  (0) 2020.03.05

+ Recent posts

티스토리툴바