본문 바로가기

전체 글

 (189)
[Python] 정렬 - 1374.강의실(골5) /heapq를 이용한 시간초과 극복 목차 1. 문제 2. 핵심 아이디어 3. 코드 4. 배운 점 1. 문제 https://www.acmicpc.net/problem/1374 1374번: 강의실 첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 www.acmicpc.net 2. 핵심 아이디어 2-1) 무엇을 고려해야 하나 : 끝나는 시간과 시작시간 당신이 4-6시의 강의를 담당하는 교수가 되었다고 하자. 강의실을 예약할 때 우리는 무엇을 고려해야 할까? 우리가 강의를 시작하는 4시를 기준으로 다른 강의들의 끝나는 시간을 살펴볼 것이다. 만약 어떤 강의실의 강의가 4시 이전에 끝난다..
[Python] DFS/BFS - 2636. 치즈(골4) / 경계면 탐색 목차 1. 문제 2. 핵심 아이디어 3. 코드 4. 배운 점 1. 문제 https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 2. 핵심 아이디어 2-1) 경계면 탐색 지금껏 1로 구성되어 있는 영역을 탐색해왔다면 이번에는 0과 맞닿은 1을 탐색해야 하는 문제였다. 즉, 가장자리인 (0,0)부터 공기층을 탐색하다가 치즈층(1)을 만나면 그 좌표층을 melt리스트에 추가한다. 이후, 녹여야하는 melt층의 좌표를 하나씩 꺼내며 치즈를 0으로 녹여준다. 2-2) 치즈가 없어..
[Python] DFS/BFS - 10026. 적녹색약(골5) / 탐색 기준값이 변수 목차 1. 문제 2. 핵심 아이디어 3. 코드 4. 배운 점 1. 문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 2. 핵심 아이디어 2-1) 적녹색약의 관점에서 세상보기 : 우선 이 문제를 처음 보자마자 탐색 문제라는 것은 인식하는 것에는 큰 어려움이 없었다. 중요한 문제, 즉 걸림돌은 어떻게 적록색약의 관점에서 진행하는 탐색을 구현할 것인가? 였다. 적록색약은 빨간색(R)과 초록색(G)의 차이를 느끼지 못한다. 즉, R과 G를 ..
[Python] DFS/BFS - 11724.연결요소의 개수(실2) 목차 1. 문제 2. 핵심 아이디어 3. 코드 4. 배운점 1. 문제 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 2. 핵심 아이디어 2-1) 연결요소의 정의 : 나누어진 각각의 그래프 조건 1) 연결 요소에 속한 모든 정점을 연결하는 경로 존재 2) 다른 연결 요소에 속한 정점과 연결하는 경로가 있으면 안됨 => 독립된 하나의 덩어리여야 함. 예를 들어 위의 그래프는 2개의 ..
[미니 프로젝트] Yammer case 분석2. 검색기능 문제 1. 서론 1-1. 문제상황 정의 더보기 1-1) 기존 검색 기능 -모든 페이지에 다음의 search box가 존재 -검색어를 타이핑하면 관련 결과가 보여짐 - 만약 "view all results"를 클릭한다면 -> result page로 이동 - result page 안에는 group, contersations 등 카테고리 tab별 결과 게시 - advanced search => 상세 필터를 통해 검색물 필터 기능 제공 문제 - 1. search 기능을 더 추가로 개발해야하는지에 대한 여부 - 2. 어떤 식으로 기존 기능을 수정해야 가장 효율적인지 => 어떠한 방법을 통해 정량적으로 기존 검색기능의 만족도를 평가하고 개선점을 파악할 수 있는가? 1-2. 테이블 명세서 둘러보기 더보기 테이블1. use..
[Python] 구현 - 8979.올림픽(실5) / 다중조건 정렬 https://www.acmicpc.net/problem/8979 8979번: 올림픽 입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 www.acmicpc.net >>문제 포인트 - 금메달, 은메달, 동메달 순 내림차순 정렬 -동점자가 있을 때 rank를 갱신하지 않음 => 인접한 행과의 비교가 필수 ex) 2-3이 동점일때 => 1등 - 2등 -2등 -4등 => before행과 비교하여 같다면 임시저장소에 포인트를 쌓음 => before행과 비교하여 같지않다면 rank를 +1하고 누적되어있던 point를 같이 더하고 비워줌 >>풀이 ..
[Python] 구현 - 1138.한줄로 서기(실2) / 뒤집어 insert https://www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net >>문제포인트 키가 큰 사람 순서대로 위치관계를 파악하는 것이 중요 예를 들어 키가 가장 작은 사람이 내 왼쪽에 나보다 키가 큰 사람이 1명 있어요! 라고 말한다면 그게 누구인지 모름 그러나 키가 두번째로 큰 사람이 내 왼쪽에 나보다 키가 큰 사람이 1명 있어요! 라고 말한다면 누구인지 특정이 됨 따라서, 키가 큰 사람부터 위치관계를 정하는 것이 쉬울 것이라 판단 => 키가 큰 사람의 위치..
[Python] 구현-13335. 트럭(실1) /큐와 시뮬레이션 https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net >>문제 포인트 - 시간 단위 1씩 판단 - 큐를 통해 bridge와 truck 배열 형성 =>본 문제가 어려웠던 이유는 쉽게 풀어볼려고 그리디적으로 접근했기 때문이었다. => 하지만, 타임프레임 1초당 판단해야 하는 것들을 목록화하고 구현하는 문제였다. 먼저 예시를 통해 시간당 진행상황을 보자 하중 : 10 arrived | bridge(길이 2)..

티스토리툴바