공부하는 사람

https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net set을 이용하면 쉽게 풀 수 있습니다 주의할 점은 m개의 문자열중에 중복이 있을 수 있다는 점입니다 #include #include #include #include #include #include using namespace std; int main() { int n,m; cin>>n>>m; unordered_set s; for(int i=0; i>str; s.i..

https://www.acmicpc.net/problem/22942 22942번: 데이터 체커 데이터가 조건에 맞는다면 YES, 조건에 만족하지 않는다면 NO를 출력한다. www.acmicpc.net 접근법 생각하기가 어려운 문제였습니다. 입력이 최대 20만이어서 brute force로는 시간초과가 분명하기에 다른 방법을 찾다가 알고리즘 분류가 자료구조이기에 스택을 떠올릴 수 있었습니다. 알고리즘 분류를 몰랐다면 떠올리지 못했을것 같네요 .,. 풀이 방법은 이렇습니다. 1. x좌표, isOpen, 원의 id를 담는 구조체를 만듭니다 2.입력을 받아 Point로 만들어 vector에 넣습니다 3. x좌표를 기준으로 vector를 정렬합니다 4.vector를 탐색하면서 isOpen 이 참이면(원의 왼쪽 좌표..

https://school.programmers.co.kr/learn/courses/30/lessons/49191 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 그래프 문제였습니다. 아이디어 떠올리기도 어렵지 않고 구현도 어렵지 않은 무난한 문제였습니다 풀이 방법을 보면 우선 이겼을때와 졌을때 상황을 나눴습니다 이긴 경우 -> A가 B를 이기고 B가 C를 이겼다면 A는 C를 이깁니다. 진 경우 -> B가 A를 이기고 C가 B를 이기면 C가 A를 이깁니다 위 로직을 구현한 것이 whenWin, whenLose 함수입니다. 구현한 함수들을 모든 선수들에 대해..

https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 이분 탐색 문제입니다 입력으로 주어지는 최대 집 개수가 20만개이므로 일반적인 방법으로는 시간초과가 날 것이기에 이분탐색으로 접근해봤습니다 우선 집 좌표의 입력이 오름차순으로 주어지지 않으므로 정렬한 후 lo에는 최소 거리 1 hi에는 최대 거리인 마지막 집 - 처음 집을 넣어주고 이분탐색을 시작합니다. 이분탐색 값은 가장 인접한 공유기 사이의 ..

https://school.programmers.co.kr/learn/courses/30/lessons/43236 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이전 포스팅인 https://kuk6933.tistory.com/148 요 문제를 풀었던 덕에 더 빠르게 감 잡을수 있었습니다 이 문제가 이분탐색 항목에 있었기에 이분탐색을 적용했던거지 쌩으로 나오면 과연 이분탐색을 생각해낼 수 있었을까 하는 생각이 들었습니다 우선 출발점과 도착점도 고려해줘야 하므로 rocks에 넣고 시작했습니다. 그리고 정렬되어 있어야 이분탐색이 가능하므로 정렬해줍니다 이제 이..

https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이분 탐색을 이렇게 쓸 수 도 있구나 하고 느끼게 해준 문제입니다 우선 입력을 보면 최대 10억명, 최대 10억분입니다. 일반적인 접근으로는 시간초과가 날 것이고 이분 탐색으로 풀어야겠다고 생각했습니다 풀이 방법은 우선 times를 정렬합니다 그리고 lo에는 최솟값 1, 그리고 hi에는 가장 느린 심사대에서 모든 인원을 처리하는 경우 걸리는 시간을 넣어줍니다 이후에는 이분탐색을 진행하면서 특정 시..

https://school.programmers.co.kr/learn/courses/30/lessons/42897 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제의 포인트는 마을의 집들이 동그랗게 배치되어 있다는 것입니다 사실 순환구조가 아니라면 DP로 쉽게 풀 수 있는 문제입니다. 풀면서 고민한 점은 0번째 집과 마지막 집의 관계였고 이를 풀어내기 위해 두가지 방법을 생각했었습니다 1. dp vector를 pair로 만들어서 첫 번째 집을 털었는지 표시하기 2. 첫번째 집을 제외하고 계산, 마지막 집을 제외하고 계산해서 둘 중 더 큰 값을 retur..

https://school.programmers.co.kr/learn/courses/30/lessons/42884 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr Greedy 항목인걸 알고 풀었음에도 어떻게 접근하는지를 생각하는데 어려웠습니다. 포인트는 카메라가 설치되는 위치입니다. 카메라는 무조건 진출 시점에 설치되어야 합니다. 진출 시점에 카메라를 설치하는 방법이 가장 많은 범위를 커버할 수 있게됩니다. 에를 들면 첫 번째 경로가 5~ 10일 때 10에 설치해야 두번째 경로의 시작이 10일 경우까지 커버할 수 있게 되는 것입니다. 8에 설치하면 9, 1..