'PS' 카테고리의 글 목록 (3 Page)

[백준/1913] 회의실 배정 | 그리디 | 우선순위 lambda 활용

2023.04.04·

PS/BOJ&Programmers

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 오늘 문제해결기법 강의 시간에 그리디 알고리즘을 배웠다. 교수님께서 가르쳐주신 내용을 정리해보고자 한다. 그리디 알고리즘을 예전부터 알고있었는데 활용을 잘 하지 못했다! 이번 기회에 확실히 잡아두자. 알고리즘 그리디 알고리즘: Greedy(욕심쟁이) [기본 마인드] 어떤 기준을 정하고 가장 최선의 선택을 먼저 시작한다. ✅ 그리디 문제를 풀 때는 기준을 세우는 게 중요하겠다. 어떤 문제를 푸는데 도저히 생각이 안 날 때 일단 이거부터 써보자. ➡️ 아이디어 생각은 어렵지 않으나 구현이 어려울 수 있다. ⭐️ 내 ..

[백준/1912] 연속합 | 누적합, 부분합

2023.03.29·

PS/BOJ&Programmers

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 구간합 알고리즘 크기가 N인 배열에 부분합을 구하는 연산을 M번 수행해야 한다고 하자. li[l] + li[l+1] + li[l+2] + ・・・ + li[r]는 다음과 같은 코드를 통해 구할 수 있다. ans = 0 for i in range(l,r): ans += li[i] l, r의 범위가 최악의 경우 0 ~ N-1이므로, 연산의 시간 복잡도는 O(N)이다. 이 연산을 M번 수행해야 하므로 최종적인 시간..

[백준/1912] 연속합 | 누적합 | max의 활용

2023.03.27·

PS/BOJ&Programmers

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net [알고리즘] 처음에 이 문제를 보고 이중 for문의 인덱스를 i를 기준으로 띄워가면서 누적합을 통해 결과를 도출하려고 했다. n=int(input()) li = list(map(int, input().split())) total = 0 ans=[] for i in range(n): total = 0 for j in range(i,n): total+=li[j] ans.append(total) print(max..

[백준/1312] 소수 | 런타임에러? | 부동소수점과 컴퓨터 연산에 대한 이해

2023.03.26·

PS/BOJ&Programmers

https://www.acmicpc.net/problem/1312 1312번: 소수 피제수(분자) A와 제수(분모) B가 있다. 두 수를 나누었을 때, 소숫점 아래 N번째 자리수를 구하려고 한다. 예를 들어, A=3, B=4, N=1이라면, A÷B=0.75 이므로 출력 값은 7이 된다. www.acmicpc.net 투 포인터 헷갈려서 쉬운 문제 찾다가 된통 당한! 문제.. 단순하게 str로 바꿔서 풀면 런타임 에러가 난다. 백준 문제에서 오타 등의 문제가 아닌 알고리즘으로인해 런타임 에러가 난 경우는 처음이다. 그만큼 배울 점이 많아서 기록해본다. 이 문제는 컴퓨터의 부동소수점 연산에 대한 이해가 기반되어야 한다. 사실 문제에서 대놓고 힌트를 제공하고 있다. 첫 번째 줄에 A와 B(1 ≤ A, B ≤ 1..

[백준/15686] 치킨 배달 | 시뮬레이션 | 2차원 공간 좌표 다루기

2023.03.21·

PS/BOJ&Programmers

이번주 주제는 시뮬레이션. 부끄럽지만 시뮬레이션은 처음 공부해본다~^^ 별 것 아님. https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net [주요 유형] 1. 2차원 공간(상,하,좌,우) ✅ 방향 벡터를 잘 쓰자. 2. 특정 게임 구현 ✅ 머릿속으로 상상하면서 테스트 케이스를 떠올리자. [Skills] 1. 문제를 잘 읽고 조건을 빼먹지 않게 메모하자 2. 자료구조를 잘 활용하자. 주절..주절...주절.... 사실 이 문제를 포..

[백준/13699] 점화식 | 동적계획법 dp 개념(피보나치)| 이중포문의 활용 |

2023.03.19·

PS/BOJ&Programmers

https://www.acmicpc.net/problem/13699 13699번: 점화식 다음의 점화식에 의해 정의된 수열 t(n)을 생각하자: t(0)=1 t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0) 이 정의에 따르면, t(1)=t(0)*t(0)=1 t(2)=t(0)*t(1)+t(1)*t(0)=2 t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5 ... 주어진 입력 0 ≤ n www.acmicpc.net [동적 계획법] dp는 이전 문제들의 답을 메모해두는 알고리즘이다. 피보나치 수열과 같이 이전에 계산한 문제의 해가 계속 필요할 때 유용하다. 그래서 동적 계획법의 핵심은 "Memoization"이다. 메모리제이션은 이전에 계산한 값들을 저장해두고, ..

[백준/17202] 핸드폰 번호 궁합 | 배열을 통해서 연산 갱신하기 |011223.. 인덱싱

2023.03.19·

PS/BOJ&Programmers

https://www.acmicpc.net/problem/1720 17202번: 핸드폰 번호 궁합 어린시절 다들 한 번씩은 이름으로 궁합을 본 적이 있을 것이다. 이것과 비슷한 방식으로 중앙대학교에는 핸드폰 번호 궁합을 보는 것이 유행이라고 한다. 핸드폰 번호 궁합을 보기 위해서는 www.acmicpc.net [알고리즘] 새로운 배열을 갱신하고, 그를 이용해서 계속 계산을 이어나가야 함. => 반복문 안에서 연산 후, 리스트로 값 갱신하고 원래 리스트에 담아서 갱신! 리스트 인덱싱 01 12 23 34.. 이렇게 할 때는 li[i], li[i+1] 이렇게하면 끝자리는 계산 자동으로 되니까 len(li)-1의 한칸 앞까지만 for문 돌려주면 된다. 이거 자주 쓰는데 항상 고민한다.. [최종 코드] a = ..

[백준/18111] 마인크래프트

2023.03.12·

PS/BOJ&Programmers

https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net [알고리즘] 1) 완전 탐색 시간 복잡도 500 * 500 * 256 = 64,000,000 때문에 min, max를 정해서 사용했는데 생각해보니 하나의 land에 0과 256이 같이 들어있으면 min_land = 0, max_land = 256이 되어서 방지할 수 없다. 그래서 3중 for문으로 완전 탐색을 하게 되면 시간 초과다. 2) 이를 해결하기 위해 이차원리스트(land)에서 같은 높이..

[백준/16283] Farm

2023.03.10·

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 | 디버깅을 열심히 하자. 내가 짠 코드를 파악하는 방법

2023.03.05·

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 | 인접 리스트에 그래프 저장하기

2023.03.01·

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] 양 | 그래프 영역 구별 하기

2023.02.28·

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] 적록색약 | 그래프 영역 구별, 같은 조건일 때 처리

2023.02.27·

PS/BOJ&Programmers

https://www.acmicpc.net/problem/10026 10026번: 적록색약적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)www.acmicpc.net이 문제는 조금 개인적인 일화가 있는데,, 작년 2학기에 교내 알고리즘 대회를 준비하면서 이 문제를 접하고 엄청 허둥지둥 거리다가 포기한 기억이 있다. 이 문제 구현을 어떻게 할지 구상해보면서 문득 저번 학기가 떠올랐는데, 방학 동안 꾸준히 공부한 보람이 조금이나마 있어서 다행이다..! 알고리즘bfs, dfs는 알고리즘이 정해져 있어서 막 구현이 어려운 문제는 아니다.하지만 이 문제를 어떻게..

[백준/9291] 스도쿠 채점 | n*n 행렬에서 m*m 행렬 추출하기

2023.02.26·

PS/BOJ&Programmers

https://www.acmicpc.net/problem/9291 9291번: 스도쿠 채점각 테스트 케이스에 걸쳐 "Case x:"를 출력한 후, 공백 한 칸 뒤에 풀이가 올바르면 "CORRECT"를, 아니면 "INCORRECT"를 출력한다. x는 테스트 케이스 번호이며, 1부터 시작한다.www.acmicpc.net 새벽에 졸린 거 참아가며 풀었는데,, ㅋ알고보니 입력값 중간에 엔터 처리 때문에 오늘까지 끌고왔다.2차원 리스트에서 열만 추출하기행은 어차피 앞쪽 인덱스만 처리해주면 행값만 추출하니까 어렵지 않게 추출할 수 있다. 근데 열은..?! [ ][i] 이런 처리가 안되니까, 따로 빼주어야 한다.이때 이중 for문의 구조를 활용하면 되는데,안쪽 for문 인덱스가 먼저 증가하니까 먼저 증가하는 인덱스를..

[백준/6186] Best Grass | bfs, dfs

2023.02.22·

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..

티스토리툴바