| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 15 | 16 | 17 | 18 | 19 | 20 | 21 |
| 22 | 23 | 24 | 25 | 26 | 27 | 28 |
| 29 | 30 | 31 |
- dfs
- 임베디드
- Stack
- 다이나믹프로그래밍
- 그리디
- 통신 인터페이스
- C
- 컴퓨터비전
- BFS
- 누적합
- 우선순위큐
- 이분탐색
- 구현
- 자바
- 컴퓨터 비전
- c++
- dp
- 코틀린
- 백준
- kotlin
- level2
- 다이나믹 프로그래밍
- java
- JavaScript
- 프로그래머스
- 2018 KAKAO BLIND RECRUITMENT
- level3
- lv2
- cpp
- 동적계획법
- Today
- Total
목록level3 (7)
코드를 느껴바라
문제 링크성공 여부(걸린 시간): 71.4점 실패 → 정답 (총 43분 33초)아이디어처음에는 그리디하게 열 기준으로 진행했다.1열을 먼저 맞추기 위해 필요한 행을 전부 뒤집고이후 각 열마다전부 같으면 그대로전부 다르면 열 토글섞여 있으면 불가능이런 식으로 처리했다.하지만 실패 원인은 명확했다.첫 열에서 무조건 행을 뒤집는 선택을 해버리면서가능한 해의 절반을 날리고 시작한 것. 왜 그리디가 안 되는가? 이 문제는 단순 구현 문제가 아니라XOR 조건을 만족하는 행/열 선택 문제다.행을 뒤집었는지 여부를 r[i], 열을 뒤집었는지 여부를 c[j] 라고 하면최종 상태는beginning[i][j] XOR r[i] XOR c[j]가 된다. 우리가 원하는 것은 이것이 target[i][j] 와 같아지는 것.따라서 ..
문제링크성공 여부(걸린 시간): 성공(1시간 20분 21초)아이디어두 수레(빨간/파란)를 동시에 이동시키며 각각 도착지에 도달하는 데 필요한 최소 이동 횟수를 구해야 한다.두 수레는 다음 조건들을 만족하며 이동해야 한다.서로 같은 칸을 동시에 점유할 수 없음 서로 자리를 교차해 지나갈 수 없음 도착지에 도착한 수레는 더 움직이지 않음 각 수레는 이미 자신이 이동했던 칸을 다시 방문할 수 없음 벽(5)은 이동 불가BFS 사용 상태는{R_x, R_y, B_x, B_y, 이동 횟수} 각 상태에서 양쪽 수레가 독립적으로 상하좌우 움직임→ 최대 16가지 경우 탐색방문 체크는 boolean[N][M][2] 형태로각 수레가 방문한 칸을 저장 단, 두 수레의 동시 이동 + 교차 불가 등 제약 때문에visi..
문제 링크걸린 시간(성공 여부): 1시간 (실패)아이디어처음에 뒤집혀있는 삼각형 기준으로 dp를 사용해야 겠다는 생각은 했으나그다음부턴 점화식을 못짜겠어서 포기했었는데 풀이를 보고 푸니 새삼 너무 겁먹은 듯 하다.핵심은 열 i까지 덮었을 때 오른쪽 끝이 마름모로 튀어나와서 다음 열로 이어져야 하는 상태(dp1) 인지,아니면 딱 닫혀 있는 상태(dp2) 인지를 나눠서 생각하는 것.dp1[i]: 열 i까지 덮었을 때 오른쪽 끝이 마름모로 튀어나와 있는 경우dp2[i]: 열 i까지 덮었을 때 깔끔하게 닫혀 있는 경우그리고 i열 꼭대기에 삼각형이 붙어 있는지(tops[i-1]) 여부에 따라 경우의 수가 달라짐.점화식은 다음과 같이 됨:dp1[i] = dp1[i-1] + dp2[i-1](이전이 어떤 상태든 i열에..
문제 링크성공 여부(걸린 시간): 실패(44분 48초)아이디어처음에 다양한 방법에 대해서 생각해봤다. ❌브루트포스로 등대의 불 켜짐을 전부 탐색 -> X 10만개임 2^100000리프노드가 있는 경우는 전부 켜주기 ❌-> 왜냐면 리프노드가 있는 노드라면 무조건 리프노드가 달린 노드에 불이 켜져야함-> 연결된 간선이 하나인 리프노드를 기억해두고 해당 리프노드가 연결된 노드를 set에 넣고 마지막에 개수를 세어주면 된다.-> 그러나 0-0-0-0-0-0-0 인 경우엔 3개는 켜져야 하는데 2개 밖에 안켜진다.리프노드에서 출발해서(0으로) 깊이가 홀수인 노드의 개수를 세어준다. ❌-> 그렇다면 그래프를 만들어 연결하고 리프노드에서 DFS로 탐색을 진행하며 depth가 홀수일때 hashSet에 add 해주면 된..
문제 링크성공 여부(걸린 시간): 성공(20분)아이디어DP 기본 개념문제인듯 하다.우측 또는 아래로 밖에 이동을 못하고 웅덩이로는 갈 수가 없다.map에 웅덩이를 -1로 표시해주고dp배열을 따로 만들어서 진행해주었다.점화식은 이렇다dp[i][j] = (map[i-1][j]!=-1?dp[i-1][j]:0) + (map[i][j-1]!=-1?dp[i][j-1]:0)위에서 저장된 dp값과 왼쪽에서 저장된 dp값즉 해당 칸에 도달하기 이전 칸까지 갈 수 있는 경우의 수를 웅덩이가 아니라면 합해준다.그럼 끝.풀이 코드import java.util.*;class Solution { public int solution(int m, int n, int[][] puddles) { int answer =..
문제 링크성공 여부(걸린 시간): ❌(20분)아이디어처음에는 순서를 전부 브루트포스로 조합하면 최대 17개의 노드를 0을 제외하고 모든 순서대로 조합했을때는 16! 이다. 사실 16!은 엣지를 생각치 않고 진짜 전부 돌려본 경우고만약 실제 노드 연결을 고려해서 노드 방문 순서를 작성하면 결국 연산수는 동일하지 싶다. (이진트리이기 때문에) 그당시엔 그렇게 생각을 못했고 생각한건 DFS로 해야한다는 것이었는데 방문한 노드들의 자식노드로 이동할때해당 노드의 다른 자식 노드도 다음 이동할 방문 리스트로 추가해야 했다. 그런데 도저히 방법이 떠오르지 않았고 그렇게 LV2라고 생각하고 있어서 20분이 지나자실패처리하고 힌트를 보았다... (알고보니 레벨 3 였음ㅎㅎ) 😅여기서 힌트를 보고 바로 풀어보았다. [P..
문제 링크성공 여부(걸린 시간): 성공(1시간 34분 17초)아이디어우선 문제를 읽으면서 부르트포스라고 확신을 했다.이유는 우선 주사위의 각 면에 어떤 숫자가 있는지는 주어진다.(6면체임)그리고 n이 최대 10이라 최대 경우의 수는 6^5 X 6^5 = 약 6000만이므로 시간은 충분하다고 가정했다.(보통 10초임)그래도 구현은 꽤나 복잡했는데 복잡할 수록 미리 설계를 하고 코드를 짜는것이 좋다고 생각해서 설계를 열심히 해보았다.시작) 일단 순서는 주사위 분배 String타입(예: n==4일때 1,4 주사위면 "14"이런식) 그리고 점수 빈도 계산A, B가 들고갈 주사위 조합을 dicePermutation에서 ArrayList로 전달한다. 만들어진 조합을 저장하기 전에 그에 해당하는주사위 조합으로 만들 ..
