본문 바로가기
반응형

분류 전체보기

 (135)
[BOJ](Python) 백준 9466번: 텀 프로젝트 문제 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 주제 방향 그래프 & DFS 시간 / 메모리 제한 3초 / 256MB 정답 비율 24.043% 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행한다. 프로젝트 팀원 수에는 제한이 없다. 모든 학생들이 동일한 팀의 팀원인 경우처럼 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택한다. 각자 단 한 명만 선택할 수 있다...
[BOJ](Python) 백준 5567번: 결혼식 문제 https://acmicpc.net/problem/5567 5567번: 결혼식 예제 1의 경우 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2, 3, 4 3명의 친구를 결혼식에 초대 www.acmicpc.net 주제 그래프 구현/순회 시간 / 메모리 제한 1초 / 128MB 정답 비율 44.052% 상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다. 상근이는 동기들의 친구 관계를 모두 조사한 리스트를 갖고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 ..
[BOJ](Python) 백준 1920번: 수 찾기 문제 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 주제 해시 테이블 시간 / 메모리 제한 1초 / 128MB 정답 비율 29.789% N개의 정수 A[1], A[2], ... , A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1
[BOJ](Python) 백준 1620번: 나는야 포켓몬 마스터 이다솜 문제 https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 주제 이진 탐색 시간 / 메모리 제한 2초 / 256MB 정답 비율 34.067% 입력 첫째 줄에는 도감에 수록된 포켓몬의 개수 N과 내가 맞춰야 하는 문제의 개수 M이 주어진다. 1 target: return binary_search(dic, target, start, mid - 1) else: return binary_search(dic, target, mid..
[휴학 중 코테 부수기] # 4. 그래프 탐색 알고리즘: DFS/BFS 동빈나의 이코테 강의를 듣고 작성한 포스트입니다. 탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다. 대표적인 그래프 탐색 알고리즘에는 DFS와 BFS가 있다. 이들은 코테에 자주 등장하고 중요한 알고리즘이다. DFS와 BFS를 이해하고 사용하기 위해 필요한 스택과 큐에 대해 공부한 후, DFS와 BFS를 배워보자. 스택 자료구조 먼저 들어온 데이터가 나중에 나가는 선입후출 형식 입구와 출구가 동일한 형태 ex) 박스를 쌓는 경우 DFS와 다양한 알고리즘에 사용된다. 스택 구현 예제 리스트 자료형으로 스택을 구현할 수 있다. # 스택 구현 예제 stack = [] # 삽입(append)과 삭제(pop) stack.append(5) stack.append(2) stack...
[휴학 중 코테 부수기] # 3. 구현(Implementation) 동빈나의 이코테 강의를 듣고 작성한 포스트입니다 구현이란 익히 쓰이듯이, 머릿 속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 모든 코테 문제가 구현이 필요한 셈이다. 그치만 흔히 알고리즘 대회에서는 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 구현 문제라고 한다. 문법적인 지식이 필요한 경우가 많다. 교재에 따라 구현 유형을 부르는 방법이 다양하지만, 코테에서 시뮬레이션 유형, 구현 유형, 완전 탐색 유형은 서로 유사한 점이 많다. 구현 유형의 예시는 이렇다. 알고리즘은 간단한데 코드가 지나치게 길어지는 문제 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제 적절한 라이브러리를 찾아서 사용해야 하는 문제 일반적으로 알..
[휴학 중 코테 부수기] # 2. 그리디 알고리즘 동빈나의 이코테 강의를 듣고 작성한 포스트입니다. 그리디 알고리즘(탐욕법) 현재 상황에서 지금 당장 좋은 것만 고르는 방법 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구 그리디 해법은 그 정당성 분석이 중요 현재 상황에서 단순히 가장 좋아 보이는 것을 반복적으로 선택하는 것으로 최적의 해를 구할 수 있는지 검토하는 과정이 꼭 필요함 정당성 분석 그리디 알고리즘 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 한다. 예시 문제 1 [문제 상황] 루트 노드부터 시작하여 다른 노드로 이동할 때, 거쳐 가는 노드 값의 합을 최대로 만들고 싶다. 최적의 해는 무엇인가? [문제 해결 아이디어] 1. 모든 경우를 다 따져보기 모..
[BOJ](Python) 백준 2075번 N번째 큰 수 문제 https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 주제 힙 시간 / 메모리 제한 1 초 / 12 MB 정답 비율 39.005% NxN의 표에 수 N^2개가 채워져 있다. 채워진 수의 모든 수는 자신의 한 칸 위에 있는 수보다 크다. N=5일 때의 예 12 7 9 15 5 13 8 11 19 6 21 10 26 31 16 48 14 28 35 25 52 20 32 41 49 이런 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. (표에..
반응형

티스토리툴바