[백준/10158] 개미 | 점화식 그게 뭔데 그거 어떻게 하는 건데
·
PS/BOJ&Programmers
10158 개미  알고리즘t의 범위가 1 ≤ t ≤ 200,000,000이므로 완전탐색을하면 타임아웃이다.그렇다면 어떤 점화식을 세워서 문제를 풀어야 한다는 건데 1. x와 y의 독립성이 문제는 1초의 시간이 지날 때 x = (x+1) or (x-1)이 되고y = (y+1) or (y-1)이 된다.따라서 각각의 값이 독립적으로 움직인다는 결론에 도달할 수 있다.  2. 이동 횟수와 이동 거리의 관계 x좌표와 y좌표는 각각 t만큼 이동을 하게 되고, 이 이동 주기가 2*w, 2*h이다.아래와 같은 그래프를 보면 이해가 쉽다.따라서 이동 자체에 대한 점화식은 다음과 같다.(p+t) % 2*w(q+t) % 2*h이제 이동 좌표에 관한 점화식을 얻었으니, 거리를 구하면 된다. 거리는 수학적으로 뺄셈을 의미하기도..
[백준/9252] 음식물 피하기 | 배운 점이 많은 문제
·
PS/BOJ&Programmers
1743 음식물 피하기   알고리즘cnt 처리방식 구현이 쉽게 떠오르지 않았다.  def dfs(x,y) : cnt = 1 visited[x][y] = True for dx, dy in d : nx, ny = x+dx, y+dy # 여기가 연결되는 부분이니까 cnt += 1 처리를 해주고, if 0  이 문제에서 dfs 함수는 #를 발견하면 주변(d 좌표)을 탐색하면서 같은 영역에 속하는 곳의 크기가 얼마인지 세어주는 함수이다. 따라서 if문 조건은 주변 영역에서 계속 #이 이어지는 경우이므로, 이때 개수를 세어주어야 한다. 처음에 잘 생각이 안나서 cnt += 1 이런식으로 세어주고 return했는데 그러면.. 같은 ..
[백준/9251] LCS | 최장공통수열
·
PS/BOJ&Programmers
9251 LCSLCS 문제 해결 기법두 수열 중 하나를 비교대상으로 잡고 나머지 수열의 문자열을 하나씩 추가하면서 공통 수열 길이 값을 table에 표시해준다.문자열이 같으면 dp table에 저장을 하고, 다시 구하지 말자.dp table은 memoization 방식으로 이어나간다.알고리즘이 문제는 부분 수열 중 가장 긴 것을 찾는 것으로 그냥 숫자만 출력해주면 돼서 dp table에 같은 문자를 확인하면 +1 누적해주면 된다,,table 설명을 위해 i=6, j=4일 때를 예를 들어보자면일단 table은 이중 for문으로 j가 먼저 돌고있는 상황이다. 그러니까 'ACAYKP'라는 문자열에 대해서 'CAPCAK'를 상대적으로 놓고 하나씩 비교를 하고 있는 것이다. 가장 긴 공통 문자열의 길이를 묻는 거..
[백준/2178] 미로 탐색 | BFS와 최단 경로
·
PS/BOJ&Programmers
BFS와 최단 경로BFS는 최단거리와 관련있다. 왤까?BFS 알고리즘과 구현에 대해 이해하면, 이에 대한 해답을 얻을 수 있다. BFS 알고리즘을 이해하기 위해서는 먼저 bfs 알고리즘이 node를 방문하는 순서를 살펴봐야 한다.bfs는 위 그림과 같이 인접한 노드를 먼저 방문한다.그리고 방문한 순서대로 노드들을 Q에 넣고 시작점에서 인접한 Node를 모두 방문하면, Q 맨앞의 노드를 popleft한다. 이후 popleft된 노드들의 인접한 노드를 탐색하여 이 노드들도 똑같이 Q에 저장한다. 결론적으로 queue는 선입선출 방식으로 동작되기 때문에 방문 노드들이 순서대로 queue에 저장된다.흠.. 이렇게만 봐서는 왜 최단경로인지 모르겠다;; 예시를 보자.시작점 A에서 F까지의 최단경로를 알아본다고 했을..
[백준/16283] Farm
·
PS/BOJ&Programmers
https://www.acmicpc.net/problem/16283 16283번: Farm입력은 표준입력을 사용한다. 첫 번째 줄에 네 정수 a, b, n, w가 한 줄에 주어진다. 1 ≤ a ≤ 1,000, 1 ≤ b ≤ 1,000, 2 ≤ n ≤ 1,000, 2 ≤ w ≤ 1,000,000이다.www.acmicpc.net[알고리즘]백준 사이트에서 알고리즘 문제를 풀고 나면 다른 사람이 쓴 코드를 항상 확인해보는데, kocc10님의 코드에 배울 점이 많아서 포스팅 해본다. [내가 쓴 코드]a, v, n, w = map(int, input().split())ans = []for i in range(n) : for j in range(n) : if a*i + v*j == w and i..
[백준/2961] 도영이가 만든 음식 | 브루트포스의 구조(조합) | 곱셈 누적 초기화는 1 | 디버깅을 열심히 하자. 내가 짠 코드를 파악하는 방법
·
PS/BOJ&Programmers
https://www.acmicpc.net/problem/2961 2961번: 도영이가 만든 맛있는 음식첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은www.acmicpc.net알고리즘 완전탐색 문제다. 문제에서 "요리의 쓴맛과 신맛은 모두 1,000,000,000보다 작은 양의 정수라고 했기 때문에 브루트포스임을 단번에 파악할 수 있었다.   신맛과 단맛을 저장해서 선택하여 곱과 합을 조합해줘야 하기 때문에 combination 함수를 사용했다.다. 브루트포스 알고리즘은 조건을 빼먹지 않고 구현하는 것이 핵심이기 때문에, 하나하나 구체적으로 코드를 작성..
[백준/1260] DFS와 BFS | 인접 리스트에 그래프 저장하기
·
PS/BOJ&Programmers
알고리즘아래와 같이 그래프의 연결 상태가 주어진다면, 인접 리스트와 인접 행렬 두 가지 방식으로 관계를 정의할 수 있다.이 문제에서는 인접 리스트를 사용하여 그래프 관계를 정의하겠다.1 21 31 42 43 4 [인접리스트를 활용한 그래프 표현] 1. 간선의 개수 만큼 정점의 관계들이 입력 되니까 간선의 수 만큼 for문을 반복.2. 두 정점을 입력 받아서 연결관계를 표현하기 위해 서로의 리스트에 저장. 이때 정점의 정보는 1 ~ n까지의 숫자로 나타나므로, graph의 크기를 n+1만큼 해주어야 한다.(range 함수는 n-1까지의 수를 반환하니까)# 그래프 초기화graph = [[] for _ in range(n+1)]# 간선의 개수가 m일 때for _ in range(m) : x, y = map(..
[백준/3184] 양 | 그래프 영역 구별 하기
·
PS/BOJ&Programmers
https://www.acmicpc.net/problem/3184 3184번: 양첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다.www.acmicpc.net알고리즘그래프 탐색 문제인 건 알겠는데, 같은 영역을 어떻게 판단하지?가 고민이었다.적록색약 문제에서는 bfs 함수에서 같은 색을 만나면 계속해서 q에 그 지점을 삽입하면서 탐색을 하게 만들었는데,얘도 마찬가지다..! 그래서  ⭐️⭐️⭐️⭐️⭐️ bfs 함수의 q가 모두 끝나면 ⭐️한 영역⭐️에 대한 큐가 끝나는 것임..⭐️⭐️⭐️⭐️⭐️그니까 while q 이 부분이 주변을 탐색하는 핵심..
[백준/10026] 적록색약 | 그래프 영역 구별, 같은 조건일 때 처리
·
PS/BOJ&Programmers
https://www.acmicpc.net/problem/10026 10026번: 적록색약적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)www.acmicpc.net이 문제는 조금 개인적인 일화가 있는데,, 작년 2학기에 교내 알고리즘 대회를 준비하면서 이 문제를 접하고 엄청 허둥지둥 거리다가 포기한 기억이 있다. 이 문제 구현을 어떻게 할지 구상해보면서 문득 저번 학기가 떠올랐는데, 방학 동안 꾸준히 공부한 보람이 조금이나마 있어서 다행이다..!   알고리즘bfs, dfs는 알고리즘이 정해져 있어서 막 구현이 어려운 문제는 아니다.하지만 이 문제를 어떻게..
[백준/6186] Best Grass | bfs, dfs
·
PS/BOJ&Programmers
dfs : 최대한 깊게 방문하지 않은 노드들에 쭉 방문하다가, 더이상 진행할 수 있는 인접정점이 없으면 되돌아감 - 재귀bfs : 한 노드에서 인접노드까지 방문한 적이 없는 모든 노드를 queue에 삽입. que는 FIFO 방식이라서 순차적인 구현 DFSfrom collections import dequer,c = map(int, input().split())pasture = [list(input()) for _ in range(r)]visit = [[0]*c for _ in range(r)]d = [(0,1),(0,-1),(1,0),(-1,0)]cnt = 0def dfs(x, y) : visit[x][y] = 1 for dx, dy in d : nx,ny = x+dx, y+d..
[알고리즘] 이진탐색 Lower/Upper Bound | Python bisect
·
PS/Algorithm
개요이진탐색을 하는데 만약 배열에 target 값이 여러 개 존재한다면, 정확한 위치의 값을 도출하는 데에 어려움을 겪을 것이다.이를 해결하기 위한 알고리즘이 Upper Bound와 Lower Bound이다. Python에서는 bisect라는 도구를 제공한다. Lower Boundtarget 이상의 값이 최초로 나오는 위치다. 즉, target보다 같거나 큰 원소 중 가장 작은 값의 위치다. 예를 들어서 아래와 같이 정렬된 배열이 존재한다고 가정하자.15551011100 이 배열의 lower_bound(5) = 5다. 또한 lower_bound(4) = 5다.가장 작은 값을 구하기 위해서 min_idx 변수를 활용하여 초기값으로 답이 될 수 없는 최댓값을 넣어놓고 문제를 해결한다. left=0right=..
[백준/8989] 시계 | 시침, 분침의 각도
·
PS/BOJ&Programmers
https://www.acmicpc.net/problem/8989 8989번: 시계기원이의 방에는 시침과 분침으로 이루어진 아날로그 시계가 있다. 기원이는 시침과 분침이 형성하는 각도 중 작은 각도를 측정하는 것이 취미이며, 이 각도는 0보다 크거나 같고 180보다 작거나www.acmicpc.net 알고리즘신선하고 재밌는 문제다. 일단 이 문제를 풀기 위해서 그림을 그렸는데, 그리고 나서 알게된 사실은  분침은 1분당 6도를, 시침은 1시간당 30도에 1/2*m을 한 각도를 갖는 것이다.사실 처음에는 12시 ~ 3시까지 90도니까 3등분을 하면 한시간 당 30도를 갖겠지?!라고 생각하고 풀었는데, 시침은 1분 동안 0.5도씩 움직이기 때문에, 이 또한 고려해주어야 한다!!  따라서, 시침과 분침의 각도를..
[백준/2852] NBA 농구
·
PS/BOJ&Programmers
알고리즘게임 라운드별로 골 넣은 시간과 해당 팀이 주어지고, 각 팀이 몇 분동안 이기고 있는지 출력하는 문제다.게임 진행 상황에 따라서 각 팀이 이기고 있는 시간(출력물)이 바뀌기 때문에 이를 구현해야 한다. 1. 골이 들어갈 때 마다 입력을 해주는 거기 때문에 입력되는 팀 번호의 개수를 통해서 각 팀이 이기고 있는지 지고 있는지 판단한다.2. 현재 게임 득점 시간이 다음 게임 득점 시간에 영향을 주기 때문에 이전 게임의 득점 시간을 반복문의 마지막에 저장한다.3. 주어진 48분 동안 득점을 한 시간이 주어지기 때문에, (주어진 시간 - 득점 시간) 연산으로 이기고 있는 시간을 출력한다.  파이썬 시간 출력시간과 관련된 문제를 풀 때, 보통 초 단위로 시간을 변경해서 푸는데 이렇게하면 알고리즘은 쉽게 짤..
[백준/6236] 용돈 관리 | 이진 탐색 트리 | 분할 | 파이썬
·
PS/BOJ&Programmers
https://www.acmicpc.net/problem/6236 6236번: 용돈 관리현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로www.acmicpc.net 분할(partition)분할은 말 그대로 여러 개로 나눈다는 뜻인데, 이산수학에서의 분할은 보통 집합의 분할을 뜻한다.집합의 분할이란 공집합이 아닌 집합 X를 서로소인 부분집합 Y1, Y2..로 나누는 것이다.집합 Y들을 모으면 집합 X가 된다.X의 원소들은 서로소이며, 교집합이 없다.이 문제에서는 각각 일(day)별로 원소들이 있고 이들을 M번 분할하여 최소 K를 찾는다.입력 예제를 분할의 예로 들면 1..
[백준/1021] 회전하는 큐 | python deque | dequed의 rotate()
·
PS/BOJ&Programmers
파이썬 dequedeque는 문제풀이에서 종종 사용했었지만 주요 내용을 다시 한번 정리해보았다.알고리즘파이썬 deque 자료구조를 알고있다면 어렵지 않게 해결할 수 있다. 최종코드from collections import dequen,m = map(int, input().split())que = deque(range(1,n+1))idx = list(map(int, input().split()))cnt = 0for i in idx: # 다 찾을 때까지 수행 while True: # 찾고자 하는 값의 위치가 중간보다 왼쪽인 경우 if que.index(i) 연산의 횟수를 세어야 하기 때문에 cnt 변수로 연산 횟수를 카운팅했다.알게된 점from collections imp..
sebinChu
'Problem Solving' 태그의 글 목록 (2 Page)
상단으로

티스토리툴바