기록장

🌵 문제 분석https://www.acmicpc.net/problem/2823RxC 크기의 마을이 주어질 때 (X는 빌딩, .은 길)임의의 한 길에서 유턴하지 않고 그 위치로 돌아올 수 있는지 출력하라.돌아올 수 있다면 0, 돌아올 수 없다면 1 출력 입력:R CRxC크기의 마을 지도🌵 구현 아이디어모든 길에 대해 상하좌우로 2개 이상의 길이 연결되어있는지 확인한다. 예제1)5 5XX.XXX...X.....X...XXX.XX(2, 0), (4, 2), (2, 0), (2, 4)좌표는 인접한 곳에 1개의 길만 연결되어있으므로 다시 돌아올 수 없다. (막다른길) -> 1을 출력함 예제2)3 9...XXX....X.....X....XXX...이 경우는 모든 길의 인접한 곳에 2개 이상의 길이 연결되어있으므..

🌵 문제 분석https://www.acmicpc.net/problem/2659시계수란 1~9 중 중복 포함 4개의 숫자가 주어졌을 때 그 숫자를 시계방향으로 읽어 만들 수 있는 가장 작은 값이다. 주어진 시계수가 모든 시계수들 중에서 몇 번째로 작은 시계수인지 출력하라. 🌵 구현 아이디어1️⃣ 1111~9999로 만들 수 있는 모든 시계수를 구한다.1111부터 1씩 증가시키면서 9999까지 모든 네 자리 수에 대한 시계수를 구한 후 중복 없이 배열에 저장한다. 예를 들어 4265이 주어지면 4265, 2654, 6542, 5426 중에서 가장 작은 2654를 시계수로 배열에 저장한다.2️⃣ 구한 시계수들을 오름차순으로 정렬한다.3️⃣ 주어진 시계수를 구하고, 그 시계수가 몇 번째 위치인지 구한다. 문..

🌵 문제 분석https://www.acmicpc.net/problem/2012N명의 학생들의 예상 등수(A)와 실제 등수(B)의 차이의 총 합이 최소가 되도록 실제 등수를 매겼을 때불만도의 합을 출력하라. 입력 :N(학생 수)N개의 예상 등수🌵 구현 아이디어❎ 브루트 포스는 시간 초과브루트 포스로 탐색하면 등수 500,000개마다 500,000명의 학생 중 누가 가장 불만도가 작은지 검사해야 하고 시간 복잡도가 250,000,000,000 > 2억 이므로 2초 안에 연산 불가능하다. 뿐만 아니라 아래와 같이 실제 등수를 항상 불만도가 가장 낮은 학생에게 부여하게 되면 먼저 실제 등수가 부여된 학생들은 불만도가 최소가 될 수 있지만 앞에서 부여되고 남은 등수를 뒤에 탐색되는 학생들에게 매칭하게 되면 불..

🌵 문제 분석https://www.acmicpc.net/problem/48031. 노드 N개가 1개 이상의 간선으로 연결되어있고2. 임의의 두 정점에 대해서는 경로가 유일하다고 할 때모든 정점이 서로 연결되어 있는 그래프를 '연결 요소'라고 한다. 사이클이 없는 연결 요소의 개수가 T일 때T==0일 때 No trees.T==1일 때 There is one tree.T>1일 때 A forest of T trees.를 출력하라. 입력 : N(노드 개수) M(간선 개수)M개의 간선N==0, M==0일 때까지 위 입력을 받음🌵 구현 아이디어이중 연결리스트에 양방향으로 간선 정보를 저장한다.아직 방문하지 않은 모든 노드에 대하여 DFS 탐색을 한다.DFS 탐색 결과 사이클이 아니면 트리 하나로 센다.모든 노드..

🌵 문제 분석https://www.acmicpc.net/problem/1916출발 도시 번호, 도착 도시 번호가 A, B로 주어질 때 A에서 B까지 가는 데 드는 최소 비용을 출력하여라.입력 :N(도시의 개수)M(버스의 개수)a(출발 도시 번호) b(도착 도시 번호) w(버스 비용)...A(구하려는 출발 도시 번호) B(구하려는 도착 도시 번호)🌵 구현 아이디어도시 개수가 최대 1,000개 이므로 인접 행렬로 구현하면 공간 복잡도가 1,000,000*4byte=4MB 1️⃣ 인접 행렬을 간선 비용으로 채우기예제 입력 1 :581 2 21 3 31 4 11 5 102 4 23 4 13 5 14 5 31 5인접 행렬을 arr[출발 도시 번호][도착 도시 번호] = 간선 비용 으로 채운다.출발, 도착 도시..

1월, 2월 결과!1월은 9명 중 1등했고 2월은 17명 중 2등했다 ㅎㅎ(캡쳐를 못 해서 받은 교환권이라도..)

🌵 문제 분석https://www.acmicpc.net/problem/18352도시가 N개, 도로가 M개(단방향) 주어지고 도시 간의 거리는 모두 1이다.X에서 X로 가는 최단 거리는 항상 0이라고 가정한다. 도시 X에서 도달 가능한 모든 도시 중 거리가 K인 곳을 모두 출력하라.아래의 경우 1에서 출발하여 최단 거리가 2인 곳은 4밖에 없다.입력 :N(도시의 개수), M(도로의 개수), K(출발 도시의 번호)(M쌍의 인접한 도시)A1 B1A2 B2... 🌵 구현 아이디어1️⃣ 인접 리스트 만들기이중 연결 리스트를 만들어서 간선 정보를 저장한다. 4 4 2 11 21 32 32 412, 323, 43 4 간선 정보를 단방향으로 저장함2️⃣ 시작점을 X로 두고 BFS 탐색X에서 시작해서 나머지 도시들로..

🌵 문제 분석https://www.acmicpc.net/problem/11725숫자 N과 N-1개의 인접 노드 정보가 주어졌을 때1을 루트로 할 경우 2~N까지의 각 노드의 부모 노드가 누구인지 출력하는 문제이다.🌵 구현 아이디어71 66 33 54 12 44 71️⃣ 먼저 인접 노드를 저장한다.이중 연결리스트를 생성해서 인접 노드 정보를 저장한다.1 6이 입력값으로 들어오면 list.add(1)=6, list.add(6)=1 이런 식으로 양방향으로 참조할 수 있게 저장한다.(양방향으로 저장해야 루트부터 탐색 시 모든 노드를 방문할 수 있음)16, 42436, 541, 2, 75361, 3742️⃣ 인접 노드 리스트를 참고해서 루트(1)부터 탐색 시작, 부모 노드 구하기이해를 위해 인접 리스트를 시각..

🌵 문제 분석https://www.acmicpc.net/problem/2116N개의 주사위를 아래 주사위의 윗면, 위 주사위의 밑면이 맞닿는 곳의 숫자가 일치하게 일렬로 쌓는다.주사위를 쌓아서 만들어진 사각 기둥의 한 옆면의 합이 최대가 되도록 할 때, 한 옆면의 숫자의 합의 최댓값을 구하여라. 입력 :N(주사위 개수)N개의 주사위 전개도에 입력되는 숫자🌵 구현 아이디어1️⃣ 마주보는 면 저장주사위의 숫자 위치가 고정되어있기 때문에 마주보는 면은 항상 정해져있다. opposite[i] = j -> i의 마주보는 면은 j임을 저장2️⃣ 첫 번째 주사위의 윗면 결정첫 번째 주사위의 윗면은 6개 중 하나가 될 수 있으므로 6가지 경우에 대해 최댓값을 찾는다.3️⃣ 나머지 N-1개 주사위의 윗면 결정첫 번째..

🌵 문제 분석https://www.acmicpc.net/problem/1713N개의 사진틀에 추천받은 학생의 사진이 게시된다. 총 S번 추천이 이루어진 후 최종 후보가 누군지 출력하라.만약 자리가 없다면 추천 받은 횟수가 가장 적은(2명 이상이라면 추천받은지 더 오래된) 학생이 삭제되고, 그 자리에 게시된다. 이미 게시된 학생이 또 추천받으면 추천횟수 증가, 사진틀에서 삭제되면 추천횟수는 0이 됨입력 :N (사진틀 개수)S (총 추천 횟수)S개의 학생 번호🌵 구현 아이디어💡 전체 동작 설계사진틀을 List로 둔다.학생을 Student 객체로 두고 변수로 학생 번호(id), 추천 받은 횟수(cnt), 게시된지 얼마나 지났는지 나타내는 값(time)을 둔다.추천 받은 학생이 생기면 O(S)-> 추천 받..