티스토리

70825

검색하기

블로그 홈

70825

hello70825.tistory.com/m

https://github.com/70825

구독자: 39

방명록 방문하기

반응형

주요 글 목록

[BOJ 9250, C++] 문자열 판별 집합 https://www.acmicpc.net/problem/9250 9250번: 문자열 집합 판별 집합 S는 크기가 N이고, 원소가 문자열인 집합이다. Q개의 문자열이 주어졌을 때, 각 문자열의 부분 문자열이 집합 S에 있는지 판별하는 프로그램을 작성하시오. 문자열의 여러 부분 문자열 중 하 www.acmicpc.net suffix array가 남았긴한데, 대표적인 문자열 알고리즘인 KMP, Trie, Aho-Corasick을 모두 배웠다. 아호코라식은 Trie 와 KMP를 섞은 일대다 패턴매칭 알고리즘이라고 한다. 결국엔 이것도 Trie를 사용하기 때문에 눈에 익으면 입력값 제한을 확인하여 유형을 찾을만한 알고리즘이라고 생각된다. 1. 문제 풀이 시간복잡도를 계산해보면 각 문자열마다 최대 10,000이고.. 공감수 0 댓글수 0 2022. 9. 4.
[BOJ 5670, C++] 휴대폰 자판 https://www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 트라이 자료구조를 공부했는데, 다른 블로그에 나와있는 문자열 트리 그림을 확인해보면 코드 이해가 KMP보다 쉽습니다. 근데 소멸자 쓰는 건 자료구조 수업 이후에 처음이라 정신 나갈 뻔했네요. 1. 문제 풀이 문자열을 탐색한다는 내용과 문자열이 겹치면 자동으로 완성한다라는 내용을 통해 트라이 자료구조를 사용해야 한다는 것을 알 수 있습니다. 그리고 트라이 문제를 캐치할 수 있는 제일 큰 핵심은 똑같은 문.. 공감수 1 댓글수 0 2022. 8. 25.
[BOJ 4354, C++] 문자열 제곱 https://www.acmicpc.net/problem/4354 4354번: 문자열 제곱 알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다 www.acmicpc.net 이런 상황일 때 실패함수를 사용하는 것이다를 잘 보여준 문제 1. 풀이 문제를 잘 읽어보면 S = A^n으로 어떤 문자열 S는 어떤 문자열 A를 n개를 이어 붙인 것이므로 aaaaaab, abaaaaa, aabbaaaa 같은 이런 문자열들은 저 문자열 그대로 A가 되어 S = A^1이 되는 것을 알 수 있습니다. 만약 S가 A의 알파벳을 순서대로 계속 붙인 경우.. 공감수 1 댓글수 2 2022. 8. 15.
[BOJ 8394, C++] 악수 https://www.acmicpc.net/problem/8394 8394번: 악수 첫째 줄에 회의에 참석한 사람의 수 n (1 ≤ n ≤ 10,000,000)이 주어진다. www.acmicpc.net 1. 문제 증명 예시가 4만 나와있는데, n = 1 ~ 3일 때도 확인해보면 피보나치 수열의 점화식이 나옵니다. arr[i] = arr[i-1] + arr[i-2] 피보나치 수열 점화식을 증명하는 방법은 생각보다 간단합니다. 회의에 참석한 사람 N명이 있고, 이미 우리가 1명부터 N-1명일 때까지의 경우의 수를 모두 구했다고 가정해보겠습니다. 이때 N-1명일 때의 경우의 수는 dp[N-1]입니다. N번째 사람이 추가되면 경우의 수가 2가지로 나뉘게 됩니다. 1) N번째 사람이 악수를 하지 않는 경우 이 경.. 공감수 2 댓글수 0 2022. 8. 9.
[BOJ 9167, Python 3] 도발 봇 https://www.acmicpc.net/problem/9167 9167번: 도발 봇 중세 기사 시대에, 사악한 조롱에 대항하는 정신력, 즉 '멘탈'은 아주 중요한 것이었다. 킹 현우는 자신의 노예들이 약한 멘탈을 갖기를 바라지 않았다. 그래서 자신의 엄청난 코딩 능력으로 트 www.acmicpc.net 풀이 지문에 나온대로 구현을 하면 됩니다. 1) 모든 것을 딕셔너리에 저장하고 시뮬레이션 돌리기 (재귀 O) 2) taunt, sentence, ..., past-rel은 함수로 구현하고, 나머지는 딕셔너리에 저장하기 (재귀 X) 풀이는 위처럼 크게 두 가지로 나뉠 것 같구요. 저는 두 가지 방법 모두로 풀었습니다.. 2번 풀이 같은 경우엔 jinhan814님 블로그에서 보고 풀었습니다. 계속 틀렸습니.. 공감수 2 댓글수 0 2022. 5. 7.
[BOJ 2424, Python 3] 부산의 해적 https://www.acmicpc.net/problem/2424 2424번: 부산의 해적 첫째 줄에 N과 M이 주어진다. 둘째 줄부터 N개의 줄에 보물 지도가 주어진다. 각 줄은 M개의 문자로 구성되어 있는데, .은 바다이고, I는 섬이고, V는 해적의 위치이고, Y는 현재 수아의 위치이고, T www.acmicpc.net 해적이 언제 해당 지역을 볼 수 있는지 빠르게 확인하는 아이디어 때문에 난이도가 높은 것 같은데 코드양만 많지 의외로 쉽습니다. 풀이 수아가 움직일 때, 해적은 가만히 있거나, 움직이는 것을 선택할 수 있는 상태에서 해적의 움직임과 상관없이 수아가 보물을 얻을 수 있을지 구하라는 문제입니다. 해적의 움직임과 상관이 없으려면 해적은 최단시간안에 모든 지역을 볼 수 있어도 수아가 보물을.. 공감수 0 댓글수 0 2021. 10. 26.
[BOJ 23288, Python 3] 주사위 굴리기 2 https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 이번에 나온 삼성 SW 역량테스트 문제입니다. 풀이 먼저 점수를 저장할 배열을 만들어주고, 플러드 필을 이용하여 본문에 나온대로 각 칸마다 B와 C를 곱한 값을 점수 배열에 저장하면 됩니다. 이 부분은 쉬우니까 넘어가겠습니다. 문제는 주사위를 굴리는 것입니다. 이것은 전개도 그림을 사용하여 설명하겠습니다. 처음 전개도가 위와 같이 있을 때, 설명하기 쉬운 남쪽과 북쪽으로 이동하는.. 공감수 0 댓글수 0 2021. 10. 25.
[BOJ 23240, Python 3] Colorful Tower of Hanoi https://www.acmicpc.net/problem/23240 23240번: Colorful Tower of Hanoi 입력은 표준입력을 사용한다. 첫 번째 줄에는 정수 $m$ ($1 \le m \le 25$)이 주어진다. 여기서, $m$은 가장 큰 디스크의 지름을 나타낸다. 이어지는 $m$ 줄에서, $i$ ($1 \le i \le m$) 번째 줄에는 하나의 영 www.acmicpc.net ICPC 2021 예선전에 나온 문제이다. 내가 맡아서 풀은 문제인데 대회 당시 분명 풀이가 맞지만 다른 예외사항을 찾지 못한 것 같아서 맞왜틀이 나와 결국 풀지 못한채로 끝났다. 지금 다시 풀어보니까 예외 사항 하나를 찾아서 풀었음 대회에서 풀었으면 등수가 거의 (현재 등수) / 2 수준으로 뛰어 올랐을텐데 참.. 공감수 1 댓글수 0 2021. 10. 13.
[BOJ 23033, Python 3] 집에 빨리 가고 싶어! https://www.acmicpc.net/problem/23033 23033번: 집에 빨리 가고 싶어! 첫째 줄에 역의 수 N(2 ≤ N ≤ 20,000)과 노선 M개(1 ≤ M ≤ 300,000)가 주어진다. 둘째 줄 부터 M개의 줄에 걸쳐서 4개의 정수 A, B, T, W가 주어지고 A역에서 B역으로 가는 단방향 노선이 존재하며, 소요 www.acmicpc.net 풀이 최단 시간을 구해야 하는데, A역에서 B역으로 가는데 걸리는 시간이 T이므로 다익스트라 알고리즘을 생각해볼 수 있습니다. 그리고 새로운 열차를 기다려서 타는 방법은 현재 시간이 W의 배수이면 그대로 현재 시간을 우선순위 큐에 넣어주고, 현재 시간이 W의 배수가 아니라면 (W - (현재 시간) % W)만큼 시간을 추가하여 움직이게 해주.. 공감수 0 댓글수 0 2021. 10. 5.
[BOJ 23034, Python 3] 조별과제 멈춰! https://www.acmicpc.net/problem/23034 23034번: 조별과제 멈춰! 교수님이 시험 기간에 조별 과제를 준비하셨다...! 가톨릭대학교의 조교 아리는 N명의 학생을 2개의 조로 구성하여 과제 공지를 하려 한다. 이때, 구성된 각 조의 인원은 1명 이상이어야 한다. 각 www.acmicpc.net 풀이 일단 1개의 조로 구성되어 있으면 학생들이 연락하며 소요되는 비용의 총합은 MST로 구할 수 있습니다. 하지만 문제는 2개의 조이기 때문에 시작점의 비용이 0인 곳이 두 곳이 존재합니다. 이런 그래프가 있다고 해봅시다. 여기서 MST를 빨간색으로 칠해보면 아래와 같이 나옵니다. 노란색을 팀장으로 해서 정점 두 곳을 노란색으로 칠하겠습니다. 이렇게 팀장이 있을 때, 답은 (1 + 2.. 공감수 0 댓글수 0 2021. 10. 5.
[BOJ 20157, Python 3] 화살을 쏘자! https://www.acmicpc.net/problem/20157 20157번: 화살을 쏘자! 호준이는 요즘 활 쏘기에 푹 빠져 있다. 열심히 활 쏘기를 연습하던 호준이는 쏠 때 마다 10점이 나오는 경지에 이르렀다. 이렇다 보니 한 방향으로 있는 과녁에 쏘는 것에 실증을 느낀 호준이는 www.acmicpc.net 풀이 좌표평면에서 한 방향으로 화살을 쏜다는 것은 기울기가 설정되어 있다는 뜻입니다. 그래서 제 1사분면부터 제 4사분면까지 defaultdict를 만들어주고, 각 좌표의 최대공약수를 통해 기울기를 구해주고 조건에 맞는 사분면에 넣어주면 됩니다. x = 0 혹은 y = 0일 때는 따로 변수를 둬서 구해주고, 여기에 있는 값들중 최댓값을 구해주면 됩니다. 코드 1 2 3 4 5 6 7 8 9 .. 공감수 0 댓글수 0 2021. 10. 4.
[BOJ 20158, Python 3] 사장님 달려가고 있습니다 https://www.acmicpc.net/problem/20158 20158번: 사장님 달려가고 있습니다 (1,1)에서 (1,2)로 이동한다. 다시 한 번 오른쪽으로 이동할 때 (1,2)에서 (1,4)로 1초안에 달려갈 수 있다. (1,3)에서 통제 시작 시간이 2초지만 현재 2초가 되지 않았기 때문에 이동할 수 있고 (1,4)에 www.acmicpc.net 풀이 지문을 읽어보면 BFS 알고리즘인 것을 알 수 있지만, 지문 내용이 구현하기가 참 까다롭습니다. 주의 할 점 가속도 같은 방향으로 달릴 경우 가속도가 붙는데, 속도 조절이 불가능함 방향 전환을 해야 1초에 1칸씩 달릴 수 있게 됨 통제 구역 가속도가 붙은 채로 통제 구역을 이동하면 [도중에 지나가는 통제 구역의 통제 시간] > [움직이기 시작.. 공감수 0 댓글수 0 2021. 10. 4.
[BOJ 20159, Python 3] 동작 그만. 밑장 빼기냐? https://www.acmicpc.net/problem/20159 20159번: 동작 그만. 밑장 빼기냐? 카드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 단, N은 짝수이다. 둘째 줄에 카드의 윗장부터 밑장까지 카드의 값 X (1 ≤ X ≤ 10,000)이 정수로 주어진다. www.acmicpc.net 대사만 들어봤지 밑장 빼기가 정확히 뭔지 몰라서 검색하다가 맨 윗장 다음장이 밑장으로 알고 풀었다가 계속 틀려버림 풀이 카드를 분배 할 때 밑장 빼기를 하면 맨 아래에 있는 카드를 줄 수 있다고 합니다. 그리고 카드를 분배한 사람(정훈이)부터 받을 수 있으니, 밑장 빼기를 하지 않으면 홀수번째로 나눠주는 카드는 정훈이가 가지고, 짝수번째로 나눠주는 카드는 상대방이 가져가는 것을 통해 짝수,.. 공감수 0 댓글수 0 2021. 10. 4.
[BOJ 20160, Python 3] 야구르트 아줌마 야구르트 주세요 https://www.acmicpc.net/problem/20160 20160번: 야쿠르트 아줌마 야쿠르트 주세요 첫 줄에는 정점의 개수 V(1 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 100,000)가 정수로 주어진다. 그 다음 E 줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u 와 v(1 ≤ www.acmicpc.net 풀이 문제를 보면 모든 정점에서 다익스트라 알고리즘을 돌려야할 것 같지만, 야구르트 아줌마가 첫번째 지점을 제외한 야구르트를 파는 나머지 9개 지점의 정점을 다익스트라로 돌리고, 내가 시작점에서 움직이는 다익스트라를 돌려 총 10번 다익스트라를 돌리면 됩니다. 혹은 야구르트 아줌마 정점 9개를 돌리면서 내가 시작점에서 움직이.. 공감수 0 댓글수 0 2021. 10. 4.
[BOJ 18128, C++] 치삼이의 징검다리 건너기 https://www.acmicpc.net/problem/18128 18128번: 치삼이의 징검다리 건너기 첫 번째 줄에 땅의 크기 N(3 ≤ N ≤ 1,000), 물 생성지 개수 W(1 ≤ W ≤ N)가 주어진다. 두 번째 줄부터 W+1줄까지 물의 생성 위치 x(행), y(열) (1 ≤ x, y ≤ N)가 주어진다. W+2줄부터 N개의 줄에 www.acmicpc.net 풀이 물 이동은 1초에 상하좌우 한 번씩 움직이므로 BFS로 만들 수 있습니다. 치삼이는 상하좌우와 대각선을 포함한 8개의 방향으로 움직일 수 있는데, 치삼이가 이동하는데 시간이 걸리지 않는다고 했으므로 치삼이가 도착할 수 있는 시간은 치삼이의 이동 경로중에 제일 늦게 식은 돌의 시간이 됩니다. 그래서 치삼이의 시간을 구하는 것은 다익스.. 공감수 0 댓글수 0 2021. 10. 1.
[BOJ 20667, C++] 크롬 https://www.acmicpc.net/problem/20667 20667번: 크롬 첫 줄에는 N, M, K 값이 주어진다. (N ≤ 100, M ≤ 1,000, K ≤ 100,000) N 은 총 크롬 탭 수이다. M 은 목표 CPU 사용량이다. K 은 목표 메모리 할당량이다. 다음 N 줄에는 다음과 같이 크롬 탭의 정보가 www.acmicpc.net 풀이 CPU 사용량과 메모리 사용량, 중요도 세 가지를 고려해야 하는데, 두 개는 배열의 인덱스에 저장하고, 나머지 하나는 배열의 값에 저장하면 냅색문제로 풀 수 있게 됩니다. 배열의 인덱스에 넣을 값은 CPU의 최댓값이 1,000이고, 메모리는 100,000이고, 중요도는 500이므로 CPU의 사용량과 중요도를 인덱스에 넣으면 될 것 같습니다. 배열의.. 공감수 0 댓글수 0 2021. 9. 27.
[BOJ 23030, Python 3] 후다다닥을 이겨 츄르를 받자! https://www.acmicpc.net/problem/23030 23030번: 후다다닥을 이겨 츄르를 받자! 쿠기는 평소 지하철 최단 경로를 탐색하여 소요 시간을 알려주는 '후다다닥' 어플을 사용 중이다. 그러나 쿠기는 걸음이 너무 느려서 '후다다닥'이 알려주는 경로를 따라가면 항상 지하철이 떠 www.acmicpc.net 풀이 지문이 좀 길지만 간단하게 정리해보면 노선 N개가 있고, 각 노선내에서 이동하는 경우는 시간이 1이 걸림 환승역에서 다른 노선으로 환승할 때는 T의 시간이 걸림(사람마다 T가 다름) 으로 정리할 수 있습니다. 이동하는데 걸리는 시간이 1 또는 T 총 2가지가 있으므로 BFS는 불가능하고, 다익스트라를 사용하여 최단거리 탐색을 할 수 있게 됩니다. 역을 저장할 때는 (노선 번호.. 공감수 0 댓글수 0 2021. 9. 24.
[BOJ 23061, Python 3] 백남이의 여행 준비 https://www.acmicpc.net/problem/23061 23061번: 백남이의 여행 준비 1번 배낭이 담을 수 있는 무게는 20이고, 담을 수 있는 최대 가치는 34이므로 효율성은 1.7이다. 2번 배낭이 담을 수 있는 무게는 21이고, 담을 수 있는 최대 가치는 37이므로 효율성은 약 1.76이다. 3 www.acmicpc.net 알고리즘 학회 beans3142님의 풀이를 들음 C++은 오버플로가 문제던데 어디서 오버플로가 나는지 모르겠어서 정신 나갈 뻔하다가 파이썬으로 제출해서 통과함 출력문이 있는지 모르고 무지성으로 제출하다가 계속 틀렸음 ㅋㅋ 풀이 문제를 보자마자 냅색문제인 것을 알 수 있습니다. 일반적인 냅색문제랑 살짝 다른 점은 가방에 1개가 아닌 M개라서 이중에서 효율이 좋은 가.. 공감수 1 댓글수 4 2021. 9. 23.
[BOJ 2447, Python 3] 별찍기 - 10 https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 풀이 예제를 보면 $3^n \times 3^n$으로 된 정사각형에서 가운데가 텅 비어있고, $3^{n-1} \times 3^{n-1}$이 텅 비어있고, .... 이렇게 모든 정사각형에서 가운데가 텅 비어있는 정사각형을 그리는 것이 목표입니다. 그래서 분할정복을 사용하여 가운데를 공백으로 만들어주고 -> 이전 정사각형보다 세 배 작은 정사각형들의 가운데를 공백으로 만들어주.. 공감수 0 댓글수 0 2021. 9. 21.
[BOJ 5719, Python 3] 거의 최단 경로 https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 클래스 6을 취득했으니 이제 단계별로 풀어보기도 공부해야겠네요 풀이 P의 값이 여러가지이므로 최단경로를 구하는 알고리즘은 다익스트라를 생각해볼 수 있습니다. 거의 최단 경로는 최단 경로에 포함되는 모든 도로들을 제외한 도로로 이루어진 최단경로입니다. 최단 경로에 속하는 모든 도로들을 제외하려면 일단 adj 배열은 2차원 리스트로 하면 도로를 찾는데 O(N), 삭제를 .. 공감수 0 댓글수 0 2021. 9. 17.
[BOJ 16282, Python 3] Black Chain https://www.acmicpc.net/problem/16282 16282번: Black Chain n개의 블랙 고리가 일렬로 연결된 체인이 있다. 블랙 고리 하나는 무게가 정확히 1g 이다. 이 고리들을 이용하여 1g 부터 ng 까지 가능한 모든 무게를 생성하려고 한다. 이를 위해 고리를 일부 풀어 www.acmicpc.net 풀이 고리를 끊어내서 1g부터 ng까지 모든 무게를 생성해야 한다고 합니다. 이 문제는 보자마자 저울이라는 그리디 문제가 생각났습니다. 블랙 체인 문제는 직접 고리를 끊어내서 1g부터 ng까지 모든 무게를 표현할 수 있어야하는 것이고, 위 그리디 문제는 주어진 추들이 있을 때 이 추들을 사용해서 표현하지 못하는 최소 그램수를 출력하는 문제라 두 문제의 아이디어는 똑같습니다. .. 공감수 0 댓글수 0 2021. 9. 16.
[BOJ 6549, Python 3] 히스토그램에서 가장 큰 정사각형 https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 풀이 이 문제는 다양한 풀이가 있는데 저는 세그먼트 트리를 이용한 분할 정복 풀이를 사용하였습니다. 먼저 arr[0] ~ arr[n-1]의 모든 구간을 잡은 뒤, 세그먼트 트리를 이용하여 가장 낮은 높이의 최솟값을 찾습니다. 그래서 (구간 길이) * (제일 작은 높이)를 구하여 답을 갱신시켜준다음, 이 가장 낮은 높이를 가진 인덱스를 기준으.. 공감수 0 댓글수 0 2021. 9. 15.
[BOJ 13977, Python 3] 이항 계수와 쿼리 https://www.acmicpc.net/problem/13977 13977번: 이항 계수와 쿼리 \(M\)개의 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 참조 다양한 방법의 이항계수 알고리즘 : https://koosaga.com/63 이항계수 (nCr) mod p 계산하기 nCr = n! / (n-r)! * r! 일 때, nCr mod prime을 빠르게 계산하는 방법에 대해서 얘기하려 한다. nCr 한 쿼리는 O(1)에 처리되어야 한다고 가정한다. (즉 전처리 한번 한 이후 nCr을 하나 계산하는데 O(1)) 1. O(n.. koosaga.com 페.. 공감수 1 댓글수 0 2021. 9. 14.
[BOJ 1019, Python 3] 책 페이지 https://www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 풀이 1 2 3 4 5 6 7 n = int(input()) arr = [0] * 10 for i in range(1, n+1): x = str(i) for j in range(len(x)): arr[int(x[j])] += 1 print(n, '-', arr) cs 이 코드는 O(N^2)로 답을 구하는 경우인데, 첫번째 자리수의 값을 제외한 나머지 값들을 9로 설정하고 확인해보면 규칙성이 나옵니다. 9 - [0, 1, 1, 1, 1, 1, 1, 1, 1, 1] .. 공감수 0 댓글수 0 2021. 9. 13.
[BOJ 20047, C++] 동전 옮기기 https://www.acmicpc.net/problem/20047 20047번: 동전 옮기기 입력은 표준입력을 사용한다. 첫 번째 줄에 나열된 동전 개수를 나타낸 양의 정수 n (3 ≤ n ≤ 10,000)이 주어진다. 다음 두 줄에 n 개의 동전이 나열된 상태인 S 와 T 가 각각 주어지며, 이 때 S와 T www.acmicpc.net 알고리즘학회 soo7652, kimtaehyun98님의 풀이를 들었음 투포인터로 접근 했었는데, N의 값이 작으면 걍 DP부터 생각해보는게 나은 것 같음. 참고로 투포인터를 사용하면 S[idx1] == T[idx2]일 때, idx1 += 1, idx2 += 1이 아닌 선택한 동전을 S에 넣고 idx2+=1을 하는 방법을 구현하기가 매우 어렵게 됩니다. 풀이 간단한 문제.. 공감수 1 댓글수 0 2021. 9. 10.
[BOJ 20041, Python 3] Escaping https://www.acmicpc.net/problem/20041 20041번: Escaping 첫 번째 줄에는 경찰의 수 N이 주어진다. 단, 1 ≤ N ≤ 500,000이다. 그 다음 N 개의 줄에는 각 경찰의 초기 위치의 좌표 (xi, yi)가 공백을 사이에 두고 주어진다. 다음 줄에는 도둑의 초기 위치의 좌 www.acmicpc.net 풀이 문제에서 예시 그림을 제공하여 쉽게 이해할 수 있던 문제입니다. 잘 생각해보면 도둑은 상하좌우 네 방향중 한 곳으로 쭉 도망치는 것이 제일 효율적으로 도망치는 것을 알 수 있습니다. 왜냐하면 만약 도둑이 원래 가던 방향이 아닌 90도 직각으로 꺾어서 한 칸 이동하면 경찰도 그만큼 한 칸 더 이동하여 방어적으로 펼칠 수 있기 때문입니다. 경찰의 위치는 (x, .. 공감수 0 댓글수 0 2021. 9. 9.
[BOJ 20046, Python 3] Road Reconstruction https://www.acmicpc.net/problem/20046 20046번: Road Reconstruction 입력은 표준입력을 사용한다. 첫 번째 줄에 도시를 표현하는 격자의 행과 열의 크기를 각각 나타내는 두 개의 양의 정수 m, n (1 ≤ m, n ≤ 1,000, 1 < m×n)이 주어진다. 다음 m개의 각 줄에 격자의 각 www.acmicpc.net 풀이 일단 BFS를 생각해볼 수 있는데 도로의 비용이 0 또는 1뿐이라면 덱을 활용한 0-1 BFS를 생각해볼 수 있지만, 비용이 0, 1, 2로 총 세가지이기 때문에 BFS로는 풀기 힘들 것 같고, 다익스트라 알고리즘을 사용하면 됩니다. 참고로 문제에 (0, 0)의 값이 -1일 수도 있다는 점을 주의해주시면 됩니다. 코드 1 2 3 4 5 .. 공감수 0 댓글수 0 2021. 9. 8.
[BOJ 20040, C++] 싸이클 게임 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 풀이 문제만 읽으면 어떤 알고리즘을 써야하는지 이해가 잘 안되지만, 예제를 직접 그림으로 그려보면서 파악해보면 바로 유니온파인드(분리집합) 알고리즘을 사용해야 한다는 것을 알 수 있습니다. 사이클을 만들어지는 조건이 두 점의 번호가 같은 선으로 이어져 있을 경우니까요. n의 값이 500,000이기 때문에 파이썬은 sys.setrecursionlimit(500000)을 사용해야 아마 통과할 것.. 공감수 0 댓글수 0 2021. 9. 8.
[BOJ 20044, Python 3] Project Teams https://www.acmicpc.net/problem/20044 20044번: Project Teams 입력은 표준입력을 사용한다. 입력의 첫 번째 행에는 팀 수를 나타내는 양의 정수 n(1 ≤ n ≤ 5,000)이 주어진다. 그 다음 행에 학생 si 의 코딩 역량 w(si)를 나타내는 2n개의 양의 정수가 공백으로 www.acmicpc.net 풀이 두 명씩 짝지어서 팀을 이루는데 이 팀들의 최솟값이 최대화가 되는게 목적입니다. 유명한 그리디 유형인데, 정렬을 하고 왼쪽에서 i번째 값과 오른쪽에서 i번째 값을 더해주면 최솟값의 합이 최대화가 됩니다. 코드 1 2 3 4 5 6 n = int(input()) w = sorted([*map(int, input().split())]) ans = 987654.. 공감수 0 댓글수 0 2021. 9. 8.
[BOJ 15906, Python 3] 변신 이동 게임 https://www.acmicpc.net/problem/15906 15906번: 변신 이동 게임 첫 줄에 2차원 격자의 크기 N(1≤ N ≤ 500), 일반 모드에서 변신 모드로 변신하는 데 소모되는 턴의 수 t(0 ≤ t ≤ 500), 목표 지점의 행과 열의 번호 r(1 ≤ r ≤ N), c(1 ≤ c ≤ N)가 주어진다. 다음 줄에 www.acmicpc.net 풀이 처음엔 BFS를 생각해볼 수 있는데 일반 이동은 (이동 횟수) + 1이지만, 변신모드로 변할 때는 (이동 횟수) + t가 되기 때문에 이걸 단순 큐에 넣어서 풀어보면 이미 방문한 경로가 다시 업데이트될 수도 있기 때문에 시간이 오래 걸리므로 다익스트라 알고리즘을 생각해볼 수 있습니다. 방문 방법은 visit 배열 2개로 나눠 각각 변신모.. 공감수 0 댓글수 0 2021. 9. 8.

반응형

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.