키자드에 등록된 a980917a의 네이버 블로그 포스트 목록

a980917a의 등록된 링크

a980917a로 등록된 네이버 블로그 포스트 수는 90건입니다.

boj_21611_마법사 상어와 블리자드 [내부링크]

https://www.acmicpc.net/problem/21611 (문제 자체가 너무 길어 나머지 부분은 생략...) <풀이> 구...

boj_21608_상어 초등학교 [내부링크]

https://www.acmicpc.net/problem/21608 <풀이> 문제 조건을 정리해보자. 1. 학생들의 자리는 주어진...

갤러리 권한받아오고, 사진 출력하기 [내부링크]

갤러리에 접근하기 위한 권한을 받아오고, 선택한 사진을 출력하는 예제이다. 예전에는 앱을 플레이스토어...

3장 Transport Layer(4) [내부링크]

이전 포스팅에서 Stop & Wait 방식(하나의 패킷을 전송하고, 그 ACK가 올 때 까지 대기하는 방식)...

3장 Transport Layer(5) [내부링크]

TCP (Transmission Control Protocol) 1. Point-to-point : Sender - Receiver가 짝을 이루고 통...

3장 Transport Layer(6) [내부링크]

다음과 같은 상황을 생각해보자. 1. Sender의 데이터 전송속도가 Receiver의 데이터 처리속도보다 느린 ...

Notification [내부링크]

FCM(Firebase Cloud Messaging)을 이용하여 앱에 알림을 전송하는 Notification 기능을 구현해보자....

https://www.acmicpc.net/problem/16235 <풀이> 시간초과로 굉장히 애를 먹었던 문제이다. 위 코드처럼 나무들의 정보를 담을 구조체를 선언하고 하나의 벡터에 현재 살아있는 모든 나무들을 담았다. 그리고 나이가 어린 나무부터 영양분을 공급하여야 하므로 정렬을 해주었다. 이후, 각 계절마다의 기능을 구현하였다. 매 해마다 살아있는 나무의 개수를 N이라고 한다면 나이 오름차순 정렬을 위해 필요한 시간은 O(NlogN)이다. 또, 계절마다의 기능을 수행하기 위해 모든 나무들에 대해 N번 탐색해야하므로 시간복잡도는 O(NlogN + N)이다. 위 코드를 살펴보자. 처음 코드와 다른점은 정렬을 제일 처음 "나이 내림차순"으로 한.......

boj_19236_청소년 상어 [내부링크]

https://www.acmicpc.net/problem/19236 <풀이> 문제 조건을 먼저 정리해보자. 1. 4x4크기의 공간에 16마리의 물고기가 존재한다. 각 물고기는 번호(1~16)와 방향(8방향)을 가지고있다. 2. 초기 상어의 위치는 (0,0)이며, board[0][0]에 위치하는 물고기를 잡아먹으며 시작한다. (이 때 상어의 방향은 board[0][0]에 존재하던 물고기의 방향과 같다.) 3. 물고기의 번호가 작은 순서대로 이동한다. (정렬이 필요할 것임을 예상) 각 물고기는 공간 내의 빈칸 or 다른 물고기가 있는 칸으로만 이동할 수 있다. 이 때, 다른 물고기가 있는 칸으로 이동하려 한다면 서로 자리를 바꾸는 방식으로 이동한다 (현재 상태를 변화시키지 않고, 다음 상.......

boj_20056_마법사 상어와 파이어볼 [내부링크]

https://www.acmicpc.net/problem/20056 <풀이> 문제 조건을 정리해보자. 1. N x N 격자에 M개의 파이어볼이 존재한다. 각 파이어볼은 위치, 질량, 방향, 속력을 가진다. 2. 행과 열의 시작과 끝은 서로 연결되어있다. 3. 모든 파이어볼이 자신의 방향 d로 속력 s만큼 이동한다. 4. 이동이 끝난 뒤, 한 칸에 2개 이상의 파이어볼이 존재한다면 다음이 일어난다. 5. 파이어볼이 K번 이동한 후, 남아있는 파이어볼 질량의 합은? 2번 조건을 구현하는 부분에서 문제가 생겨 AC를 받기까지 힘들었다.. 우선 8방향의 row와 col 변화를 pii로 만들어서 delta 배열에 저장하였다. (0~7 방향에 맞게, 인덱스도 맞춰주었다.) 그리고 row와 col을 따.......

boj_20057_마법사 상어와 토네이도 [내부링크]

https://www.acmicpc.net/problem/20057 <풀이> 문제 조건을 정리해보자. 1. 토네이도는 가운데서부터 시작해 위 그림과 같은 방향으로 진행된다. 2. 토네이도는 x에서 y로 이동함에 따라 위 그림에 표시된 비율로 모래를 이동시키게 된다. (비율을 계산하며 발생하는 소수점 아래는 버린다.) 3. a로 이동하는 모래의 양은 비율이 적혀있는 칸으로 이동하지않고 남아있는 모래의 양이다. ( a = x - sum( 비율) ) 4. 모래는 격자 밖으로 날아갈 수도 있다. 우선 가장 먼저 토네이도를 정상적으로 진행시켜야 한다. 제일 먼저 토네이도가 발생하는 횟수를 구해야한다. 위와 같은 사이클을 토네이도의 한 주기로 보았다. 위 그림을 살펴.......

boj_20058_마법사 상어와 파이어스톰 [내부링크]

https://www.acmicpc.net/problem/20058 <풀이> 문제 조건을 정리해보자. 1. 2^N x 2^N 크기의 격자가 있다. (최대 64x64) 2. 전체 격자를 2^L x 2^L 크기의 부분격자로 나눈다. 3. 모든 부분격자를 시계방향으로 90도 회전시킨다. 이후, 얼음이 있는 칸 3개 이상과 인접해있지 않은 칸은 얼음의 양을 1만큼 감소시킨다. 4. 모든 파이어스톰이 시전된 후, 남아있는 얼음 A[r][c]의 합, 남아있는 얼음중 가장 큰 덩어리가 차지하는 개수는? 우선 제일 먼저 격자를 부분격자로 나누어야 한다. 전체 부분격자의 개수는 다음과 같다. (2^N x 2^N) / (2^L x 2^L) 개 이후 부분격자의 개수만큼 90도 회전시켜준다. rotate 함수를 구현하는데 조금.......

boj_21609_상어 중학교 [내부링크]

https://www.acmicpc.net/problem/21609 <풀이> 문제 조건을 정리해보자. 1. N x N 크기의 격자가 있고, 초기에 모든 칸에는 블록이 하나씩 들어있다. 2. 블록은 검은색, 무지개, 일반 블록이 있다. 3. 일반 블록은 M가지의 색상이 있고, 각각은 M이하의 자연수로 표현한다. 4. 검은색 블록은 -1, 무지개 블록은 0으로 표현한다. 5. 블록 그룹은 다음과 같이 정의한다. 5-1. 1개 이상의 일반블록(모두 같은 색) + 무지개 블록(개수제한 x) 으로 구성 5-2. 5-1을 만족하며 블록의 총 개수가 2개 이상이어야 그룹이 될 수 있다. 5-3. 모든 블록은 인접해있어야 한다. 5-4. 기준 블록 : 블록 그룹 내의 가장 왼쪽 상단에 위치한 블록 6. 크기.......

Room Database [내부링크]

1. Room Database란? 다른 서버와 통신할 필요 없이, 앱 내부적으로 가지고 있는 데이터베이스. 네트워크 통신이 불가능한 상황에서 사용자가 오프라인 상태로 데이터를 탐색할 수 있도록 관련 데이터를 저장할 수 있다. 2. Room 구성요소 1) Database Class : 데이터를 저장할 데이터베이스 클래스 2) Entities : 데이터 테이블을 구성하는 row 3) DAO (Data Access Objects) : DB와 통신할 수 있는 CRUD 메소드를 제공해주는 객체 3. build.gradle 추가 4. Database Class 선언 쉽게 생각하면 DB에 사용할 모델을 만들어주는 것이다. 사용할 entity를 선언하고, @annotation을 사용하여 PK, Column 등을 명시해준다. 5. DAO 선언 DB와 통신하기.......

3장. Transport Layer (1) [내부링크]

Transport Layer의 기능 각 host들의 프로세스 사이에 논리적 연결을 형성켜준다. sender : 데이터를 작은단위의 segment로 나누고, Network Layer에 전달한다. receiver : segment로 데이터를 만들고 Applcation Layer에 전달한다. TCP vs UDP ※ in-order delivery : transport layer끼리 packet을 반드시 순서대로 주고받는다는 것은 아니다. 응용계층에서 '그렇게 보이도록' 만들어주는 역할. Multiplexing & Demultiplexing 위에서 Transport Layer의 기능은 각 host들의 프로세스 사이에 논리적 연결을 형성시켜주는 것이라고 하였다. 이 때 필요한 것이 'Multiplexing & Demultiplexing' 이다. Source의 3가.......

3장. Transport Layer(2) [내부링크]

UDP (User Datagram Protocol) 1. connectionless : connection을 위한 delay가 존재하지않아 빠르다. 2. connection이 없으므로, 각 segment들은 독립적으로 수행된다. 3. 기본적인 Multiplexing, Demultiplexing만 수행 4. Unreliable(no congestion control) : 데이터가 분실되거나, 손상될 수 있다. 5. header의 사이즈가 작다. ex) Streaming Multimedia App, DNS 등 UDP Segment Format length : 헤더와 데이터를 포함한 전체 segment의 길이 checksum : UDP segment에 에러가 존재하는지의 정보를 제공 Checksum Segment에 에러 유/무의 정보만을 제공하기 위한 비트 (UDP는 unreliable이지만, 간단하게만 에러의 유/무만 제공해서 응용프.......

boj_11053_가장 긴 증가하는 부분 수열 [내부링크]

https://www.acmicpc.net/problem/11053 <풀이> 알고스팟에서 같은 문제를 풀어본 적이 있다. 중요한 문제라 다시 한 번 점검하는 차원에서 풀어보았다. 처음에 순간 'O(n^2)으로 풀리지 않을까?' 하는 멍청한 생각이 들었다... (n의 크기가 1000밖에 안 돼서..) " 1 2 3 4 10 2 3 4 5 6 7 8 " 이 반례를 생각해보면 안 된다는 것을 쉽게 알 수 있다. dp 배열에 어떤 값을 저장할지가 중요하다. 이러한 배열이 있을 때, dp 배열의 원소로는 "나를 포함한, 증가하는 수열의 길이"가 들어가게 된다. 제일 처음 pivot = 10 을 생각해보면, (인덱스 0의 10을 의미) 10 -> 20 -> 30 -> 50 순으로 재.......

boj_1520_내리막 길 [내부링크]

https://www.acmicpc.net/problem/1520 <풀이> 처음 풀어보는 그래프 + DP 문제였다 (1,1) -> (M,N) 까지의 경로의 개수를 구하는 문제여서 완전탐색을 돌리기위해 dfs로 탐색해야했다. 그러면 어디서 반복되는 계산을 줄일 수 있을까? 위 예제는 서로 다른 두 경로이지만, "20"에 도착한 후로는 같은 경로로 진행된다. 완전탐색에서는 20 -> 17 -> 15 ->10이 중복하여 재귀호출된다. 따라서 이를 줄이기위해 2차원 배열 dp를 선언하고, 그 원소로는 "해당 칸에서 목적지까지 가기위한 경로의 개수"를 저장하였다. dfs를 탐색하기 위해 최악의 경우 3가지 방향을 탐색해야한다. (숫자가 작은 쪽으로 이동.......

버튼 색깔 변경 [내부링크]

안드로이드에서 버튼 색깔 변경하는 법 위 코드를 보면, "background" 옵션으로 버튼색깔을 지정해주었음에도 불구하고, 바뀌지 않는 것을 볼 수 있다. 이 때, <Button> 태그 대신, <androidx.appcompat.widget.AppCompatButton> 태그를 사용하면 바로 변경된다.

boj_2565_전깃줄 [내부링크]

https://www.acmicpc.net/problem/2565 <풀이> 좌측 그림은 input으로 주어진 것을 그림으로 나타낸 것이고, 우측 그림은 이 테스트케이스가 정답이 될 때를 그림으로 나타낸 것이다. 그렇다면, 모든 전깃줄이 서로 겹치지 않기위한 조건을 한 번 생각해보자. 전깃줄이 겹치지 않으려면, "나보다 위에있는 전깃줄들은 나보다 아래로 내려오면 안된다." 는 조건이 필요하다. 우측 그림을 보면 A입장에서 더 낮은 위치의 전깃줄들은 B에도 항상 더 낮은 위치에 연결되어 있다. 8 2 9 1 4 6 7 10 이 말을 바꿔생각하면, 서로 겹치지않는 전깃줄의 개수는 "증가하는 부분 수열의 최대 길이" 이다. 따라서, 이문제를 풀기위.......

SharedPreferences [내부링크]

1. SharedPreferences 란? 앱을 사용하면서 데이터를 저장하는 일은 매우 흔한 일이다. 보통은 서버에 데이터베이스를 구축하고 여기에 저장하는 것이 일반적이지만, 작은 데이터라면 SharedPreferences를 사용하는 것도 좋아보인다. SharedPreferences는 데이터를 파일 형태로 앱 폴더 내에 저장하는 방식이다. (key - value 형식) 2. Mode SharedPreferences는 다음과 같이 여러 모드로 선언할 수 있다. 1) MODE_PRIVATE : 생성한 Application에서만 사용 가능하다. 2) MODE_WORLD_READABLE : 외부 App에서 사용 가능, But 읽기만 가능 3) MODE_WORLD_WRITEABLE : 외부 App에서 사용 가능, 읽기/쓰기 가능 3. 뷰 생성 아래와 같이 간단한 뷰를.......

boj_19237_어른상어 [내부링크]

https://www.acmicpc.net/problem/19237 <풀이> 조건이 많아 코드양도 많고 구현하는데 꽤 까다로운 문제였다. 조건을 요악하자면 다음과 같다. 1. 상어는 1초마다 현재 위치에 자신의 냄새를 뿌리고 이동한다. (냄새의 지속시간 : K초) 2. 상어는 인접한 4방향중 냄새가 없는 곳을 찾는다. 3-1. 냄새가 없는 곳이 여러곳일 경우 현재 바라보는 방향의 우선순위에 따라 이동한다. 3-2. 냄새가 없는 곳이 없는 경우, 자신의 냄새가 있는 곳으로 이동한다. 이 또한, 바라보는 방향의 우선순위에 따라 이동한다. 4. 만약 한 칸에 여러 마리의 상어가 이동하려 한다면 번호가 가장 작은 상어만 남고, 나머지는 쫓겨난다. 5. 1번 상어만 남을 때.......

boj_15685_드래곤커브 [내부링크]

https://www.acmicpc.net/problem/15685 <풀이> 각 드래곤커브의 N세대를 모두 구한 다음, board에 표시하고 정답을 출력하는 방식으로 하였다. 각 좌표를 회전시키기 위해 수학공식을 이용하였다. (x,y)를 (a,b)기준으로 X도 만큼 회전시킨 (x',y') 문제 조건에서 시계방향으로 회전시키므로 X는 -90(sin-90 = -1)이 되어야 한다. 또한, y축의 증가하는 방향이 반대이므로, y값에 -1을 곱해주어야 한다. 드래곤 커브로 둘러쌓인 정사각형은 이렇게 오른쪽, 밑, 대각선의 좌표 모두 드래곤커브인 경우를 말한다. 따라서 (i,j), (i+1,j), (i,j+1), (i+1,j+1)를 검사하여 카운팅한다. <코드>

3장 Transport Layer(3) [내부링크]

Reliable Data Transfer 란? Transport Layer에서 Application Layer로 데이터를 전달할 때 데이터의 손실, 변질, 순서 등이 문제 없음을 보장하는 것 Error Type & Solution 1) Bit error : Checksum을 검사하여 에러가 포함되어있지 않은 경우 ACK 전송 2) Packet loss : Sender가 데이터를 전송하고 일정한 시간동안 ACK를 받지못하는 경우 중간에 packet loss가 발 생하였다고 간주하고 재전송함. 만약 Receiver가 전송한 ACK가 loss된 것이라면, Sender는 이를 알 지 못하고 패킷을 다시 재전 송하게됨. Receiver 입장에선 재전송된 이 패킷이 실제 데이터인지, 재전송된 데이터인지 모름 => Packet Sequence Number로 해결 - o.......

1장. Introduction(1) [내부링크]

2학기 때 수강한 컴퓨터 네트워크 수업 관련 내용 정리. 시험준비하면서 필요한 것만 쓰다보니 중요한 내용들이 빠질 수도 있다. 필요할 때 보충하자 ! Internet 이란? Inter + net의 의미로, 여러 Network들이 연결된 그물 형태 위 그림처럼 여러 종류의 Network가 연결되어 Internet을 구성한다. Internet 의 구성 Internet은 HW + SW로 구성된다 HW : end host(네트워크 사용 주체를 의미), link, interconnection devide(Router, switch, Repeater) SW : OS, App program, Protocol Protocol 이란? Protocol이란 간단하게 얘기하면 의사소통 규칙(데이터 교환 규칙)? 과 비슷한 의미이다. Protocol은 다음 3가지를 정의한다. 1. Message form.......

boj_2512_예산 [내부링크]

https://www.acmicpc.net/problem/2512 <풀이> 앞서 풀었던 이분탐색 문제들과 동일하다. https://blog.naver.com/a980917a/222615447373 자세한 풀이는 위 문제를 참고하자. 다른 차이점이 있다고하면, 각 지방의 총예산이 최대가 되는 mid값을 구하는 것이므로, "현재 총 예산 > 이전 총 예산" 이 되는 시점에 업데이트가 진행된다. 추가적으로, "lower == upper"가 되는 케이스를 구분할 수 있게 됐다. https://blog.naver.com/a980917a/222615447373 이 문제에서는 "lower == upper"가 되는 케이스를 처리하지않았다. 왜냐하면, 상한값으로 나무를 자른다면, 획득하는 나무가 0 .......

1장. Introduction(2) [내부링크]

네트워크 평가 기준 1. Delay : 패킷이 source에서 destionation 까지 이동하는데 걸리는 시간 Process Delay = 라우터에서 패킷을 포워딩하거나, 에러체크 등의 패킷을 처리하는데 걸리는 시간 Queueing Delay = 혼잡제어(Congestion Control )를 위해 패킷을 잠시 큐에 대기시키는 시간 Transmission Delay = 라우터가 첫번째 패킷 ~ 마지막 패킷까지 모두 링크로 내보내는데 걸리는 시간 ※ L / R (L : packet length, R : bandwidth) Propagation Delay = 실제로 패킷이 link를 타고 이동하는데 걸리는 시간 2. Packet Loss : 버퍼가 가득찬 라우터에 어떤 패킷이 도착할 경우 Loss될 수 있다. 3. Throughput : 비트 전.......

boj_3020_개똥벌레 [내부링크]

https://www.acmicpc.net/problem/3020 <풀이> 가장 먼저 브루트포스로 어떻게 풀 수 있을지 생각해보았다. 각 높이 h 마다 몇개의 장애물이 존재하는지 탐색해본다면, O(NH)의 시간복잡도가 필요하다. 하지만 NH는 10^11으로 1초안에 불가능하다. 따라서 1초안에 해결하기 위해서는, N 혹은 H의 시간복잡도를 O(log)로 줄여아, O(NlogN)풀이가 가능해진다. 그럼 N과 H중 뭐를 O(log)로 줄일 수 있을까? 우선 N은 줄일 수 없다고 생각했다. 왜냐하면, 석순or종유석의 높이가 다양하고, 이분탐색을 하기위한 어떤 규칙이 안 보였기 때문이다. (Search Space를 줄였을 때, 정답이 이 공간에 무조건 존재하는 규칙) 그래서 모든 N에 대하여, H.......

boj_1939_중량제한 [내부링크]

https://www.acmicpc.net/problem/1939 <풀이> 문제 조건을 정리해보자. 1. 여러 개의 섬들이 있다. 이 섬들은 다리로 연결되어있는데, 다리의 최대중량 c 보다 큰 무게는 지나갈 수 없다. 2. 어떤 두 개의 섬을 연결하는 다리는 한 개 이상일 수 있다. 3. 1번 공장에서 출발해 2번공장으로 가는 경로는 항상 존재한다. 문제에서 요구하는 것은, 한 번의 이동으로 옮길 수 있는 중량의 최대값이다. 따라서, 공장1에서 공장2까지 갈 수 있는 여러 루트 중에서 각 루트의 다리중량의 최소값이 최대가 되게하는 무게를 찾아야 한다. 그래서 아래와 같이 완전탐색으로 시도하였다. ex) 위 그림을 살펴보면, 1번 노드에서 5번 노드까지가는 경로.......

2장. Application Layer(1) [내부링크]

Network Applcation 여러 응용프로그램들 중, 네트워크를 사용하는 프로그램. (각 end-host에서 실행된다.) ex) e-mail, web, p2p, sns, youtube 등 Applcation의 구조 1. server-client-server 구조 1) server가 항상 on 되어야 통신이 가능하다. 2) server는 영구적인 IP주소를 가진다 3) Data Center가 존재한다. (트래픽 관리) 4) client의 IP는 dynamic하다. 5) client가 server에 데이터를 요청하는 형식 6) client는 필요할 때 server에 연결을 요청한다. 2. peer-to-peer(P2P) 구조 1) server가 존재하지 않는다. 2) client가 데이터를 요청할 수도, 제공할 수도 있다. -> 확장성 : client가 증가하더라도, 그만큼 데이터의 양도 증가.......

boj_8983_사냥꾼 [내부링크]

<풀이> 완전탐색으로 문제를 어떻게 풀지 생각해보자. 사냥꾼이 위치할 수 있는 모든 사대에서, 모든 동물로부터의 사정거리를 구하고 사냥이 가능한지를 판단해보면 된다. 이 때 최악의경우에 시간복잡도 O(MN) = 10^10이 되고 1초 내에 통과가 불가능하다. 지금까지 이분탐색을 공부하며 보았던 풀이방법은 두가지가있다. while문을 이용하여 lower,upper를 설정하고 그 mid값으로 조건을 만족시키는지 계산하여 Search Space를 줄여나가는 방법과, 정렬된 자료구조에서 lower_bound or upper_bound를 이용하여 원하는 값을 찾아내는 방법이다. 이 문제에서는 어떤방법을 사용할 수 있을지 생각해보자. 우선 전자의 방법을 사용하기.......

2장. Application Layer(2) [내부링크]

DNS (Domain Name System) 우리가 어떤 웹사이트에 접속하기 위해선 해당 server의 IP주소를 알아야한다. 하지만 우리가 모든 IP주소를 외울 순 없다. 이 때 우리가 접속하고자하는 웹사이트의 이름을 입력하면 해당 IP주소를 반환해주는 시스템이 바로 Domain Name System, DNS이다. DNS의 장점 DNS server는 전 세계에 계층구조로 분산되어있다. 1. Load Distribution -> 실제로 하나의 웹사이트에서 여러개의 서버를 두는 경우가 많은데, 이 때 DNS에서 각 client의 요청에 다른 IP 주소를 알려주어 트래픽을 분산시키도록 함 2. Distributed DB System 1) Single point of failure 방지 - 하나의 DNS DB에 문제가 생기더라도 다른 DNS DB를.......

boj_1149_RGB거리 [내부링크]

https://www.acmicpc.net/problem/1149 <풀이> DP가 정말 오랜만이라 잘 풀 수 있을까 걱정됐는데, 풀이 방법이 생각보다 빨리 떠올랐다. (예전에 비슷한 유형을 몇 개 풀어봐서 그런듯 하다.) 문제를 간략하게 설명하자면, N개의 집을 색칠을 할건데, 이웃한 집들은 다른색으로 색칠하고자 한다. 이 때 최소비용을 구하는 문제이다. (조건 1,2,3을 모두 합쳐서 생각해보면 결국 이 말인 거 같다.) 위 사진은 TC4번을 나타낸 것이다. 문제 조건을 다시 살펴보면, i 번째 집의 색은 i - 1번째 집의 색과 달라야한다. 2번 집에 빨강색, 초록색, 파랑색중 어느 색을 칠해야 정답이 될지 우리는 모른다. 하지만 각 케이스마다 최소값을 구할 수.......

boj_15686_치킨배달 [내부링크]

https://www.acmicpc.net/problem/15686 <풀이> 문제에서 요구하는 것은 "폐업시키지 않을 치킨집을 최대 M개 골랐을 때" 도시의 치킨 거리의 최솟값이다. 그렇다면, 폐업시키지 않을 치킨집을 0개부터 M개까지 선택해가며 각 case마다의 도시의 치킨거리를 구하고 이 중 최소값을 찾아야한다. 아주 간단한 dfs 문제이다. 예를 들어, M이 3이라고 가정하고, 치킨집이 총 3개라고 가정한다면 폐업시킬 치킨집을 다음 그래프처럼 그릴 수 있다. 이를 dfs탐색하며 각 노드에서의 도시의 치킨거리를 구하고 최소값을 출력하면 쉽게 풀린다. <코드>

boj_10830_행렬제곱 [내부링크]

https://www.acmicpc.net/problem/10830 <풀이> 우선 B의 최대값이 100,000,000,000 (100억) 이다. 1초안에 통과시키려면 O(n) = 10^8이 되어야하는데 턱없이 부족하다. 그래서 최소 O(logN)으로 풀어야겠다고 생각했고, 아는 게 이분탐색밖에 없으니 이분탐색으로 접근을 했다. 이분탐색에서 가장 중요한 건 다음 재귀호출에서 Search Space를 절반으로 줄이는 것이다. 예를 들어, B가 4인 경우에는 총 4번 계산해야 할 것을 " O(log4) = 2"를 이용하여 두 번만에 계산할 수 있다. 각 depth마다 우측 자식노드는 좌측 자식노드와 동일하므로 "재활용"한다고 생각하면 Search Space를 절반으로 줄여갈 수 있.......

Navigation Component [내부링크]

네비게이션은 간단하게 설명하자면, 프래그먼트 화면전환을 쉽게 할 수 있게 해준다. 이번에 RePose 진행하면서, 처음에 네비게이션을 사용하지않고 화면을 구상하다가 백스택 관리하는 부분에서 멘탈이 터져 코드를 싹 갈아엎은 적이 있어서 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 이번에 잘 정리해두고 다음부터는 필히 그냥 무조건적으로 네비게이션을 사용해야겠다. 1. Build Gradle에 Library 추가 2. navigation xml 파일 만들기 res폴더에 다음과 같이 Navigation 타입의 xml파일을 만들어준다. 3. 사용할 화면 (Fragment) 만들기 다음과 같이 3개의 프래그먼트를 만들었다. 화면은 간단하게 텍스트와 버튼으로 구성하였다. 4. 메인액티비티와 네비게이.......

RecyclerView [내부링크]

리사이클러뷰는 어떤 반복적이고, 동적인 리스트를 보여주는데 활용. ex) 메뉴리스트, 친구리스트 등등... 1. 리사이클러뷰 생성 원하는 위치에 리사이클러뷰를 생성해준다. item 0 ... 9 가 출력되는 것을 볼 수 있다. 2. 리사이클러뷰에 담을 레이아웃 만들기 리사이클러뷰에 담고싶은 레이아웃을 만든다. 이렇게 이미지 하나와, 이름, 휴대폰 번호를 보여줄 레이아웃을 만들었다. 3. 리사이클러뷰 어댑터 만들기 아래는 리사이클러뷰를 이용하기 위해 기본적으로 필요한 메소드들이다. 주석으로 설명하기에는 쓸 말이 애매하다... (완성된 코드를 보는게 효율적일 거 같다.) 위 안드로이드 공식문서를 바탕으로 각 메소드의 기능을 내 생각대.......

ViewPager2 [내부링크]

ViewPager란? 인스타에서 사진 여러장을 게시물로 작성하게되면, 한 장 한 장 손으로 스와핑해서 다음 사진으로 혹은 이전 사진으로 넘어갈 수 있다. 이렇게 여러 뷰(혹은 프래그먼트)를 담는 컨테이너를 뷰페이저라고 한다. 1. 라이브러리 추가 프로젝트단위 build.gradle에 뷰페이저 디펜던시를 추가한다. 2. xml 파일에 뷰페이저 추가 뷰페이저를 이용하여 원하는 레이아웃을 만든다. 3. 뷰페이저에 담을 프래그먼트 생성 아래 코드는 뷰페이저에 담을 TestFragment이다. newInstance 메소드를 이용하여 데이터를 전달받고, 프래그먼트 생성자 역할을 하도록 한다. 4. 뷰페이저 어댑터 생성 리사이클러뷰와 마찬가지로, getItemCount 함수를 이.......

ViewBinding [내부링크]

뷰바인딩 (View Binding) 뷰바인딩을 사용하면 "findViewById" 코드를 작성하지 않고, 바로 뷰 객체에 접근할 수 있다. 1. build.gradle 추가. 앱단위 build.gradle 파일을 열어 아래 그림과 같이 viewBinding을 enable 시켜준다. 2. 바인딩 클래스 객체 선언 viewBinding을 enable시키고 나면, 각 XML 레이아웃 파일의 바인딩클래슬르 선언할 수 있다. 클래스 이름은 XML 레이아웃 파일의 "카멜 표기법 + Binding" 으로 나타난다. 아리 사진처럼, binding 객체를 선언해주자. 3. 레이아웃 파일과 뷰바인딩 연결시키기 아래 3줄을 통해, 레이아웃과 뷰바인딩을 연결시킬 수 있다. ("레이아웃과 뷰바인딩을 연결"한.......

DataBinding [내부링크]

데이터바인딩 데이터 바인딩은 앱 내의 어떤 데이터와 뷰를 결합시켜준다. 아래 안드로이드 공식문서에서 가져온 코드를 보자. findViewById 함수를 통해, 텍스트뷰 객체를 찾고, text값에 viewModel 객체의 userName 값을 할당한다. 아래 코드는 레이아웃에서 바로 viewModel 객체가 가진 변수 값을 할당하는 코드이다. 위 코드와 동일한 기능을 하지만, 레이아웃 파일에서 처리함으로써 class파일에서 textView의 text 속성 값을 할당하는 코드를 작성하지 않아도 된다. 이처럼 데이터바인딩을 사용함으로써 작성되는 코드 수를 줄일 수 있다. 1. 데이터바인딩 Enable 앱 단위 build.gradle을 열어, 아래와 같이 데이터바인딩을 enable 시켜준.......

boj_1654_랜선 자르기 [내부링크]

https://www.acmicpc.net/problem/1654 <풀이> 실버문제 임에도 불구하고 이분탐색은 너무 어렵다.. 특히 이 문제처럼 어떤 배열을 가지고 이분탐색을 하는 게 아니라, 값?을 가지고 유추하는 듯한 느낌이 드는 문제 너무 싫다. 이번 문제는 다른 사람 풀이를 매우 많이 참고하였다. 사실 아직까지도 완벽한 이해는 아닌 듯 하지만, "그렇구나~" 하면서 받아들였다. 우선 주어진 예제를 가지고 생각해보자. 802, 743, 457, 539 의 길이를 가지는 랜선이 4개 있다. 우리는 이 랜선들을 "적당한 길이"로 잘라서 11개를 만들어야한다. 그렇다면, 우리가 선택할 수 있는 "적당한 길이"의 최대값과 최소값은 얼마.......

boj_2805_나무 자르기 [내부링크]

https://www.acmicpc.net/problem/2805 <풀이> https://blog.naver.com/a980917a/222613830410 이 문제와 거의 흡사하다. 이 번 문제도 1트는 하지 못했는데, 이유를 살펴보니 int 타입 overflow 때문이었다. 이분탐색문제는 데이터 크기가 int타입을 자주 벗어나는 거 같다. 다음 부터는 신경쓰자 !! 다시 한 번 더 정리하자면, 이러한 수의 범위를 가지고 짐작하며 Search Space를 좁혀나가는 문제는 lower와 upper의 초기값을 잘 생각해봐야한다. 또, 위 랜선자르기 문제와는 달리 이 문제는 lower와 upper가 같은 경우를 생각하지 않아도 됐다. 무슨 차이일까?? 정확하게 잘 모르겠다..... <코드>

boj_2580_스도쿠 [내부링크]

https://www.acmicpc.net/problem/2580 <풀이> 1.우선 input을 받으면서 빈칸이 들어오면 그 개수를 카운팅해서 emptyNum변수에 저장한다. 2. 이중 for-loop으로 input에서 빈 칸 찾기 3. for(1 ~ 9) 들어갈 수 있는 숫자 찾기 --> can_inputNum() 가로, 세로는 이렇게 단순히 구현하였고 3x3은 내가 숫자를 놓을 row,col을 함수 인자로 받아와서 그 범위의 왼쪽상단에 위치하도록 변환하고 이중 for-loop으로 bool을 판별해주었다. 4. 빈칸을 채웠으면 emptyNum-- 5. dfs() 6. emptyNum == 0 이란 얘기는 모든 빈칸을 채웠다는 의미이므로 return 7. 여러 정답이 나올 수가 있는데, 하나만 출력하면 되므로 정답을 찾은 경우.......

boj_9663_N-Queen [내부링크]

https://www.acmicpc.net/problem/9663 <풀이> 처음엔 for(0~N) 해당 col의 빈칸 찾기 -> 해당 칸에 퀸이 공격 가능한 칸 지우기 (이중 for문) -> dfs(col+1) 이렇게 구현을 했었는데 시간초과가 떴다... 도저히 모르겠어서 결국 N-Queen 풀이를 외우자는 마인드로 구글링을 했다. 우선 자료구조가 조금 특이했다. 기존에 생각했던 2차원 array가 아니었다. N의 사이즈 만큼 position[N] 이렇게 1차원 array를 만들었는데, 설명하자면 position[1] = 2란 의미는 첫번째 퀸은 (2,1)에 놓인다는 의미 !! 이렇게 퀸이 놓여졌을 때는, 아래와 같이 array가 형성된다. 1. for(1~N) 아직 놓이지 않은 Queen 찾기 --> 이 말은 &quot.......

boj_17070_파이프 옮기기1 [내부링크]

https://www.acmicpc.net/problem/17070 <풀이> 1. 현재 파이프가 놓인 상태 state 변수에 저장하기 2. switch-case 문으로 state에 따른 다음 파이프 놓는 방법 나누기 3. 파이프의 끝이 (N,N)에 온다면 cnt++, return 이렇게 로직을 짜면 브루트포스 코드가 완성된다 근데 조금 더 생각해보면 이렇게 파이프의 끝이 (4,4)에 state = "세로" 형태로 놓일 수 있는 경우가 여러개 존재하는 것을 알 수 있다. 이렇게 되면 (4,4)에서 다음 칸으로 넘어갈 때 연산을 두 번 시행하는 것이므로 memoization을 통해서 연산 횟수를 줄일 수 있을 거 같다. ex) (4,4)에 state="세로" 이런 상태로 들어왔을 때 찾은 정.......

boj_11054_가장 긴 바이토닉 부분수열 [내부링크]

https://www.acmicpc.net/problem/11054 <풀이> tc1로 예시를 들어보자면 1 5 2 1 4 3 4 5 2 1 이러한 가장 긴 바이토닉 수열이 나오게 된다. sequence[8] =5 인 index를 기점으로 수열의 증가와 감소가 나뉘게 된다. 이 말은 즉, 수열의 증감이 나뉘는 index의 좌측은 LIS(Longest increasing Sequence) 우측은 LDS (Longest decreasing sequence) 를 구하고, 그 합이 최대값이 되도록 하면 된다. --> 각각의 인덱스의 lis와 lds를 구해야함. < LIS 풀이 참고 > https://blog.naver.com/a980917a/222449827685 1. 좌측의 LIS를 구하기 위해선, 수열을 뒤집고 LDS를 구해야한다 이 말이 뭐냐면, 1 5 2 1 4 3 4 5 2 1 이 예시.......

boj_13305_주유소 [내부링크]

https://www.acmicpc.net/problem/13305 <풀이> 문제에서 구하자고 하는 것은 "가장 왼쪽 도시에서 부터 가장 오른쪽 도시까지의" 최소비용이다. 우리가 상식적인 선에서 최소비용으로 어떤 미션을 수행하기 위해선, 최소비용으로 최고의 효율을 뽑아야 한다. 이 문제의 특징을 살펴보면 쉽게 알 수 있다. 이 문제는 무조건 "왼쪽"에서 "오른쪽"으로 순차적으로 도시를 방문해야 한다. 따라서, 어떤 도시에 가기 위해선 이전(왼쪽) 도시에서 충분한 주유를 해야한다. 만약 다음 도시의 주유가격이 그 이전(왼쪽)의 어떤 도시의 주유가격보다 비싸다면 나는 그 도시에서의 주유를 피하기 위해 그 이전의 어떤.......

boj_1931_회의실 배정 [내부링크]

https://www.acmicpc.net/problem/1931 <풀이> 하나의 회의실을 최대한 여러번 사용하려고 하면, 어떤 회의가 가능한 빨리 끝이나야 한다. (그래야 다음 팀이 사용할 수 있기 때문) 따라서 회의가 종료되는 시간을 기준으로 오름차순 정렬을 하고, 가용한 회의를 배치한다면 가장 많은 수의 회의를 택할 수 있다. 하지만 이 경우 한 가지 문제가 발생한다. 만약 (1,4) (6,6) (5,6) 이런 인풋이 들어왔을 경우, 회의가 종료되는 시간을 기준으로 정렬하였기 때문에 (1,4) (6,6) (5,6) 순서로 정렬이 될 것이며, 아래 그림과 같이 회의가 배치될 것이다. 3번 회의의 시작시간이 2번 회의의 종료시간보다 작으므로, 3번 회의는 가용한 회의가.......

Fragment [내부링크]

# 프래그먼트는 하나이상의 액티비티 위에 올라가야한다. (하나의 액티비티에 여러 개의 프래그먼트가 올라갈 수도 있다) # 프래그먼트 xml 파일 1개, kt 파일 1개 1. 우선 이렇게 기본적인 메인 xml 파일을 만든다. 위 그림처럼 선택되어 있는 부분은 "FrameLayout"임. --> 프래그먼트가 들어갈 자리 2. 각 프래그먼트에 들어갈 xml파일을 만든다 3. 프래그먼트 kt파일을 만들어줌. 프래그먼트는 onCreate가 아니라 onCreateView. ( 똑같은 동작이라고 생각하면 됨) setContenView가 없고, inflater로 이렇게 화면을 넣어줌 val view = inflater.inflate(R.layout.프래그먼트들어갈자리id, container, false) (container와 fa.......

boj_1780_종이의 개수 [내부링크]

https://www.acmicpc.net/problem/1780 <풀이> 조건2에서 1을 충족하지 않을 경우, 종이를 같은 크기의 9개로 자르고 조건1을 충족하는지 검사한다고 하였으므로, 분할정복으로 접근해야겠다고 생각하였다. 먼저 can_use 함수를 이용하여, 조건1을 만족시키는지 검사하였다. 간단하게 설명하자면, nxn 행렬에 적힌 숫자가 모두 같아야 true 이므로, matrix[1][1]의 값을 flag로 설정하여 O(n^2)으로 모든 원소들이 같은지 비교하였다. 만약 true가 리턴된다면, 사용가능한 종이이므로 그 값을 0,1,-1로 나누어 개수를 카운팅 해주었다. false가 리턴된 경우, 종이를 같은 크기의 9개로 나누어야했는데, drow와 dcol 배열을 이용해서 각 sta.......

boj_17135_캐슬 디펜스 [내부링크]

https://www.acmicpc.net/problem/17135 삼성기출문제를 접한지 얼마되지 않아 코드가 조금은 비효율적이고 중구난방한 느낌이 든다. 근데 뭔가 조금 다르게 생각하면, 이런 코드가 통과되는 걸로 봐선 로직이 정확하기만 하면 타임아웃에 대해선 굉장히 후한 느낌이다.ㅋㅋ 이 문제를 푸는데 4시간 정도 걸린 거 같다. 사실은 뭐 도저히 모르겠어서 '맞왜틀?' 하다가 결국 질문게시판 반례 케이스로 디버깅했다. 알고보니 "가장 가깝고, 가장 왼쪽에 있는 적"을 선택하는 조건에서 문제가 있었다. 코드를 수정하고 보니 어려운 구현은 아니었던 거 같은데 그저 꼼꼼함이 부족했던 거 같다. 다음부턴 조건 한 줄 한 줄 천천.......

boj_2178_미로탐색 [내부링크]

https://www.acmicpc.net/problem/2178 <풀이> 1. 우선 미로의 상태를 나타낼 array, visit 여부를 확인할 array, 몇번째 이동만에 해당 인덱스에 왔는지 확인할 array 이렇게 총 3개의 array를 만들었다. 2. (1,1)을 시작으로 bfs를 돌며 board[i][j] = 1 인 칸은 visit[i][j] = 1 (방문처리), cnt[i+1][j+1] = cnt[i][j]+1로 지나온 칸수를 카운팅 해주었다. 3. 최종 목적지인 (N,M)에 도달하기 위해 지나친 칸 수 출력 cnt[N][M] <코드>

boj_7576_토마토(2차원) [내부링크]

https://www.acmicpc.net/problem/7576 <풀이> 만약 이런 인풋이 들어왔다고 할 때 이런 트리로 표시된다. 위 그림을 통해 depth가 1증가 할 때 마다 익은 토마토들은, 자신과 인접해있는 익지않은 토마토들을 익게 만든다는 것을 알 수 있다. --> 모든 토마토들이 익었을 때, 만들어지는 tree의 depth를 측정해야 함.(depth = 모든 토마토가 익는 최소 날짜) 1. get_tomato()를 통해 input에서 사전에 익어있는 토마토들의 좌표를 Queue에 push 2. all_tomato()를 통해 모든 토마토가 익어있는 input이 들어오는 case 처리 3. bfs로 탐색을 하며 depth 측정 --> 최종 depth를 측정하기 위해서 각 depth마다 노드의 개수를 카운.......

boj_7562_나이트의 이동 [내부링크]

https://www.acmicpc.net/problem/7562 <풀이> board 2차원 array에 해당 칸에 가기 위해 지나친 칸 수를 저장하였음. --> for문으로 8방향 중 진행이 가능한 방향을 찾고, 진행이 가능하다면, board[i+1][j+1] = board[i][j] + 1 <코드>

boj_7569_토마토(3차원) [내부링크]

https://www.acmicpc.net/problem/7569 <풀이> https://blog.naver.com/a980917a/222493042385 위의 문제와 같은 조건에 토마토를 담는 상자가 단일층 --> 다층으로 바뀌었다. 풀이는 동일 !! ### 까먹지 말자 ### 3차원 array에서 array[높이][가로][세로] !!!! <코드>

boj_1707_이분그래프 [내부링크]

https://www.acmicpc.net/problem/1707 <풀이> 이 문제를 풀면서 이분그래프라는 것을 처음 들어봤다. 우선 주어진 예제로 이분그래프가 뭔지 생각해보면 tc1) 이 경우엔, 노드를 두개의 집합으로 나누는 경우의 수는 {공집합} & {1,2,3} {1} & {2,3} {2} & {1,3} {3} & {1,2} 이렇게 4개의 경우가 존재한다. 이 때 각 집합의 원소들이 서로 인접(연결)하지 않는 경우의 수 {3} & {1,2} 가 존재할 때, 이분그래프라고 한다. tc2) 노드들을 2개의 지합으로 나누는 경우의 수를 적어보면, {공집합} & {1,2,3,4} {1} & {2,3,4} {2] & {1,3,4} {3} & {1,2,4} {4} & {1,2,3} {1,2} & {3,4} {1,3} &.......

boj_2206_벽 부수고 이동하기 [내부링크]

https://www.acmicpc.net/problem/2206 <풀이> 처음에 다른 일반적인 bfs문제와 같이 갈 수 있는 길을 찾아서 최종 도착지에 도달했을 때 tree의 depth를 출력하는 코드 + 벽을 부수는 조건문 이렇게 풀면 풀릴거라고 생각했는데 당연히 틀렸었다 !! 늘 그랬듯이 이왜틀을 시전하다가 이 예제에서 분명히 오른쪽 3칸, 아래쪽 4칸 이동 후 벽을 부수고 최종 목적지 도착. 즉 정답은 9 가 출력되길 원했는데 이상하게 15가 나왔다. 15는 이처럼 가장 먼 길로 돌아가는 경우다. 왜 이런일이 발생했을까를 생각해보니, 애초에 위에 파랑색으로 표시된 경로는 코드가 실행되지도 않았다.. 우선 내가 정한 bfs탐색순서에서는 위 그림에서 노랑색.......

프로그래머스 LV1 ) 크레인 인형뽑기 게임 (2019 카카오 겨울인턴) [내부링크]

<문제> https://programmers.co.kr/learn/courses/30/lessons/64061# <풀이> 1. board 2차원 ...

boj_1451_직사각형으로나누기 [내부링크]

<문제> https://www.acmicpc.net/problem/1451 <풀이> 하나의 직사각형이 세 개의 작은 직사각...

boj_17305_사탕배달 [내부링크]

<문제> https://www.acmicpc.net/problem/17305 <코드> <풀이> 1. 우선 3g, 5g 두 종류...

boj_1697_숨바꼭질 [내부링크]

<문제> https://www.acmicpc.net/problem/1697 <코드> <풀이> BFS 문제를 처음 풀어...

boj_5214_환승 [내부링크]

<문제> https://www.acmicpc.net/problem/5214 <풀이> 1. 우선 처음 떠올린 풀이 방법은 벡터 ...

boj_12865_평범한배낭 [내부링크]

<문제> https://www.acmicpc.net/problem/12865 <풀이> 1. 물건들의 정보를 pair로 담아 vecto...

boj_16562_친구비 [내부링크]

<문제> https://www.acmicpc.net/problem/16562 <풀이> 0 - 1 ) 이런식으로 친구가 6명이 있을...

Union-Find [내부링크]

내가 취직하는 그 날까지

세그먼트트리 (SegmentTree) [내부링크]

내가 취직하는 그 날까지

FenWikTree(펜윅트리) [내부링크]

내가 취직하는 그 날까지

aoj_CLOCKSYNC [내부링크]

https://www.algospot.com/judge/problem/read/CLOCKSYNC <풀이> 1. 모든 시계는 버튼을 누...

aoj_PICNIC [내부링크]

https://www.algospot.com/judge/problem/read/PICNIC < 풀이 > 1. 처음에는 0번 학생부터 시...

aoj_BOARDCOVER [내부링크]

https://www.algospot.com/judge/problem/read/BOARDCOVER <풀이> 간단하게 문제를 설명하...

aoj_QUADTREE [내부링크]

https://www.algospot.com/judge/problem/read/QUADTREE <풀이> 우선 쿼드트리는 재귀로 호...

aoj_FENCE [내부링크]

https://www.algospot.com/judge/problem/read/FENCE <풀이> 모든 경우를 다 구해서 가장 큰 값...

aoj_JUMPGAME [내부링크]

https://www.algospot.com/judge/problem/read/JUMPGAME <풀이> 1. 이렇게 (1,1)에서 (5,4)...

Github 파일 올리기 [내부링크]

Github에 커밋 하는 법 매일 까먹어서 정리 1. Github에서 레포지토리 만들기 2. 이 레포지토리와 연동할...

DoitMission-03 [내부링크]

< Mainactivity.java > 1) 각 view 들의 object 선언해주고 2) onCreat() 함수에 각 view들 id값을...

Button 바꾸기 [내부링크]

1. Button을 내가 원하는 사진으로 바꾸기 1) drawable폴더에 사진 넣기 2) "이미지 버튼" 을 ...

Git Branch 하는 법 [내부링크]

0. 리포지토리에 파일 생성 1. branch 생성 ※ git branch --> 현재 branch 상태 2. git checkout 브랜...

aoj_LIS [내부링크]

https://www.algospot.com/judge/problem/read/LIS <풀이> tc 두번째 5 4 3 2 1 6 7 8 을 예시로 ...

aoj_WILDCARD [내부링크]

https://www.algospot.com/judge/problem/read/WILDCARD <풀이> 1. file_name과 wildcard를 ...

Intent로 다른 액티비티 띄우기 [내부링크]

앱에서 화면을 전환한다 => 다른 액티비티를 띄운다. 따라서 전환할 액티비티 화면을 새로 만들어...

aoj_TILING2 [내부링크]

https://www.algospot.com/judge/problem/read/TILING2 <풀이> 처음엔 아래 코드처럼 for문을 ...

aoj_ASYMTILING [내부링크]

https://www.algospot.com/judge/problem/read/ASYMTILING <풀이> TILING2를 풀면서...

aoj_TRIANGLEPATH [내부링크]

https://www.algospot.com/judge/problem/read/TRIANGLEPATH <풀이> 1. 위 그림처럼 표...

aoj_NUMBERGAME [내부링크]

https://www.algospot.com/judge/problem/read/NUMBERGAME <풀이> 예제 -1000 -1000 -3 -1...

aoj_LUNCHBOX [내부링크]

https://www.algospot.com/judge/problem/read/LUNCHBOX <풀이> 1. 간단하게 해석해보자면, ...

aoj_ALLERGY [내부링크]

https://www.algospot.com/judge/problem/read/ALLERGY <풀이> 우선 input처리가 까다로웠다. 친구의 이름을 저장할 배열, 각 친구가 먹을 수 있는 음식들을 저장할 배열, 각 음식마다 먹을 수 있는 친구의 번호를 저장할 배열, 각 친구마다 현재 먹을 수 있는 음식 개수를 저장할 배열 이렇게 4개의 array를 만들었다 TC 1번을 예시로 들어보면 <친구 이름 저장 배열> <각 친구가 먹을 수 있는 음식들을 저장할 배열> <각 음식마다 먹을 수 있는 친구의 번호> <각 친구마다 현재 먹을 수 있는 음식의 개수> 1. for문으로 먹을 음식이 없는 친구 탐색 (all_eat() -> 모두 먹을 음식이 있으면 return 0, 아니라.......

boj_1260_BFS와DFS [내부링크]

https://www.acmicpc.net/problem/1260 <풀이> 간단히 DFS와 BFS만 구현하면 된다. 1. 양방향 간선이므로 이렇게 양쪽 모두에 next 후보가 될 수 있도록 넣어주어야 한다. 2. visit[1001]을 이용하여 해당 node가 방문 되었는지를 표시하고, 방문되었다면 next 후보에서 제외하였다. <코드>

boj_2606_바이러스 [내부링크]

https://www.acmicpc.net/problem/2606 <풀이> 우선 제일 먼저 떠오른 방법은 Union-Find 이다. input을 받으면서 노드들을 연결시켜주고, for문을 돌며 부모노드가 1인 노드들을 카운팅 해주면 정답이 나올 것 같다. 두 번째로 한 노드를 방문하고 그것의 next를 구하여 DFS 탐색을 하는 방법이다. 두 번쨰 방법으로 구현하였다. 각 노드들을 방문할 때 마다 카운팅 해주었음.

boj_1012_유기농배추 [내부링크]

https://www.acmicpc.net/problem/1012 <풀이> 1. input으로 받은 2차원 array에서 배추가 있고 (array[i][j] = 1), 아직 방문하지않은 (visit[i][j] = 0) index 찾기 2. 1번에서 찾은 array[i][j]를 start로 두고, bfs로 탐색하며 인접해있는 배추들 visit처리. 3. bfs가 끝났다는 의미는, 한개의 배추 단지(?) 탐색을 마쳤다는 의미이므로 지렁이수 +1 (cnt++) <코드>

실시간 검색어