Algorithm

[백준 1103] 게임 (C++)

1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 백트래킹과 DP가 합쳐진 문제? 중요 - 방문처리 방문한 곳에 도달했다면 사이클을 이루므로 무한번 이동가능. -1 출력 후 exit()으로 프로그램 종료 나머지는 현재 위치좌표를 가지는 dp배열을 통해 최대 이동 횟수를 재귀적으로 메모이제이션 한다. 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 ..

[백준12762 ] 롤러코스터 (C++)

12762번: 롤러코스터 첫째 줄에 개조하고자 하는 구간의 길이 \(N\)이 주어진다. 구간의 길이는 1,000을 넘지 않는 자연수이다. 둘째 줄에 구간 내에 있는 각 기둥들의 높이가 주어진다. 기둥의 높이는 10,000 이하의 자연 www.acmicpc.net 숫자가 감소하다가 증가하는 경우, 숫자가 계속 증가하는 경우, 숫자가 계속 감소하는경우의 수를 모두 구하면 된다. 여기서 숫자가 계속 증가하는 경우의 수를 구하는 이유는 아래와 같다 1. 기둥을 마음대로 삭제할 수 있다. 2. "그리고 롤러코스터의 진행 방향은 공사가 끝난 후 결정된다." => 앞, 뒤 부터 시작해서 감소하는 수열만 찾으면 된다. 구간의 시작부분이 양 끝 모두 될 수 있다. 따라서 특정 인덱스를 시작으로하는 감소하는 수열의 길이를..

[백준 1234] 크리스마스 트리 (C++)

1234번: 크리스마스 트리 첫째 줄에 트리의 크기 N, 빨강의 개수, 초록의 개수, 파랑의 개수가 주어진다. N은 10보다 작거나 같다. 빨강, 초록, 파랑의 개수는 0보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 레벨이 최대 10이므로 1 + ... + 10 = 55 이다. 따라서 한가지 색을 최대 55개까지만 사용할 수 있다. -> 배열의 크기가 [11][60][60][60]인 이유 cache 배열은 [현재 층][빨간색을 사용한 횟수][초록색을 사용한 횟수][파랑색을 사용한 횟수] = 경우의 수 기저조건은 재귀를 돌면서 현재 층이 N을 넘기면 해당 경우가 있다는 뜻으로 1을 반환하도록 했다. 각 층마다 사용된 색의 개수가 모두 같아야 하고, 각 층마다 색깔에 따라서 순열이..

[백준 2479] 경로찾기 (C++)

2479번: 경로 찾기 길이가 같은 두 개의 이진수 코드 A와 B가 있다고 하자. 이 두 코드 사이의 해밍 거리는 A와 B의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 수이다. 예를 들 www.acmicpc.net 해밍 거리가 1인 경우만 서로 이동이 가능하다. 따라서 모든 정점을 서로 1:1로 보면서(N^2) 해밍거리를 확인하고 1인 경우에 정점을 연결시켜주는 작업을 가장 먼저 한다. 두 번째로 가장 짧은 해밍 경로를 찾아야 하므로 A부터 B까지 최단경로를 구하는 다익스트라 알고리즘을 수행해 준다. 다익스트라 도중 우선순위 큐에 원소를 넣을 때, 큐에 들어가는 정점에 도달하기 직전의 정점이 현재 정점이므로 parent[next] = now 를 통해 이전 정점을 기록해..

[백준 16437] 양 구출 작전 (C++)

16437번: 양 구출 작전 2, 3, 5번에 사는 모든 양들은 1번 섬으로 갈 수 있지만 7번 섬에 사는 양들은 1번 섬으로 가기 위하여 6번 섬을 거쳐야 하는데 6번 섬에 사는 늑대들의 수가 7번 섬에 사는 양들의 수보다 많으므로 www.acmicpc.net 각 마을에 있는 늑대와 양의 수를 island 배열에 저장한다. 이때 늑대의 수는 음수로 저장하도록 했다. 양이 1번 섬으로 들어오는 최대 수를 알아야 한다. 따라서 1번 섬에서 시작해서 양을 데려온다는 생각으로 dfs를 수행했다. 1. 만약 현재 섬이 리프 노드이고 양이 살고 있다면 양을 데리고 올 수 있다. return 양의 수 만약 현재 섬이 리프 노드이고 늑대가 살고 있다면 0을 리턴한다. 2. 현재 섬에 살고있는 양 또는 늑대(음수)를 ..

[백준 15591] MooTube(Silver) (C++)

15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net N과 Q가 각각 최대 5000이므로 주어지는 쿼리마다 매번 bfs를 수행해도 시간에 늦지 않을 것이라고 생각했다. 시작점에서 bfs를 수행하면서 다음 영상과의 유사도(USADO)가 K보다 작은 경우 다음 영상은 추천되지 않는다고 생각하면 편하다. K보다 큰 경우에만 다음 영상의 번호를 큐에 넣으면서 bfs를 수행하고 그 수를 카운팅을 해준다면 매 쿼리마다 답을 구할 수 있게 된다. 1 2 3 4 5 6 7 8 9..

[백준 3980] 선발 명단 (C++)

3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 한 줄에 하나씩 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net 백트래킹 인원수가 최대 11명이고 자신이 원하는 포지션 최대 5개 중 하나에 들어갈 수 있으므로 O(5^11 - @)의 시간복잡도가 가능하다고 생각한다. 포지션은 11개인데 11명의 선수가 원하는 포지션을 5개씩 가지고 있다면 중복되는 경우가 아주 많아서 백트래킹에서 걸러지게된다. 따라서 절대 O(5^11) 시간은 나올 수 없고 그보다 훨씬 적은 시간이 들 것으로 예상했다. 백트킹을 수행하면서 현재 선수가 원하는 포지션 중 하나에 들어갈 수 있다면 현재 선수의 스탯을 더하고 다음 선수로 넘..

[백준 1339] 단어수학 (C++)

1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 브루트 포스 - 순열 (연습) 7달 전에 그리디를 사용해서 풀었었는데 이번엔 백트래킹 완전탐색을 이용해서 풀었다. 모든 단어를 입력받고 단어에 사용된 알파벳(최대 10개)를 중복 없이 걸러내기 위해서 중복을 허용하지 않는 자료구조인 set을 사용했다. 10개의 알파벳에 9~0까지의 숫자를 매칭해주고 모두 매칭이 된 경우 (cnt == 알파벳의 개수) 최대 10개의 단어를 매핑테이블(table[27])을 이용해 모두 숫자로 바꾸고 각각을 더해주었다. 매칭은 ..

[백준 2529] 부등호 (C++)

2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net 브루트 포스 - 순열 (연습) 어제 푼 카카오 2021 하반기 공채 1차 코테 4번문제 (양궁) 과 비슷한 문제이다. 정렬이 잘못되었다고 하는데 나는 아직도 어디가 틀렸는지 감이 오지않는다. 경험삼아 쳐본 코테 덕분에 나 자신을 돌아보고 실력이 얼마나 부족한지 다시 생각해보는 계기가 되었다. 지금까지 하고싶은 알고리즘 공부, 재밌어보이는 문제, 내가 자신있는 파트의 문제 위주로 풀었고 자기 만족을 위해서 알고리즘 문제를 풀어왔다면, 남은 1년은 시험 공부하는 ..

[백준 1525] 퍼즐 (C++)

1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net BFS, 비트마스킹 3x3 크기의 퍼즐은 각 칸마다 0~8까지의 숫자가 들어간다는 것을 이용해서 하나의 숫자당 4개의 비트를 사용. long long 타입에서 총 36개의 비트를 사용해 3x3 퍼즐의 정보를 저장하도록 했다. 위 퍼즐에서 0의 위치는 3행 3열에 있다. 따라서 32번째 비트~35번째 비트 공간이 해당 칸을 저장하게된다. 그리고 특정 칸에 위치한 숫자를 알아내기 위한 mask로서 Checker배열을 설정했다. BFS를 수행하면서 매번 0의 위치를 찾아준다. 0의 위치를 찾았다면 0이 갈 수 있는 4방향을 모두 탐색해본다. 범..