본문 바로가기

분류 전체보기

 (125)
2230 수 고르기 https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 틀린 이유 투포인터의 범위 증감 방향을 잘못 설정. 정렬했기 때문에 인접한 원소가 가장 작은 차이를 가진다. 따라서 인접한 원소부터 범위를 늘려가면서 최적해를 찾아야 답을 찾을 수 있다. 문제 접근 N이 10만이기 때문에 완전탐색은 사용불가능. 차이가 최소인 경우를 찾기 위해 정렬이 필요하다. 차이를 비교하면서 탐색해야 하는데, 이 때 투포인터를 사용하여 인접한 원소가 가장 작..
15565 귀여운 라이언 https://www.acmicpc.net/problem/15565 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 투포인터라는 개념을 알고 있으면 쉽게 풀 수 있는 문제다. N이 10만이기 때문에 N^2의 탐색 방법을 사용하면 시간초과가 발생한다. 따라서 최대한 N에 가깝게 풀어야 한다. 이 문제에서는 범위를 최대한 넓게 탐색한 뒤에 조건을 만족한다면, 왼쪽부터 범위를 줄여가면서 최적해를 찾는다. 이 때, 범위를 1씩 줄이면서 답을 갱신하면 원하는 답을 얻을 수 있다. 정답 코드 더보기 import ja..
1138 한 줄로 서기 https://www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net 간단해보이지만 헷갈려서 결국 정답을 참고한 문제다. 문제의 핵심은 입력받은 상대 순서, 즉 자신의 왼쪽보다 키 큰 사람이 몇 명있는지이다. 상대 순서를 i라 해보자. 가장 큰 사람부터 줄을 서기 시작하면 항상 맨 처음선다. 이후 줄을 서는 사람의 i가 0인지, 1인지에 따라 먼저 선 사람의 왼쪽인지 오른쪽인지가 결정되는 것이다. 또한 그 다음 사람은 i가 0이면 맨 처음, 1이면 중간, 2..
오늘의 질문: jpql 프로젝션 대상이 둘 이상이면 반환 값을 어떻게 받나? 간단한거지만 개념이 헷갈려서 기록해두려 한다. SQL에서는 select 절에 여러 값을 반환받을 수 있다. 그렇다면 jpql에서는 어떻게 반환받아야 하나? 반환 값이 하나라면 select [변수명] from 객체 선언... 으로 간단하게 가져올 수 있는데 여러 개는 처음이라 헷갈렸다. 생각했던 방법은 크게 두가진데 첫 째 Query Projection용 DTO 클래스를 사용한다. jpa 강의에서 배운 방법이지만, Infra 영역이 DTO에 의존하게 되어 꺼려졌다. 뿐만 아니라 DTO 특성상 다른 레이어에 의존 관계가 생겨서 별로 좋지 못한 방법같았다. 둘 째 자바의 Object[] 타입으로 받는다. 참고: https://stackoverflow.com/questions/6877857/jpa-query-t..
2887 행성 터널 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 고찰: 처음엔 크루스칼 알고리즘을 수행하기 위해 단순히 행성끼리 간선을 모두 연결하여 정렬하면 되겠다라고 생각한 순간 메모리 초과가 떴다.. 행성의 최대 개수인 N이 10만인 것을 간과하고 N^2 으로 접근해서 그런 것 같다. 풀이: 문제의 조건 중 간선의 비용을 min (|x1 - x2|, |y1 - y2|, |z1 - z2|)로 계산한다는 것에 집중하자. 모든 ..
4485 녹색 옷 입은 애가 젤다지? https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 접근 방식은 최솟값은 갱신하면서 탐색하는 방향이라면 대부분 맞는 것 같다. 나의 방법은 Cost를 저장하기 위해 dist라는 2차원 배열을 선언하여 해결하였다. dist[nr][nc] > dist[r][c] + arr[r][c] => 다음 칸의 cost를 저장할 때 더 작은 값이라면 탐색한다. 정답코드 더보기 import java.io.BufferedReader; import j..
15971 두 로봇 https://www.acmicpc.net/problem/15971 15971번: 두 로봇 2018년 강원도에서 새로운 동굴이 발견되었다. 이 동굴에는 총 N개의 넓은 방이 존재하며 좁은 통로로 서로 연결되어 있는 것으로 밝혀졌다. N개의 방은 1번부터 N번까지의 번호를 붙여 1번 방, 2번 www.acmicpc.net 답을 도출하는 과정을 잘 이해하지 못하여 틀린 문제이다. 다른 사람의 코드를 참고하긴 했지만 여러모로 아쉬웠다. 내가 처음에 접근했던 방식은 로봇이 위치한 두 정점에서 각각 BFS를 수행하여 교차되는 지점들을 모두 찾아 경로의 합을 구하는 방식이었다. 그런데, 틀렸다고 나와서 당황했다;; 사실 정답은 최단 경로 가중치의 합에서 가장 긴 가중치만 빼주면 된다. 이를 위한 탐색 방법은 bfs..
코딩테스트 중간 점검 지금까지 여러 기업들의 코딩 테스트를 겪어보고 느낀 점, 보완해야할 점들을 정리해보고자 한다. 1. 문제 분석 능력이 부족한 것 같다. 문제 지문이 긴~걸 읽다보면 핵심이 무엇인지를 까먹을 때가 있다. 2. 구현 능력 이건 벼락치기 vs 꾸준히 문제 풀기 둘 중에 어떤게 시간대비 효율적인지 모루겠다.. 이번 라인 하반기 테스트에서 알고리즘은 그렇게 어렵지 않았는데 구현에서 발목을 잡힐 때가 생각 외로 많았다. 3. 알고리즘과 알고리즘의 연결 자주 출제되는 알고리즘 분류들 중에서 연결지어서 나오면 못 푸는 경향이 있다. e.g. , ,
오늘의 질문 : Java의 Enum은 왜 생성자가 있는가? 자바의 Enum엔 특이하게도 생성자가 있다. 내가 주로 다루던 C++과는 다른 사용법이다. 일반적으로 Enum의 사용법은 상수를 열거하여 표현해야 할 때 주로 사용한다. 연관있는 상수들을 응집시키지 않고 열거하기만 하면 소스코드가 지저분해지고, 가독성이 떨어지기 때문이다. 자바에서는 왜 Enum에 생성자를 넣었을까. 이유를 알아보기 위해 C++의 Enum을 살펴보자. C++에서는 Enum에 상수 값만 할당할 수 있다. enum Type { TYPE1 = 1, TYPE2, TYP3 } 그런데, 정수가 아닌 문자열을 할당하고 싶다면? enum TYPE { TYPE1 = 1, TYPE2, TYPE3 } String TypeConverter(Type type) { switch(type) { case TYPE.T..
오늘의 질문 : JPA 엔티티 수정 방식 Q. jpa에서 조회한 엔티티를 업데이트할 때 실무에선 어떤 방식으로 업데이트하시는지 궁금합니다. 1. 엔티티 내부에 id를 제외한 모든 파라미터를 받는 수정자 메서드를 생성 2. builder로 객체를 clone하고, 빌더를 이용한 수정자 메서드 생성 3. 업데이트할 필드의 내용으로 새 엔티티를 생성하고, id를 복사 불변, 신뢰성때문에 되도록이면 수정자 메서드를 넣지 않고, 식별자를 copy하여 객체를 새로 만드는 방식을 생각했었는데, 답변을 보니 생각이 달라졌다. 고찰 : 1. 도메인 로직에 수정 메서드를 넣고, 수정하는 책임을 지게 하는게 깔끔하다. 2. 불변이 꼭 만능은 아니며, jpa의 엔티티 논리적 동치관계는 ID로 하기 때문에, 굳이 새로만들어서 불변성 보장을 시도하지 않아도 된다. 3. ..

티스토리툴바