문제 https://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 모든 사람은 비어있는 자리 중 번호가 가장 작은 자리에 앉아야 한다. 다음과 같은 이용 규칙으로 모든 사람이 기다리지 않는 컴퓨터의 최소 개수와 자리별로 몇 명의 사람이 사용했는가를 구하는 문제였다. 문제 풀이 처음에 비어있는 자리 중 번호가 가장 작은 자리에 앉는다는 규칙을 제대로 보지 않아서 틀렸었다. ..
문제 https://www.acmicpc.net/problem/1765 1765번: 닭싸움 팀 정하기 1번 학생 혼자 팀, 2, 4, 6번 학생 셋이서 팀, 3, 5번 학생 둘이서 팀일 때, 팀의 개수가 최대이다. www.acmicpc.net 내 친구의 친구는 내 친구이다. 내 원수의 원수도 내 친구이다. 해당 조건에 맞게 짠 가장 많은 팀 수를 구하는 문제였다. 문제 풀이 Union-Find 알고리즘을 이용해 풀었다. 친구와 원소 그래프 벡터를 따로 만들었고 조건에 맞게 makeUnion 해주는 과정을 반복했다. 친구끼리는 makeUnion을 해줬으며 원수일 경우에는 해당 원수의 원수 리스트 모두에 대해 makeUnion을 해줬다. team 개수를 찾을 때에는 set을 이용해서 다른 parent를 가진..
문제 https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 체스판에 놓을 수 있는 비숍의 최대 개수를 구하는 문제였다. 문제 풀이 시간 제한이 10초나 되는 문제였지만 완탐으로 하니 시간 초과가 나왔다. 어떻게 줄여야 할지 감도 잡히지 않아 검색해 보니 비숍은 2가지 경우에는 절대 서로를 잡을 수 없다고 했다. 아래와 같이 o인 칸과 x인 칸은 아예 다른 경우로 생각하면 된다. 원래는 전체 칸을 다 살펴야 했지만 나눠 생각하면 o인 칸, x인 칸을 따로 생각..
문제 https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 얼리 아답터가 아닌 사람은 자신의 친구가 모두 얼리 아답터인 경우에 아이디어가 전파되는 상황에서 얼리 아답터의 최소 수를 구하는 문제였다. 문제 풀이 처음에 u - v의 관계가 항상 u가 부모, v가 자식이라고 생각하고 단방향 그래프를 만들어 풀었는데 그게 아닐수도 있었다. 처음의 풀이는 루트 노드를 찾은 다음 레벨 별 순회를 하며 해당 서브트리의 dp를 갱신해줬다. 하지만 무방향 그래..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/1831 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr N을 만들 수 있는 경우의 수를 구하는 문제였다. *++이 3단고음이고 *은 3을 곱하기, +는 1을 더하기이다. 3단고음 중간에 3단 고음을 실행할 수 있다. 문제 풀이 처음에 1에서 시작해 N을 만드는 방법으로 했는데, 시간 초과가 계속 났고 풀이를 참고해서 다시 풀었다.. N부터 시작해서 1까지 도달하게 했고, *는 3으로 나누기, +는 3으로 나눈 나머지를 빼도록 했다. 3으로 나눠진다..
문제 https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 게임을 진행하면서 움직일 수 있는 동전의 최대 횟수를 구하는 문제였다. 문제 풀이 많은 시행착오가 있었고, 결국 다른 블로그를 참고해서 해결했다. 처음에는 단순히 백트래킹을 이용했는데, 6%에서 시간 초과가 나타났다. 이를 해결하기 위해서 좌표와 횟수, 방향 정보를 우선순위 큐에 넣어 bfs를 돌렸는데 해결되지 않는 경우가 있었다. 그리고 map의 각 칸에 set을 만들어 이전에 방문한 적이..
문제 https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 트리의 각 레벨의 양 끝 노드간의 거리 중 최댓값을 구하는 문제였다. 문제 풀이 처음에는 트리 노드에 달려 있는 노드들의 합으로 위치를 계산하려고 했는데, 중위순회를 하면 순회하는 순서가 위치가 될 것 같아서 다시 풀었다. 1번 노드의 parent를 계속 거슬러 올라가 루트 노드를 찾는다. 루트노드에서부터 중위순회를 돌려 각 노드의 위치를 찾는다. 트리를 레벨 별로 순회를 ..
제네릭을 사용하면 타입을 컴파일러에 알려주고 컴파일러가 알아서 형변환 코드를 추가해 준다. 5장은 이런 제네릭을 사용할 때 주의사항과 팁을 알려준다. 용어 정리 제네릭 타입 제네릭 클래스/인터페이스 : 클래스와 인터페이스 선언에 타입 매개변수가 쓰인다. (List) 제네릭 클래스/인터페이스를 통틀어 제네릭 타입이라 한다. 매개변수화 타입 각 제네릭 타입은 일련의 매개변수화 타입을 정의한다. 이름 (List) 로 타입 제네릭 타입을 하나 정의하면 로 타입도 함께 정의된다. 로 타입은 제네릭 타입에서 타입 매개변수를 전혀 사용하지 않을 때를 말한다. (List에서 List) 타입 선언에서 제네릭 타입 정보가 전부 지워진 것처럼 동작한다. (제네릭 없던 코드와 호환되기 위함) 한글 용어 영문 용어 예 매개변수..