'PS/BOJ&Programmers' 카테고리의 글 목록 (3 Page)

[백준/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+j ==..

[백준/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 2 1 3 1 4 2 4 3 4 [인접리스트를 활용한 그래프 표현] 1. 간선의 개수 만큼 정점의 관계들이 입력 되니까 간선의 수 만큼 for문을 반복. 2. 두 정점을 입력 받아서 연결관계를 표현하기 위해 서로의 리스트에 저장. 이때 정점의 정보는 1 ~ n까지의 숫자로 나타나므로, graph의 크기를 n+1만큼 해주어야 한다. (range 함수는 n-1까지의 수를 반환하니까) # 그래프 초기화 graph = [[] for _ in range(n+1)] # 간선의 개수가 m일 때 for _ in range(m) :..

[백준/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문 인덱스가 먼저 증가하니까 먼저 증가..

[PS/MySQL] 프로그래머스 SQL 고득점 Kit Lv1 문제(3) ^_^

2023.02.24·

PS/BOJ&Programmers

평균 일일 대여 요금 구하기 SELECT CAR_TYPE, ROUND(AVG(DAILY_FEE),0) AS 'AVERAGE_FEE' FROM CAR_RENTAL_COMPANY_CAR WHERE CAR_TYPE = 'SUV'; ROUND 반올림 WHRER 테이블의 열 name 지정 강원도에 위치한 생산공장 목록 출력하기 SELECT FACTORY_ID, FACTORY_NAME, ADDRESS FROM FOOD_FACTORY WHERE ADDRESS LIKE '강원도%' ORDER BY FACTORY_ID 문제에서 'a,b,c에 대해서만 조회하세요'하면 SELECT에 * 말고 a,b,c 써주기 LIKE 문자 찾기!! (_랑 %) 12세 이하인 여자 환자 목록 출력하기 [MySQL IF function] IF..

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

2023.02.22·

PS/BOJ&Programmers

dfs : 최대한 깊게 방문하지 않은 노드들에 쭉 방문하다가, 더이상 진행할 수 있는 인접정점이 없으면 되돌아감 - 재귀 bfs : 한 노드에서 인접노드까지 방문한 적이 없는 모든 노드를 queue에 삽입. que는 FIFO 방식이라서 순차적인 구현 가능 popleft로 앞에거 빼주면 됨 ㅇㅇ dfs 구현 from collections import deque r,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 = 0 def dfs(x, y) : visit[x][y] = 1 for dx, dy in ..

[백준/6550] 부분 문자열 | 반복문으로 고정된 인덱스 다루기

2023.02.21·

PS/BOJ&Programmers

알고리즘 있는지 없는지 확인하면 되겠네~~ 개꿀~~ 이런 태도로 문제를 대했지만 내가 간과한 것이 있었다. 처음에 이중 for문으로 s랑 t를 비교해서 다르면 pop하는 알고리즘을 생각했는데 이렇게 하면 s가 t의 '부분 문자열'인지 알 수 없다. 왜냐면,, 전체를 돌면서 문자가 다르기만 하면 pop을 해버리니까 '부분 문자열'인지 판단이 불가능하다. s에 속하는 문자가 있냐/없냐의 문제가 아니라 s가 t의 부분 문자열인가?라는 문제기 때문에 이중 for문으로 s와 t를 도는 식으로는 해결이 불가능하다는 뜻. 따라서 s를 단순히 반복하며 t에 있는 문자들과 비교하는 방식이 아니라 순차적으로 돌면서 t에 속하는 문자와 같은지 확인해주면 된다. 1. for문으로 비교하고자 하는 t를 돌면서 만약 t의 문자와..

[백준/8989] 시계 | 시침, 분침의 각도

2023.02.19·

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 농구

2023.02.16·

PS/BOJ&Programmers

알고리즘 게임 라운드별로 골 넣은 시간과 해당 팀이 주어지고, 각 팀이 몇 분동안 이기고 있는지 출력하는 문제다. 게임 진행 상황에 따라서 각 팀이 이기고 있는 시간(출력물)이 바뀌기 때문에 이를 구현해야 한다. 1. 골이 들어갈 때 마다 입력을 해주는 거기 때문에 입력되는 팀 번호의 개수를 통해서 각 팀이 이기고 있는지 지고 있는지 판단한다. 2. 현재 게임 득점 시간이 다음 게임 득점 시간에 영향을 주기 때문에 이전 게임의 득점 시간을 반복문의 마지막에 저장한다. 3. 주어진 48분 동안 득점을 한 시간이 주어지기 때문에, (주어진 시간 - 득점 시간) 연산으로 이기고 있는 시간을 출력한다. 파이썬 시간 출력 시간과 관련된 문제를 풀 때, 보통 초 단위로 시간을 변경해서 푸는데 이렇게하면 알고리즘은 ..

티스토리툴바