어흥

문제 링크: https://www.acmicpc.net/problem/22116 22116번: 창영이와 퇴근 A1,1에서 AN,N까지, 경로상의 최대 경사의 최솟값을 출력한다. www.acmicpc.net 1. 주의할 점 - 여러가지 푸는 방식이 존재하지만, 1씩 증가시키면서 10억까지 테스트 → TLE 발생 2. 구현 - BFS+이분탐색을 통해 차이가 Mid이하라면 전진이 가능하다고 판단 - L=0, R=10억, Result = R-L로 초기화 하고 이분탐색을 시작한다 - Mid = L+(R-L)/2를 통해 Mid값을 갱신하고, BFS()가 가능하면 Result의 값도 갱신한다 import java.util.*; import java.lang.*; import java.io.*; class Main {..

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/81303 코딩테스트 연습 - 표 편집 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO" programmers.co.kr 1. 주의할 점 - 어렵다... 많이 어렵다(이전 인턴 문제에 비해 난이도가 급 상승했다) - 세그먼트 트리 or 리스트 or STL에 대한 이해도가 높은 해결 할 수 있다 2. 구현 - 세그먼트 트리 or 리스트로는 아직 풀어보지 않아서 Set을 통해 해결했다(조만간 세그먼트 트리, 리스트로도 풀어..

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 1. 주의할 점 - BFS를 통해 해결하며, 무엇을 기준으로 수행 할 것인지 ..

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/81301 코딩테스트 연습 - 숫자 문자열과 영단어 네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다. 다음은 숫자의 일부 자 programmers.co.kr 1. 주의할 점 - 딱히 없다... 2. 구현 - 여러 가지 방법이 존재한다. Map을 통해 저장&비교, Substring 그리고 나와 같은 풀이 - 만약 C가 숫자라면 Str에 붙이고, 영어라면 0~9까지 앞글자를 비교하여 해당 숫자를 찾은 후, i의 값을 변경시킨다. 이때, 첫 글자가 같은 숫자가 있으므로 이 경우에는 2번째 글자까지 ..

문제 링크: https://www.acmicpc.net/problem/1662 1662번: 압축 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이 www.acmicpc.net 1. 주의할 점 - 괄호에 대한 처리 - 문자열을 복원 v.s 길이만 구하기 2. 구현 - 문자열을 복원하지 않고 길이만 구해도 되므로, 길이만 구하여 메모리 또한 아낄 수 있도록 한다. 다만, 구현이 좀 더 복잡 할 수 있다 - Stack 2개를 이용하여 해결한다 #예시 234(10) - Len 스택에는 '(' 괄호가 나오기 전의 숫자를 제외하고 계산된 길이. 위의 예시에선 '..

문제 링크: https://www.acmicpc.net/problem/17616 17616번: 등수 찾기 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 세 정수 N, M, X가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 105, 1 ≤ M ≤ min(N(N-1)/2, 5×105), 1 ≤ X ≤ N) . 다음 M 줄에는 각각 두 정수 A, B가 주어 www.acmicpc.net 1. 주의할 점 - N≤10^5이므로 간선들의 정보를 나타내는 2차원 배열을 사용하지 않는다 2. 구현 - 가장 높은 등수는 1+ (해당 학생보다 잘 본 학생 수) - 가장 낮은 등수는 전체 학생수 - (해당 학생보다 못 본 학생 수) - Check[][2] 배열을 통해 각 Node를 방문했는지 검사한다([][0]: 정방..

문제 링크: https://www.acmicpc.net/problem/2637 2637번: 장난감조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 1. 주의할 점 - 위상정렬로 접근한다 - 필요한 물품의 개수를 List 형태로 담지 않는다 → 메모리 초과 회피 2. 구현 - Info 형태의 구조체를 이용하여 A의 물건을 만들기 위해 Idx번째 물건이 Val만큼 필요하다는 것을 나타낸다 - Need[] 배열을 통해 필요한 총 물건의 수를 저장한다 - Conn[] 배열을 통해 연결된 상위부품의 수를 나타낸다..

문제 링크: https://www.acmicpc.net/problem/11562 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 1. 주의할 점 - 매 쿼리마다 통행을 바꿔야하는 횟수를 구하지 않는다 2. 구현 - Arr[][] 배열을 통해 간선에 대한 정보를 받으며, Arr[a][b]는 a->b로 가기 위해 바꿔야 하는 도로의 수를 저장한다 - Arr[][] 배열을 초기화하고, 입력받을 때 단방향인 경우에는 0,1을 저장하고 양방향인 경우에는 0,0을 저장한다 - 플로이드 와샬 알고리즘을 통해 Arr[][]..