본문 바로가기

분류 전체보기154

[백준] 두 배 더하기 https://www.acmicpc.net/problem/12931 12931번: 두 배 더하기 모든 값이 0으로 채워져 있는 길이가 N인 배열 A가 있다. 영선이는 다음과 같은 두 연산을 수행할 수 있다. 배열에 있는 값 하나를 1 증가시킨다. 배열에 있는 모든 값을 두 배 시킨다. 배열 B가 주 www.acmicpc.net 배열의 모든 요소들을 0으로 만드는 최소횟수를 구하는 방식으로 바꿔서 생각해보면 편하다. 최소횟수가 되기 위해서는 나누기 연산을 최대한 활용해야하는데 그렇게 하기 위해서 nums의 모든 요소들을 짝수로 만들어주고 나누기를 진행해주면 된다. # 문제링크: https://www.acmicpc.net/problem/12931 import sys input = sys.stdin.readl.. 2023. 2. 6.
[백준] 숨바꼭질 4 https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net BFS를 통해 +1, -1, 순간이동(X2)를 통해 도달할 수 있는 모든 경우를 체크해주었습니다. 우선순위 큐를 활용하여 cnt가 낮은 상태가 먼저 나오도록 하여 현재 숫자에 도달할 수 있는 가장 적은 횟수가 visited에 저장되도록 하였습니다. 그 다음으로는 순서를 정하는 방법입니다. K를 시작으로 +1을 통해 도달한 경우, -1을 통해 도달한 경우, 순간이동.. 2023. 2. 6.
[백준] 군사 이동 https://www.acmicpc.net/problem/11085 11085번: 군사 이동 전쟁 당시 Baekjoon World의 국왕은 Cube World를 공격할 작전을 세운 적이 있습니다. Baekjoon World와 Cube World는 p개의 지점과 w개의 길로 표현됩니다. 모든 길은 양방향이며, 각 길마다 너비가 존재하여 www.acmicpc.net 경로에 존재하는 가장 넓은 너비를 구하는 것이 목적인 문제입니다. 지나갈 수 있는 최소 너비를 지정해주고 이보다 큰 간선만을 택하면서 다익스트라를 수행한 다음 목적지에 도달할 수 있는지를 체크하면 풀 수 있습니다. # 문제링크: https://www.acmicpc.net/problem/11085 import sys, os, heapq from c.. 2023. 2. 5.
[백준] 트리의 지름 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 두 정점 사이의 경로가 가장 긴 값(트리의 지름)을 구하는 것이 이번 문제의 목표입니다. 트리의 특성상 부모 노드를 하나만 가질 수 있기 때문에 하나의 부모노드에서부터 자식 노드를 연결하여 만들 수 있는 최대 경로의 길이를 정할 수 있습니다. dfs로 탐색해주면서 현재 노드에서 도달할 수 있는 최대 길이를 리턴해주고 현재 노드에서 만날 수 있는 상위 2개의 최대 길이를 더해주면 트.. 2023. 2. 4.
[백준] 낚시왕 https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 삼성 기출 문제의 경우 설계를 잘해야하는데 심신미약 상태에서 푸느라 설계부터 꼬여서 고생을 많이한 문제입니다. 포인트가 되는 부분은 상어의 다음 위치를 가져오는 next_pos 함수입니다. 핵심 포인트는 행이 1, R, 열이 1, C를 벗어나게 됐을 때 얼마나 벗어났는지 계산하여 반영해주어야하는게 포인트입니다. 왼쪽으로 향하다가 벗어나서 오른쪽으로 방향 전환하여 진행해도 격자를.. 2023. 2. 3.
[백준] 물대기 https://www.acmicpc.net/problem/1368 1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어 www.acmicpc.net 문제의 특징을 생각해봤을 때 논에 물을 끌어오려면 연결 그래프여야하고 각각의 연결 비용을 합쳤을 때 최소비용이 되어야하므로 자연스럽게 최소 신장 트리로 풀어야한다고 생각했습니다. 문제는 직접 논에 우물을 파는 것을 처리해야하는데 이 부분은 별도의 노드(코드에서는 other_node)를 만들어서 우물을 팔 때 발생하는 비용으로 각 노드와 연결시켰습니다. 이렇게 구축한 .. 2023. 2. 3.
[BOJ] 일요일 아침의 데이트 https://www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트 첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있 www.acmicpc.net 문제의 지문을 잘 읽어야하는 국어문제입니다. 만약 어떤 칸이 비어있는데, 인접한 칸에 쓰레기가 있으면 쓰레기 옆을 지나는 것이다. 그리고, S와 F는 세지 않는다. 라는 지문의 내용이 있는데 이 부분을 처리하지 않으면 잘못된 답이 나오게 됩니다. S, F인 경우에는 쓰레기에 인접해있지 않는 칸으로 처리하여 해결하면 됩니다. 큐에서 빠져나오는 우선순위를 정해주기 위해 우.. 2023. 2. 2.
최장 공통 부분 수열(LCS) 최장 공통 부분 수열이란? 먼저, 부분 수열이란 순서대로 뽑아서 나올 수 있는 수열들을 의미합니다. 예를 들어 abcdefb의 부분 수열에는 abc, bdf등이 있습니다. 따라서 공통 부분 수열은 두 문자열에서 순서대로 뽑아서 나올 수 있는 공통 부분 수열을 의미합니다. 예를 들의 abcde와 cde의 공통 부분 수열에는 ce, de cde 등이 있습니다. 마지막으로 최장 공통 부분 수열은 두 문자열에서 순서대로 뽑아서 나올 수 있는 가장 길이가 긴 공통 부분 수열이 됩니다. abcde와 cde의 최장 공통 부분 수열은 cde가 됩니다. DP를 활용하여 LCS 구하기 LCS는 DP를 활용하여 해결할 수 있습니다. 두 문자열 A, B의 LCS를 구한다고 가정하면 DP[i][j]는 A의 i번째까지의 문자와 .. 2022. 12. 13.
[코드트리] 미로 타워 디펜스 - python ↑문제 링크: https://www.codetree.ai/frequent-problems/maze-tower-defense/description 코드트리 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 제일 문제가 되는 부분은 나선형으로 2차원 Array를 어떻게 방문할지였습니다. 문제에서는 중심을 시작으로 ←, ↓, →, ↑ 순으로 진행하게 되는데 저는 (0, 0)을 시작으로 →, ↓, ←, ↑ 순으로 탐색한 다음 순서를 뒤집어서 방문 순서를 저장해 두었습니다. 이렇게 변형한 이유는 변형된 순서로 탐색을 하게 되면 다음 위치가 격자를 벗어나거나 이미 방문한 위치이면 방향을 을 전환하면 되기 때문에 .. 2022. 10. 13.

티스토리툴바