from collections import deque
import sys
input = sys.stdin.readline
T = int(input().strip())
for \_ in range(T):
m, n, k = map(int, input().strip().split()) # 배추밭의 가로, 세로, 배추가 심어져 있는 위치의 개수
farm = [[0]*m for _ in range(n)]
for _ in range(k):
x, y = map(int, input().strip().split())
farm[y][x] = 1
visited = [[False]*m for _ in range(n)]
answer = 0
dx = [-1,1,0,0]
dy = [0,0,-1,1]
def bfs(y,x):
q = deque()
q.append([y,x])
while q:
y, x = q.popleft()
visited[y][x] = True
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0<= nx <m and 0<= ny <n:
if farm[ny][nx] == 1 and visited[ny][nx] == False:
visited[ny][nx] = True
q.append([ny,nx])
for j in range(n):
for i in range(m):
if farm[j][i] == 1 and visited[j][i] == False:
visited[j][i] = True
bfs(j,i)
answer +=1
print(answer)
1. 아이디어
- bfs
- dfs
2. 복잡도
- O(V+E): 2000 >> 가능
- V : 1000
- E : 1000
3. 자료구조
- 그래프: int[][]
- 방문기록: bool[][]
해결 코드
from collections import deque
import sys
input = sys.stdin.readline
n,m,v = map(int, input().strip().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
v1, v2 = map(int, input().strip().split())
graph[v1].append(v2)
graph[v2].append(v1)
for e in graph:
e.sort()
visited_b =[False]*(n+1)
visited_d =[False]*(n+1)
def dfs(start):
visited_d[start] = True
print(start, end=' ')
for i in graph[start]:
if not visited_d[i]:
dfs(i)
def bfs(start):
q = deque([start])
visited_b[start] = True
while q:
n = q.popleft()
print(n, end=' ')
for i in graph[n]:
if not visited_b[i]:
visited_b[i] = True
q.append(i)
dfs(v)
print()
bfs(v)
1. 아이디어
- 인접한 픽셀의 색이 같은 경우 dfs
- 방문하지 않은 노드에 대하여 dfs 반복하여 모든 그룹 카운팅
- 적록색맹의 경우 R,G를 통일하여 같은 방식으로 그룹 탐색
2. 복잡도
- O(n*2)
3. 자료구조
- 재귀, 리스트
해결 코드
import sys
sys.setrecursionlimit(10 ** 6) # 재귀 최대 깊이 설정( 파이썬의 재귀 최대 깊이의 기본 설정이 1,000회 이기 때문에 추가 필요)
input = sys.stdin.readline
n = int(input().rstrip())
pic = [list(input().rstrip()) for _ in range(n)]
visited=[[False]*n for _ in range(n)]
dxdy = [[-1,0],[1,0],[0,-1],[0,1]]
rg_y_cnt, rg_n_cnt = 0, 0
# 색상이 같은 경우 dfs하여 그룹 방문처리
def dfs(x,y):
# 현재 색상 좌표를 방문
visited[x][y]= True # 방문처리
current_color = pic[x][y]
for dir in dxdy: # 상하좌우 방문
nx,ny = x+dir[0],y+dir[1]
if 0<= nx <n and 0<= ny <n: # 범위 내에 있고
if visited[nx][ny]==False: # 미방문인 경우
if pic[nx][ny] == current_color: # 현재 좌표의 색상과 상하좌우 좌표 색상이 같으면 끝까지 탐색
dfs(nx,ny)
# 미방문인경우 dfs하여 그룹 탐색
for i in range(n):
for j in range(n):
if visited[i][j]==False:
dfs(i,j)
rg_y_cnt+=1
# 적록색맹의 경우 R,G 구분 못 하므로 G로 통일
for i in range(n):
for j in range(n):
if pic[i][j]=='R':
pic[i][j]='G'
# 방문처리 초기화
visited = [[False]*n for _ in range(n)]
for i in range(n):
for j in range(n):
if visited[i][j]==False:
dfs(i,j)
rg_n_cnt+=1
print(rg_y_cnt,rg_n_cnt)
1. 아이디어
- 최단거리 탐색 문제
- BFS는 현재 노드에서 가까운 곳부터 찾기 때문에 경로 탐색 시 첫번째로 찾아지는 해답이 최단거리임을 보장
- 상하좌우 모두 탐색
- 상하좌우 좌표가 미로의 범위 밖 or 0이면 탈락
2. 복잡도
- 상하좌우 BFS O(n)
3. 자료구조
- 리스트, 큐
해결코드
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split()) # n줄, 길이 m짜리 입력
maze = list(list(map(int,' '.join(input()).split())) for _ in range(n)) # ' '.join(input()) 입력된 문자열을 ' '간격을 하나의 문자열로 반환
# 이동
dx = [-1,1,0,0]
dy = [0,0,-1,1]
q = deque([(0,0)])
result = 0
while q:
x,y=q.popleft()
for i in range(4): # 상하좌우 방문
nx,ny=x+dx[i],y+dy[i]
if 0<=nx<n and 0<=ny<m: # 미로의 범위내에 있고
if maze[nx][ny]==1: # 다음이 1이라면
#방문처리
maze[nx][ny]=maze[x][y]+1 # 탐색하면서 미로에 이동거리 업데이트
q.append((nx,ny)) # 방문 노드
print(maze[n-1][m-1]) # 도착 좌표 이동거리 출력
널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.
배열에 자연수 x를 넣는다. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다.
입력
첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다.
출력
입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력하면 된다.
예제 입력 1
13
0
1
2
0
0
3
2
1
0
0
0
0
0
예제 출력 1
0
2
1
3
2
1
0
0
해결 코드
'''
1. 아이디어
-x 로 heappush 하여 최대 힙을 만들어서 출력한다
2. 복잡도
O(logn) 복잡도로 출력, O(n)회
3. 자료구조
- Heap
'''
import heapq
import sys
input = sys.stdin.readline
n = int(input())
heap = []
heap_length = 0
for _ in range(n):
x = int(input())
if x == 0:
if heap_length == 0:
print(0)
else:
print(-heapq.heappop(heap)) # -x 로 추가하여 -를 붙여 출력
heap_length = len(heap)
else:
heapq.heappush(heap, -x) # 힙에 원소를 추가할 때 -x로 추가 하여 최대값 정렬
heap_length = len(heap)
널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.
배열에 자연수 x를 넣는다. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다.
입력
첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 231보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다.
출력
입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.
예제 입력 1
9
0
12345678
1
2
0
0
0
0
32
예제 출력 1
0
1
2
12345678
0
해결코드
import heapq
import sys
input = sys.stdin.readline
n = int(input())
heap = []
heap_length = 0
for _ in range(n): # 1. 배열에 자연수 x를 넣는다.
x = int(input())
if x == 0: # x가 0이라면
if heap_length == 0: # 배열이 비었으면 0 출력
print(0)
else: # 있는 경우, 가장 작은 값 출력
print(heapq.heappop(heap))
heap_length = len(heap)
else:
heapq.heappush(heap, x)
heap_length = len(heap)
자바 개발자들의 필!수! 라이브러리 롬복, 롬복이란 무엇인지와 어떻게 사용하는지 알아보자.
롬복은 자바 개발할 때 자주 사용하는 코드 Getter, Setter, 기본생성자, toString 등을 어노테이션으로 자동 생성해 줍니다.
인텔리제이에서 프로젝트에 롬복 추가
Build.gradle에 코드 추가
compile('org.projectlombok:lombok')
Gradle 새로고침하여 라이브러리(의존성) 추가
Lombok 플러그인 다운로드 및 인텔리제이 재시작
롬복에 대한 설정 팝업 클릭 or [Preferences > Build,... > Compiler > Annotaion Processor]에서 Enable annotaion processing 체크
롬록으로 리팩토링하기
Hello Controller 코드 롬복으로 전환하기
web 패키지에 dto 패키지 추가
모든 응답 Dto를 관리
Hello ResponseDto 생성
package com.choee.service.springboot.web.dto;
import lombok.Getter;
import lombok.RequiredArgsConstructor;
@Getter
@RequiredArgsConstructor
public class HelloResponseDto {
private final String name;
private final int amount;
}
@Getter
선언된 모든 필드의 get 메소드를 생성해 준다.
@RequiredArgsConstructor
선언된 모든 final 필드가 포함된 생성자를 생성해 준다.
final이 없는 필드는 생성자에 포홤되지 않는다.
Dto에 적용된 롬복이 잘 작동하는지 테스트 코드 작성
package com.choee.service.springboot.web.dto;
import org.junit.Test;
import static org.assertj.core.api.Assertions.assertThat;
public class HelloResponseDtoTest {
@Test
public void 롬복_기능_테스트() {
// given
String name = "test";
int amount = 1000;
// when
HelloResponseDto dto = new HelloResponseDto(name, amount);
// then
assertThat(dto.getName()).isEqualTo(name);
assertThat(dto.getAmount()).isEqualTo(amount);
}
}
assertThat
assertj라는 테스트 검증 라이브러리의 검증 메소드
검증하고 싶은 대상을 메소드 인자로 받는다.
메소드 체이닝이 지원되어 isEqualTo와 같이 메소드를 이어서 사용 가능
isEqualTo
assertj의 동등 비교 메소드
assertThat에 있는 값과 isEqualTo의 값을 비교해서 같을 때만 성공
Junnit과 비교하여 assertj의 장점
CoreMatchesrs와 달리 추가적으로 라이브러리가 필요하지 않다.
-> Junit의 asserThat을 쓰게 되면 is()와 같이 CoreMatchers 라이브러리가 필요하다.
자동완성이 좀 더 확실하게 지원된다.
-> IDE에서 CoreMatcher와 같은 Matcher 라이브러리의 자동완성 지원이 약하다.
!트러블슈팅!
문제: 그레이들 5에서 롬복을 비롯해서 Querydsl 등의 플러그인 설정 방법 변경
해결: build.gradle 의존성에 annotationProcessor('org.projectlombok:lombok') 추가
비고: gradle 5 이상부터 어노테이션을 구별해서 추가해야 한다.
HelloReponseDto를 사용하여 HelloController에 코드 추가
package com.choee.service.springboot.web;
import com.choee.service.springboot.web.dto.HelloResponseDto;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RequestParam;
import org.springframework.web.bind.annotation.RestController;
@RestController
public class HelloController {
@GetMapping("/hello")
public String hello() {
return "hello";
}
// 추가된 부분
@GetMapping("/hello/dto")
public HelloResponseDto helloDto(@RequestParam("name") String name,
@RequestParam("amount") int amount) {
return new HelloResponseDto(name, amount);
}
}
package com.choee.service.springboot.web;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.boot.test.autoconfigure.web.servlet.WebMvcTest;
import org.springframework.test.context.junit4.SpringRunner;
import org.springframework.test.web.servlet.MockMvc;
import static org.hamcrest.Matchers.is;
import static org.springframework.test.web.servlet.request.MockMvcRequestBuilders.get;
import static org.springframework.test.web.servlet.result.MockMvcResultMatchers.content;
import static org.springframework.test.web.servlet.result.MockMvcResultMatchers.jsonPath;
import static org.springframework.test.web.servlet.result.MockMvcResultMatchers.status;
@RunWith(SpringRunner.class)
@WebMvcTest(controllers = HelloController.class)
public class HelloControllerTest {
@Autowired
private MockMvc mvc;
@Test
public void hello가_리턴된다() throws Exception {
String hello = "hello";
mvc.perform(get("/hello"))
.andExpect(status().isOk())
.andExpect(content().string(hello));
}
// 추가된 API 테스트 코드
@Test
public void helloDto가_리턴된다() throws Exception {
String name = "hello";
int amount = 1000;
mvc.perform(
get("/hello/dto")
.param("name",name)
.param("amount",String.valueOf(amount)))
.andExpect(status().isOk())
.andExpect(jsonPath("$.name",is(name)))
.andExpect(jsonPath("$.amount",is(amount)));
}
}
param
API 테스트할 때 사용될 요청 파라미터를 설정한다.
단, 값은 String만 허용된다.(숫자, 날짜 등의 데이터도 등록할 때 문자열로 변경해야한다.)
package com.choee.service.springboot;
import org.springframework.boot.SpringApplication;
import org.springframework.boot.autoconfigure.SpringBootApplication;
@SpringBootApplication
public class Application { // 메인 클래스
public static void main(String[] args) {SpringApplication.run(Application.class,args);} // SpringApplication.run : 내장 WAS 실행
}
@SpringBootApplication
스프링 부트의 자동 설정
스프링 Bean 읽기와 생성 모두 자동 설정,
@SpringBootApplication이 있는 위치부터 설정을 읽어가므로 메인 클래스틑 항상 프로젝트의 최상단에 위치해야한다.
Spring Bean 이란?
Spring에 의하여 생성되고 관리되는 자바 객체를 Bean이라고 한다.
참조: melonicedlatte.com/2021/07/11/232800.html
내장 WAS(Web Application Server)란?
별도로 외부에 WAS를 두지 않고 애플리케이션을 실행할 때 내부에서 WAS를 실행하는 것
내장 WAS 이용의 장점
항상 서버에 톰캣을 설치할 필요가 없게 되고, 스프링 부트로 만들어진 Jar 파일(실행 가능한 java 패키징 파일)로 실행하면 된다.
언제 어디서나 같은 환경에서 스프링 부트를 배포할 수 있다.
3. 현재 패키지 하위에 web 패키지 생성
컨트롤러와 관련된 클래스들을 관리하는 패키지
HelloControler 클래스 생성하여 테스트 API 작성
package com.choee.service.springboot.web;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RestController;
@RestController
public class HelloController {
@GetMapping("/hello")
public String hello() {
return "hello";
}
}
@RestController
컨트롤러를 JSON을 반환하는 컨트롤러로 만들어준다.
이전의 @ResponseBody를 각메소드마다 선언했던 것을 한번에 사용할 수 있게해주는 어노테이션
@GetMapping
HTTP Method인 Get의 요청을 받을 수 있는 API를 만들어 준다.
이전엔 @RequestMapping(method = RequestMethod.GET)으로 사용
여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.
현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다. 예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.
여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.
입력
첫 줄에 테스트케이스의 수가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다.
테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다. 이때 맨 왼쪽은 0번째라고 하자. 두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.
출력
각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.
예제 입력 1
3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1
예제 출력 1
1
2
5
분석
아이디어
문제에서 요구하는대로 구현
해결 코드 주석 참조
복잡도
주어진 문서들의 길이 시간 복잡도
자료구조
큐
해결 코드
tc = int(input())
for _ in range(tc):
n,m = map(int,input().split())
docs = deque(list(map(int,input().split())))
out_num=0
while docs:
doc_top = max(docs) # 중요도가 제일 높은 문서
doc_1 = docs.popleft() # 가장 앞에 있는 문서
m-=1 # 찾으려는 문서가 출력될 때까지, 왼쪽으로 이동하면서 탐색
if doc_top == doc_1: # 가장 앞에 있는 문서가 중요도가 제일 높은 문서이면
out_num+=1
if m < 0: # 찾으려는 문서가 중요도가 제일 높은 문서라 출력
print(out_num)
break
else:# 2. 가장 앞에 있는 문서가 중요도가 제일 높은 문서가 아니라면
docs.append(doc_1) # Queue의 가장 뒤에 재배치
if m<0: # 찾으려는 문서가 중요도가 제일 높은 문서가 아니면서 가장 앞에 있어
m = len(docs) - 1 # 가장 뒤에 재배치
3) build.gradle 변경 반영 인텔리제이 오른쪽 하단 알럿의 Enable Auto-import 클릭하여build.gradle 변경이 있을 때 마다 자동 반영되도록 설정
4) 의존성 확인 오른쪽 Gradle 탭을 클릭하여 의존성들이 잘 받아졌는지 확인
1.5 인텔리제이에서 깃과 깃허브 사용하는 방법
VCS(버전 관리 시스템) 선택: Git
Git의 원격 저장소 서비스 선택: Github
인텔리제이에서 깃허브 연동
1) Ctrl + Shift + A : Action 검색창 열기 2) share project on github 검색 3) 깃허브 로그인 4) Repository name 설정 후 등록 ( 최초 git ingnore 설정 No) 5) 첫 커밋 팝업창에서 .idea 디렉토리 제외한 후 커밋 ( 실행시 자동으로 생성되는 파일들이므로 깃허브 올릴 필요 없음 ) 6) .gitignore파일을 사용하여 .idea 폴더를 앞으로의 모든 커밋 대상에서 제외 처리
인텔리제이에서는 .gitignore 파일에 대한 기본적인 지원이 없음
플러그인에서 .gitignore 지원
.ignore 플러그인 지원 기능
파일 위치 자동완성
이그노어 처리 여부 확인
다양한 이그노어 파일 지원(.gitignore, .npmignore, .dockerignore 등)
설치 방법
1) Ctrl + Shift + A : Action 검색창 열기 2) plugins 검색 3) Marketplace 에서 .ignore 설치 4) 인텔리제이를 다시 시작해서 설치한 플러그인 적용 ( 반드시 재시작해야만 함) 5) .gitignore 파일 생성: 프로젝트 이름을 선택한 뒤, 마우스 오른쪽 or Alt + Insert로 New(생성목록) 확인하여 .gitignore 파일 생성 6) 이그노어 처리 후 깃허브에 .gitignore 파일을 푸시하여 반영