본문 바로가기

전체 글

 (403)
백준 8901번 - 화학 제품 (Java) https://www.acmicpc.net/problem/8901 AB, BC, CA를 만들 수 있는 모든 경우의 수를 확인해봐야하기 때문에 이 문제는 완전탐색 문제로 분류된다.AB를 0개 만들었을 때, BC를 0개 만들었을 때 -> CA가 만들어지는 개수가 정해진다.그러므로 AB를 가능한 만큼 만들어보고 각 경우의 수를 만들어보면 된다. A = 4B = 3C = 5 가 있다고 가정하자.  AB 는 B가 3이므로 3개까지 만들 수 있다.AB의 개수가 0이면 BC는 3개를 만들 수 있다. B를 사용하지 않았기 때문이다. BC를 0개 만들었다면 CA는 4개BC를 1개 만들었다면 CA는 3개BC를 2개 만들었다면 CA는 2개BC를 3개 만들었다면 CA는 1개 만들어낼 수 있다.  그리고 AB를 만들어낼 수 있..
백준 2651번 - 자동차경주대회 (Java) https://www.acmicpc.net/problem/2651 그리디로 풀자니 이전의 값을 계속 다시 사용해야한다.완전탐색을하면 2^100 승으로 당연히 시간초과다. 그래서 이 문제는 다이나믹 프로그래밍을 사용해야한다. DP 문제들은 다 그렇지만 1차원으로 해결가능한지? DP배열에 무슨 값을 넣어야하는지? 가 중요하다. 그리고 DP값에는 거의 모든 문제에서 정답이 들어간다는 것을 다시 한 번 명심하자. 즉,  DP[N] = N 지점까지 최소 정비로 올 수 있는 경우가 된다. 정비를 받지 않고 한번에 오는 것이 당연히 시간적으로는 손해가 안난다. 4지점의 경우, 1,2,3 에서 4까지 올 수 있다. 그리고 1,2,3에서 4까지 올수 있는 경우의 수는 다음과 같다. 1. 정비를 받고 올 수 있음2. 올 ..
프로그래머스 - 후보키(C++) https://school.programmers.co.kr/learn/courses/30/lessons/42890# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 조합과 0123이 들어왔을 때 023을 찾아낼 수 있는가? 라는 문제와 같다. 그래서 각 튜플을 문자열을 이어붙이고 set을 사용해 유일성을 판단하고각 후보키들을 배열에 넣어놓고현재 후보키의 후보를 0123이 들어왔을 때  023을 가져와서 임시 배열의 0, 2, 3을 true로 만든다.그리고 0,1,2,3을 거쳐 임시 배열이 true인 것의 개수를 샌다. 만약 카운트의 수 = 지금 비교하고 있는 ..
백준 2212번 - 센서(C++) https://www.acmicpc.net/problem/2212이분탐색인가? 라는 생각이 들 수밖에 없는 문제였다. https://www.acmicpc.net/problem/1477 문제가 떠오르는 문제이기 때문이다. 1477번과 비슷하기도 하다. 만약 2212의 한 커버 거리의 최대나 최소를 구하라고 했다면 1477번 처럼 풀 수 있을 것이다. 이 문제는 시뮬레이션처럼 어디에 기지국을 설치할지 정하는 것이 아니라 각 센서 사이의 거리를 구해놓고 가장 먼 사이에다가 설치하면 되기 때문에 전체 값에서 그 값들을 빼주면 되는 문제였다. 정렬이던 그리디던 간에 아이디어를 떠올리지 못하면 매우 어려운 문제다. #include #include #include using namespace std;int main(..
Java로 문자열 xml 파일 파싱 xml 형태이지만 문자열로 저장된 코드에서 원하는 값을 파싱해 사용해야하는 상황이 발생했다. DocumentBuilderFactory factory = DocumentBuilderFactory.newInstance(); DocumentBuilder builder = factory.newDocumentBuilder(); Document document = builder.parse(new InputSource(new StringReader(xml.toString()))); document.getDocumentElement().normalize(); NodeList tagLis..
Spring Boot JPA - BufferedReader로 CSV 파일을 읽어 DB에 저장하기 BufferedReader자바에서 입출력을 빠르게 받을 때 많이 사용했던 버퍼리더, 정확히 버퍼 리더가 무엇인가버퍼란 어떤 데이터가 전송 될 때 일시적으로 저장되는 영역이다. (캐시와는 다르다.) 어떤 데이터들을 한 번에 묶어서 전송하기 때문에 전송이 빠르다. BufferedReader br = Files.newBufferedReader(Paths.get(filePath));map을 사용해 임시 값 저장csv파일은 ,로 구분된 정보를 엑셀 형태로 보여주는 파일이다. 그러니까 텍스트로 옮기면이름, 나이, 사는곳김, 20, 서울박, 21, 부산이런식으로 구성되어 있다. 버퍼리더로 값을 받으면 한 행씩 정보를 받지 열(col)씩 받지 않기 때문에 맨 위 헤더들을 key값으로 갖는 hashm..
코드 트리 - 마법의 숲(삼성 SW 역량테스트 2024 상반기 오후 1번 문제 C++) https://www.codetree.ai/training-field/frequent-problems/problems/magical-forest-exploration?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai 정말 삼성 문제 다운 문제이다. 코드트리에서 배정한 난이도는 골드3 인데 백준이었다면 골드4~5이지 않을까 생각된다. 까다로운 구현 + bfs 문제이다. 먼저 어떤 기능이 필요한지 정리해두고 그 기능을 어떻게 짜야할지 고민해야하는 문제다. 이걸 푸는데 순수시간으로 2~3시간 정..
백준 16235 나무 재테크(C++) https://www.acmicpc.net/problem/16235 구현 자체도 정신을 똑바로 차려야하고 0.3초라는 매우 적은 시간 제한으로 인해 최적화를 잘 해줘야했다. 각 땅의 상황을 계절에 맞게 조절하는 것이 관건인 문제였다. 그리고 한 타일에 나무가 여러그루를 잘 컨트롤해줘야 했다. 나의 경우 2차원 자료구조를 사용하기 싫어서 1차원으로 사용후 x, y 좌표를 변화해주는 작업을 했는데 지금 생각하니 굳이 필요없는 작업인 것 같다. 이 문제에서 핵심은 N  조건에서 여러 나무가 있다면 나이가 가장 어린 순서대로 처리해주어야하기 때문에 처음엔 우선순위 큐를 사용했다. 예제는 모두 통과했지만 43퍼센트에서 시간초과가 발생했다. 그리고 질문게시판과 구글링을 통해 우선순위큐가 아닌 덱이 답이라는 것을 알..

티스토리툴바