Studying IT with cobinding

[백준/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)에서 같은 높이..

[OS] os를 공부하기 위해 알아야 하는 용어들

2023.03.10·

CS/OS

컴퓨터 시스템 구조 각각의 I/O device에는 이 디바이스를 관리하는 작은 cpu가 붙어있음(= device controller) cpu 안에도 register 있다. cpu는 항상 메모리에 있는 instructions만 실행한다. timer : 특정 프로그램이 cpu를 독점하는 걸 막기 위한 장치(time sharing) ➡️ 하나의 instructions이 긴 시간 잡아먹으면 interrupt 걸림. interrupt 걸리면 running ➡️ blocked 상태로 interrupt 사용자 프로그램은 항상 OS를 통해 I/O 장치에 접근할 수 있다. Multiprogramming/Multiple processing 메모리에 여러 프로그램이 동시에 올라가는 방식 * 같이 알아둬야할 것 cpu는 사실..

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

[OS] 운영체제

2023.03.09·

CS/OS

운영체제 컴퓨터 하드웨어 바로 위에 설치되어, sw와 hw를 연결하는 sw 계층 좁은 의미 : 커널(운영체제의 핵심, 부팅 이후 항상 메모리에 상주) 넓은 의미 : 각종 시스템들 운영체제의 목적 1. 자원을 효율적으로 관리하는 것 hw 자원(cpu, 메모리, I/O 장치 등)을 관리 sw 자원(프로세스, 파일, 메시지 등)을 관리 형평성있는 자원 배분 2. 사용자가 편리하게 컴퓨터를 사용할 수 있는 환경을 제공하는 것. 운영체제의 분류 ✅ 동시 작업 가능 여부를 기준으로 2가지로 나뉜다. 1. 단일 작업(single tasking) 한 번에 하나의 작업만 처리 ex) MS-DOS 프롬프트 2. 다중 작업(multi tasking) 동시에 두 개 이상의 작업 처리 ex) UNIX, MS Windows ✅ ..

[백준/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는 알고리즘이 정해져 있어서 막 구현이 어려운 문제는 아니다.하지만 이 문제를 어떻게..

[DB/MySQL] 기본 명령어3 | ORDER BY, GROUP BY, DISTINCT, LIMIT

2023.02.24·

DB

ORDER BY파이썬 sort / sorted와 똑같음.오름차순이 default이고 내림 차순으로 하려면 뒤에 DESC(Descending)을 붙여주면 된다.SELECT *FROM cityORDER BY Population;SELECT *FROM cityORDER BY CountryCode ASC, Population DESC;# USA의 인구수 오름차순 출력SELECT *FROM cityWHERE CountryCode = 'USA'ORDER BY Population;GROUP BY말 그대로 그룹으로 묶어줌.집계함수(Aggregation : AVG, MIN, MAX, COUNT, STDEV(표준편차), VARIANCE(분산))과 함께 사용 CountryCode 별로 인구수의 평균 볼건데,, Country..

[DB/MySQL] 기본 명령어2 | BEETWEEN, IN, LIKE, ALY, ALL

2023.02.23·

DB

BETWEEN 숫자로 구성된 연속적인 데이터 BETWEEN, ANDSELECT *FROM cityWHERE Population 7000000 AND 8000000IN()이산값 조건SELECT *FROM cityWHERE Name IN('Seoul', 'Pusan')LIKE문자열의 내용 검색 (%랑 _ 사용)KOR 기억안남.. KO 뒤에 한 글자 머였더라..? 할 때 SELECT *FROM cityWHERE CountryCode LIKE 'KO_'Tel로 시작하는 .. 도시 뭐더라..? 할 때SELECT *FROM cityWHERE Name LIKE 'tel %' ANY / SOME서브 쿼리의 여러가지 조건 중 하나만 만족해도 출력SELECT *FROM cityWHERE Population > ANY # ..

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

[알고리즘] 이진탐색 Lower/Upper Bound | Python bisect

2023.02.20·

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

티스토리툴바