거창한 시작

www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 알고리즘 종류 - 우선순위 큐 - 정렬 - 자료구조 사고 과정 1. 도착 위치를 기준으로 오름차순 정렬한다. (출발 위치를 기준으로 오름차순해서 풀어보면 알겠지만, 출발 위치 + d로 범위를 탐색하면 출발 위치가 작은 사용자를 고려할 수 없다. 그래서 도착 위치를 기준으로 오름차순 정렬한다.) 2. 하나씩 가져온다. 2-1. 도착 위치 - 출발 위치가 철도 선..

www.acmicpc.net/problem/12764 12764번: 싸지방에 간 준하 첫째 줄에 사람의 수를 나타내는 \(N\)이 주어진다. \((1 \le N \le 100,000)\) 둘째 줄부터 \(N\)개의 줄에 걸쳐서 각 사람의 컴퓨터 이용 시작 시각 \(P\)와 종료 시각 \(Q\)가 주어진다. \((0 \le P \lt Q \le 1,000 www.acmicpc.net 알고리즘 종류 - 우선순위 큐 - 자료구조 - 구현 사고 과정 - 컴퓨터를 시작하는 시간에 따라 오름차순 정렬하고, 하나씩 뽑아서 사용중인 사용자들의 끝나는 시간과 비교한다. 비교해서 사용중인 사용자의 끝나는 시간보다 이전에 새로운 사용자가 들어오면 새로운 컴퓨터 자리를 만들어주고, 사용중인 사용자의 끝나는 시간보다 늦게 들어..

programmers.co.kr/learn/courses/30/lessons/1829 코딩테스트 연습 - 카카오프렌즈 컬러링북 6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5] programmers.co.kr 알고리즘 종류 - BFS 사고 과정 1. 2중 for문으로 picture를 탐색한다. 1-1. 이미 방문했거나 색이 칠해지지 않았으면 탐색하지 않는다. 2. 탐색할 위치의 y와 x를 찾았으면, BFS를 수행한다. 2-1. 이동할 때 가용한 범위에 있는지 확인한다. 2-2. 같은 색인지 확인한다. 2-3. 이미 방문했는지 확인한다. 3. BFS 탐색이 끝났으면, 최대 영역의 값을 ..

programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 알고리즘 종류 - 문자열 사고 과정 1. 자를 길이를 결정한다. 2. 초기에 맨 앞에서부터 자른다. 3. 잘라진 문자열(str)과 이후 잘라진 문자열(str2)을 비교한다. 3-1. 비교 후, 같으면 cnt++ 3-2. 비교 후, 다르면 임시 tmp에 cnt + str를 저장한다. 3-3. cnt, str 변수를 초기화 한다. 4. 끝에 남은 문자열을 처리한다. 5. ..

www.acmicpc.net/problem/13905 13905번: 세부 첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄 www.acmicpc.net 알고리즘 종류 - 이분탐색 - MST 사고 과정 1. 최대 스패닝 트리를 만든다. 2. BFS로 시작점에서 출발하여 도착지점에 도달할 때까지 각 간선의 최소값만 저장한다. 구현(C++) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565..

www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 알고리즘 종류 - 구현 사고 과정 - 기본적인 크루스칼 알고리즘에 양쪽 노드가 다른 성별인지 확인해주는 조건만 걸어주면 된다. 1. 노드의 성별을 저장할 배열을 생성한다. 2. 사이클을 확인하는 부분에 다른 성별인지 확인하는 조건을 추가한다. 구현(C++) 1234567891011121314151617181920212223242526272829303132333435363..

www.acmicpc.net/problem/2931 2931번: 가스관 러시아 가스를 크로아티아로 운반하기 위해 자그레브와 모스코바는 파이프라인을 디자인하고 있다. 두 사람은 실제 디자인을 하기 전에 파이프 매니아 게임을 이용해서 설계를 해보려고 한다. www.acmicpc.net 알고리즘 종류 - 구현 사고 과정 - 가스는 한 방향으로 이동한다. 따라서 이동하는 좌표와 방향을 기록하면서 중간에 끊긴 좌표를 찾으면 된다. 1. M과 Z의 위치를 기록한다. 2. 시작점 M의 4방향을 탐색하여 연결된 파이프가 있는 쪽에 방향을 설정한다. 2-1. 만약에 4방향에 연결된 파이프가 없으며, Z를 시작점으로 변경한다. 3. DFS 또는 BFS를 이용하여, 가스를 이동시켜본다. 3-1. 본인은 BFS를 사용하여 큐..

www.acmicpc.net/problem/10993 10993번: 별 찍기 - 18 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. www.acmicpc.net 알고리즘 종류 - 구현 사고 과정 1. 짝수일 때, 역삼각형이고 홀수일 때, 삼각형 모양이다. 2. n에 따라 가로는 1 + 2^0 + 2^1 + ... + 2^n이고, 세로는 1 + 2^0 + 2^1 + ... + 2^(n-1)이다. 3. 본인은 바깥부터 안으로 *을 표시하기로 했다. 따라서, 바깥에 *을 표시하고 다음 *을 그릴 구역을 선정한다. 3-1. 구역은 가로는 x1~x2, 세로는 y1~y2로 정했다. 3-2. x1은 처음에 0에서 시작해서 계속 2^(i-1)만큼 오른쪽(+)으로 이동한다. 3-3. x2는 처음에 가로 최대지점에서..

programmers.co.kr/learn/courses/30/lessons/59414 코딩테스트 연습 - DATETIME에서 DATE로 형 변환 ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디 programmers.co.kr 사고 과정 - DATE_FORMAT(DATETIME, 형식) : DATETIME 자료형을 년도-월-일로 출력해야 한다. 구현(C++) 1 2 3 4 -- 코드를 입력하세요 SELECT ANIMAL_ID, NAME, DATE_FORMAT(DATET..

programmers.co.kr/learn/courses/30/lessons/59411 코딩테스트 연습 - 오랜 기간 보호한 동물(2) ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디 programmers.co.kr 사고 과정 - 보호기간이 가장 긴 순서대로 나열하면 된다. ORDER BY에 column만 넣을 수 있는 것은 아니다. 아래 처럼 연산을 넣어서 정렬시킬 수 있다. 구현(C++) 1 2 3 4 SELECT INS.ANIMAL_ID, INS.NAME FROM..