boj

[백준 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방향을 모두 탐색해본다. 범..

[백준 17472] 다리 만들기 2 (C++)

17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net BFS, 최소 스패닝 트리 BFS를 통해서 각 칸마다 섬의 번호를 지정해서 섬을 구분한다. 모든 섬과 섬 사이의 거리를 구한다. 서로 이어지지 않은 섬은 거리를 INF로 한다. 여기까지 사전작업을 마쳤으면 모든 섬을 연결하는 최소 거리를 구하면 된다. 모든 노드를 연결하는 최단거리를 구하는 알고리즘은 최소 스패닝 트리임을 알 수 있다. 2번 과정에서 얻은 섬 간의 거리는 양방향이었으므로 중복되는 구간은 제외하고 새로운 벡터에 넣어준다. 거리를..

[백준 1395] 스위치 (C++)

1395번: 스위치 첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O www.acmicpc.net 세그먼트 트리 오랜만의 백준 풀이다. 어저께 하루 종일 고민하면서 구현했고 방금 구현을 마무리해서 AC를 받았다. 처음엔 3653 영화 수집 문제를 풀려고 했는데 아무리 생각해도 푸는 방법이 생각이 안 나서 런하고 만난 문제가 이번 문제다. 도망쳐서 만났기 때문에 한번 더 도망칠 수가 없었다.. 전에 풀었던 구간합구하기2 문제랑 느낌이 비슷해서 레이지 세그먼트 트리로 감을 잡았다. [백준 10999] 구간 합 구하기 2 (..

[백준 15559] 내 선물을 받아줘 (C++)

15559번: 내 선물을 받아줘 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000, 1 < N×M ≤ 1,000,000) 둘째 줄부터 N개의 줄에는 구사과가 있는 곳의 지도가 주어진다. 지도에 쓰여 있는대로 이동했을 www.acmicpc.net 강한 연결 요소 임의의 칸에서 출발해서 다시 자신의 칸으로 되돌아 올 수 있으면 해당 루트의 아무 지점에 선물을 놓아도 선물을 가져갈 수 있다. 따라서 각 칸의 scc번호를 구한다. scc번호를 구하고 scc그래프를 만드는데 역방향으로 만드는게 중요하다. 하나의 SCC집합 내부에선 어떤 칸에 놓던지 선물을 가져갈 수 있는 성질을 활용하면 된다. SCC의 outdegree가 0이면 해당 SCC에서 다른 SCC로 갈 수 없다..