전체 글
![[FlipKart 인터뷰] 금광](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdna%2FctcoDX%2FbtqWVQ7kTJt%2FAAAAAAAAAAAAAAAAAAAAAPBoHOJF0_mU8GmL-gc28lPXIhiDgEUKGRxu46SO9yaX%2Fimg.png%3Fcredential%3DyqXZFxpELC7KVnFOS48ylbz2pIh7yKj8%26expires%3D1764514799%26allow_ip%3D%26allow_referer%3D%26signature%3Dg9HI0AxStQpDjef%252B9Vbrrgom%252FMg%253D)
[FlipKart 인터뷰] 금광
초기접근 점화식 세우는 과정은 어렵지 않았다. 각 단계는 전 단계에서 올 수 있는 경우중에 가장큰 수 + 해당 금광수 이다. 이것을 점화식으로 나타내면 d[i][j] = max(d[i-1][j-1], d[i][j-1], d[i+1][j-1]) + data[i][j] 이다. 여기서 가장 위쪽과 아래쪽은 전단계에서 오는 경우의 수가 1개가 적다. 이것을 따로 구현하는 것 보다 data와 d 위아래에 0을 채워놓으면 훨씬 더 구현하기 쉽다. 해결 아이디어 1. 점화식 : d[i][j] = max(d[i-1][j-1], d[i][j-1], d[i+1][j-1]) + data[i][j] 2. 쉽게 구현하기 : 위아래에 0을 채워놓으면 훨씬 더 구현하기 쉽다. 정답코드 tc = int(input()) for t i..
EP9. 프록시와 연관관계 관리
프록시 em.getReference() : 데이터베이스 조회를 미루는 가짜(프록시) 엔티티 객체 조회 실제 클래스를 상속받아 만들어져서 모양이 같다. 그래서 사용자입장에선 그냥 진짜인지 프록시인지 구분하지 않고 사용할 수 있다. 프록시 초기화 프록시 객체에서 메소드 하나를 호출하면 영속성 컨텍스트가 DB를 조회해 실제 엔티티를 생성한다. 그리고 프록시 객체는 실제 엔티티를 가리킨다. 프록시 특징 프록시객체를 초기화할때 프록시객체가 실제 엔티티로 바뀌는게 아니다. 실제 엔티티에 접근이 가능한 것이다. 실제 엔티티와 프록시끼리 타입비교시에 ==비교가 안되고 instance of 로 비교해야한다. (실제 엔티티가 아니라서 !) 프록시가 언제들어올지 모르기때문에 엔티티끼리 비교할땐 instance of 비교로 ..
다이나믹 프로그래밍 문제접근
DP조건에 맞는지 확인하는 방법 1. 큰 문제를 작은문제로 나눌 수 있다. 2. 동일한 작은 문제를 반복적으로 해결한다. 처음에 딱 문제를 볼때 접근해야하는 과정 1. 그리디, 구현, 완전탐색인지 확인한다 2. 방법이 떠오르지 않으면 DP 조건을 확인해본다. 3. 재귀로 비효율적인 완전탐색을 구현해보고 4. 작은 문제로 큰 문제 해결이 가능하면 DP로 코드개선을 한다. 일반적인 코테의 DP문제는 기본유형으로 낸다. = 점화식만 세우면 구현은 쉽다.
EP8. 고급 매핑
상속관계 매핑 조인전략 단일테이블전략 구현클래스마다 테이블전략 어떤 전략이든을 선택하든 객체는 똑같이 구현된다. 하지만 DB 설계에서는 전략에따라 테이블 구성이 달라진다. 주요 어노테이션 @Inheritance(strategy = InheritanceType.XXX) JOINED : 조인전략 SINGLE_TABLE : 단일테이블전략 TABLE_PER_CLASS : 구현클라스당 테이블 전략 @DiscriminatorColumn(name='DTYPE') : DTYPE 부분 컬럼 이름 지정 가능 @DiscriminatorValue("XXX") : DTYPE부분 도메인 이름 지정 가능 조인전략 테이블 ITEM 테이블이 존재한다. 그리고 각 ALBUM, MOVIE, BOOK 테이블이 존재하고 ITEM 테이블을 상..
![[카카오코테] 가사 검색](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdna%2FztMSZ%2FbtqWjqiKtkm%2FAAAAAAAAAAAAAAAAAAAAAKYxxxqdGslcGyqtL7PbH4mhVyV_RZcYUm10C7UIMWGO%2Fimg.png%3Fcredential%3DyqXZFxpELC7KVnFOS48ylbz2pIh7yKj8%26expires%3D1764514799%26allow_ip%3D%26allow_referer%3D%26signature%3D9JLz6lBjnR4vOW9Z3P1uC3nvP5I%253D)
[카카오코테] 가사 검색
문제 설명 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 친구들로부터 천재 프로그래머로 불리는 프로도는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다. 그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "fro??"는 "frodo", "front", "frost" 등에 매치되지만 "frame", "frozen"에는 매치되지 않습니다. 가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 qu..
EP7. 다양한 연관관계 매핑
연관관계 매핑시 주의할 점 다중성 단방향, 양방향 연관관계의 주인 다중성 다대일 : 중요 일대다 : 잘 안씀 일대일 : 별로 안씀 다대다 : 아예 안씀 단방향, 양방향 테이블 : 외래키 하나만 있어도 가능하니까 방향의 개념이 없다. 객체 : 한쪽에서 다른쪽을 보려면 참조를 해야한다. 그래서 방향이 있다. (사실 양방향은 서로 단방향이 2개 있는 것이다.) 연관관계의 주인 외래키가 있는 곳 다양한 연관관계 매핑 방법 다 대 일 : @ManyToOne 단방향 외래키가 있는 곳에 참조를 넣고 매핑시킨다. 코드 Member @ManyToOne @JoinColumn(name = "TEAM_ID") private Team team; 양방향 다대일 관계에 일대다를 추가한 것이 양방향이다. (추가해준다해도 테이블에 영..
[백준 2110] 공유기 설치
문제 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. 입력 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는..