Problem Solving (BOJ)

Substring: 전체 문자열에서 연속된 부분 문자열Subsequence: 전체 문자열의 부분 문자열 (연속되진 않아도 됨, 순서만 맞으면 됨)비교하고자 하는 문자열을 각각 행, 열로 배치문자를 비교하여 같았을 때 -> 현재 칸에 들어갈 값은 대각선 왼쪽 위의 값 +

A 받을 때 str을 int로 map, map객체를 list로 변환N이 1,000,000이라 O(N)으로 처리해야함stack에는 A를 순회하며 A의 index를 저장Ai이 A\[stack-1] 보다 크면 ans\[stack-1]에 Ai를 저장for문에서 반복할 때마다

N이 최대 1,000,000이라서 list의 count()를 쓰기에는 시간 초과 발생 (count()는 원소 하나 당 O(N)의 시간복잡도 -> 각 원소의 개수를 모두 구하려면 O(N^2))collections module의 Counter를 사용Counter()는 각

우선순위: '(', ')' >>> '\*', '/' >>> '+', '-'입력받은 중위 표기식을 순회하면서 진행피연산자인 경우 바로 result string에 concat'('인 경우에는 stack에 append -> 괄호 시작의 flag 역할')'인 경우에는 괄호 시

dp table에서 ans와 값이 같은 index를 찾고, 그 index부터 역순으로 내림차순으로 순회하며 가장 긴 증가하는 부분 수열을 찾음

brute force로 해결0부터 1000000까지 순회하며 모든 경우를 확인함(채널은 무한대만큼 있기 때문에, 500000이하만 순회할 경우, 고장난 버튼이 3, 4일 때 N이 510000일 경우 최솟값은 6인데 10000로 출력됨)초기 최솟값을 abs(N-100)으

dfs를 이용해서 left, right, down, up 하는 경우를 각각 탐색함recursion으로 dfs를 구현함4방향, 총 5번 이동 (4 ^ 5 = 1024의 경우)모든 방향 탐색을 마친 후 (cnt가 5일 때), block에서 최댓값을 찾아, 전역변수 ans를

위의 그림과 같은 방식으로 진행 됨보드를 나타내기 위해 board라는 이름의 2차원 list를 정의함기본값: 0, 뱀의 위치: 1, 사과 위치: 2snake의 좌표를 저장하기 위해 depue(())를 사용함뱀의 머리는 snake-1, 뱀의 꼬리는 snake0임회전하는

초기 상태의 dice가 0, 1, 2, 3, 4, 5라고 할 때,cmd == 1 (동쪽 이동)3, 1, 0, 5, 4, 2cmd == 2 (서쪽 이동)2, 1, 5, 0, 4, 3cmd == 3 (북쪽 이동)4, 0, 2, 3, 5, 1cmd == 4 (남쪽 이동)1,

총 19가지의 테트로미노가 나옴board에서 모든 칸을 순회하면서 19가지의 테트로미노의 경우를 모두 고려하여 최댓값을 구함 (brute force/ 500 500 19)dshape 다차원 list를 정의하여 19가지의 테트로미노의 dx, dy를 저장함

역순으로 dp table 채워야함i가 N-1부터 0까지 순회할 때,스케줄상 아예 일을 할 수 없는 경우Ti + i > N인 경우임. 이 경우는 dpi를 dpi+1로 채워줘야함 (뒷부분 날짜인 경우 0으로 채워주기 위해 dp를 N+1만큼 0으로 초기화해줌)일을 할 수 있

brute force로 해결벽을 세울 수 있는 모든 좌표를 walls에 저장함recursion을 사용한 combination 함수를 통해 walls에서 3개의 tuple을 선택하는 조합을 all_wall에 저장함all_wall에 있는 원소들을 모두 순회하면서 가장 sa

반시계방향으로 90도 회전 -> d = (d+3)%3청소한 좌표를 N\*M 크기의 list를 생성하여 1로 표시함 (visited)

N과 K의 관계를 찾아내기 위해 2차원 table로 경우의 수를 구해봄dpi = dpi-1 + dpi의 점화식을 구할 수 있음

dp1은 가장 긴 증가하는 부분 수열의 길이임dp2는 가장 긴 감소하는 부분 수열의 길이인데, 현재 index에서 끝 index까지를 고려함A를 역순으로 정렬한 수열에 대해 가장 긴 증가하는 부분 수열을 구하고, 이를 다시 역순으로 정렬하면 dp2를 구할 수 있음dp1

dp1은 수열에서 수를 제거하지 않은 경우의 연속합임dp2는 수열에서 수를 제거하는 경우의 연속합임. 이 경우에선 2가지 case를 고려해야함case 1) Ai를 제거하는 경우case 2) i 이전의 index를 이미 제거하여 Ai를 제거할 수 없는 경우case 1)과

1번 집의 색과 N번 집의 색이 같지 않아야 한다는 조건을 처리해줘야함\-> for문을 3번 돌며1번 집의 색이 빨강일 때 -> N번 집의 색은 초록 or 파랑1번 집의 색이 초록일 때 -> N번 집의 색은 빨강 or 파랑1번 집의 색이 파랑일 때 -> N번 집의 색은

n이 홀수면 0매번 새로운 모양이 2개씩 추가됨dpn = dpn-2 \* dp2 + (dpn-4 + ... + dp2) \* 2 + 2

브루트포스로 풀면 시간 초과가 발생함x % N == y % N을 만족하는 x, y가 있는지 확인해야함\-> x를 N으로 나눈 나머지가 y를 N으로 나눈 나머지와 같을 때까지 x에 M을 더해줌

backtracking을 이용한 풀이backtracking은 기본적으로 brute force 전략을 취하지만, 처리 속도를 향상시키기 위한 pruning이 중요한 역할을 함

출력되는 수열이 오름차순이어야 하기 때문에, flag를 dfs()의 인수로 넘겨줘야함

같은 수를 여러 번 고를 수 있도록 구현

중복 가능 + 비 내림차순

입력받은 수열에서 backtracking

오름차순 조건 추가

같은 수를 여러 번 고를 수 있도록 구현

비 내림차순 조건 추가

탐색한 노드 (visited node)를 저장하기 위한 자료구조로 visit list를 사용 (index별로 true, false가 저장됨)위의 그림에서 보이는 것처럼 같은 depth에서 값이 같은 경우는 pruning을 해야하기 때문에 flag 변수를 이용해 같은 d

비 내림차순 조건 추가\-> idx_flag를 dfs function의 input parameter로 추가하여 구현함

같은 수를 여러 번 고를 수 있도록 구현

비 내림차순 조건 추가같은 수 여러 번 고를 수 있도록 구현

dfs 이용하여 모든 node 순회

모든 node를 순회하여 각 정수들의 차이의 최댓값을 구함배열 안에 정수들이 같은 수가 들어있을 수도 있기 때문에 visit = False \* N을 정의하여 모든 node들을 순회할 수 있도록 구현함

dfs를 이용하여 모든 도시들을 순회함len(nodes) == N일 때, 가격을 계산하기 시작함\-> min_value가 global minimum value임 (해당 경우마다 min_value를 갱신해줌)\-> 길이 없는 경우에는 바로 return 해줌\-> 마지막에

dfs순회하면서, 오름차순으로 출력될 수 있도록 index flag를 input parameter로 설정해둠

처음에 위의 코드와 같이 dfs로 접근했는데, runtime error (recursion error)가 발생함그래서 위의 그림처럼 다음 순열을 구하는 방법을 찾아보았고, 그 결과는 아래와 같음1) 뒤에서부터 순회하며 뒤의 수(=t)가 앞의 수(=h)보다 큰 경우 둘을

다음 순열 문제와 마찬가지로 이전 순열을 구하는 방법을 찾음1) 뒤에서부터 순회하며, 뒤에 있는 수(=t)가 앞에 있는 수(=h)보다 작은 경우, 이 둘을 swap 함2) t의 뒤에 있는 수부터 끝까지 내림차순으로 정렬해줌

letter list를 오름차순으로 sorting오름차순으로 dfs 순회len(visit) == L일 때, 모음 최소 하나, 자음 최소 두개 조건을 만족하는 경우에 print

능력치를 빠르게 search 할 수 있는 방법을 구해보려 했다가 그냥 안구함person list를 만들고 N/2의 depth로 dfs를 오름차순으로 순회하여 팀을 구성할 수 있는 모든 경우의 수를 구함link팀의 선수는 start팀의 선수와 중복되지 않고, 선수는 중복

[스타트와 링크] 문제와 마찬가지 방식으로 접근함팀원 수가 일치하지 않는 경우까지 고려해야하므로 N//2 이하의 depth를 모두 순회해야함

모든 수의 조합을 순회해서 len(visit) == k+1일 때 유효성을 검사하면 당연히 시간 초과가 발생함 (10의 10승)따라서 depth 마다 확인 작업이 필요함이를 위해선 dfs()에서 인자로 현재 depth와, 이전 숫자 (before_number)를 넘겨주어

구하고자 하는 sequence of integers에서 integer set이 {-10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}으로, 총 21개임 -> 모든 경우를 확인한다면 시간 복

depth를 1부터 N까지 변경시켜주며 dfs를 순회하여 조건을 만족시키는 부분수열들을 구함depth 1 -> 원소가 1개인 부분수열depth 2 -> 원소가 2개인 부분수열 ..계속 틀리길래 원인을 못 찾고있다가 다음날 다시 보니까 수열은 원소들이 중복되는 경우가 있

직사각형을 조각들로 자르는 걸 구현하는게 감이 안잡혔음 -> bitmasking을 처음 이용해봄입력받은 Paper를 1차원으로 indexing 함 -> 조각들로 자르는 모든 경우의 수 = 2 ^ (N \* M)가로방향 확인: i & (1 << idx) !=

adjacent list를 이용하여 graph를 구현함해당 graph를 dfs를 통해 순회하면서, depth가 5인 경우가 생기면 possbile_flag = 1로 할당조건에 맞는 A, B, C, D, E가 존재하면 1 출력 -> dfs의 depth가 5면 1 출력de

bfs는 queue 자료구조를 사용함 (시간복잡도를 고려하여 deque 객체 사용)adjacent list에서 first in first out 으로 인접한 node들을 먼저 탐색해줌

위의 그림과 같이 graph가 형성되어 있는 경우, 연결 요소가 2개 있다고 함for문을 통해 N만큼의 시작 node들을 순회하면서 그 결과값을 set형식으로 check list에 저장해둠len(check)이 연결 요소의 개수가 됨

이분 그래프를 판별하기 위해서, depth마다 color 값을 1과 -1로 번갈아가면서 할당해줌 -> 만약 이전 depth의 node와 현재 depth의 node가 같은 color라면, print("NO") 처음에 Recursion error가 발생해서 "sys.s

2중 for문을 돌며 Map이 1인 경우 dfs 순회 시작Map 밖을 접근하는 경우 returnMap에서 해당 위치의 값이 1인 경우 count +=1을 해주고 해당 위치를 0으로 바꿔줌. 그 후 주변 (dx = 0, 0, -1, 1, 1, -1, 1, -1, dy =

0, 0부터 시작하여, bfs순회를 하면서 Map의 값이 1인 경우에 상하좌우 탐색nx = x + dxi; ny = y + dyi는 new x, y 좌표queue에 nx, ny 좌표를 넣어주고, Mapnx에 이전 depth의 Map값 (Mapx) + 1을 할당해줌

최소 날짜 -> bfsMap에 1이 두 개 이상인 경우가 있으므로, 먼저 first_one list에 1의 좌표를 넣어줌\+) 후에 deque에도 할당Mapnx가 0인 경우에 Mapx + 1의 값을 할당해줌bfs() 종료 후, 0이 있다면 print(-1) 해주고 프로

bfs 순회 + 나이트의 이동 규칙에 따라 dx, dy list 변경

사이클이 존재하는 지 확인 -> dfs를 순회하면서, 처음 시작한 좌표로 돌아오는 경우가 있는 경우 "Yes" 출력하도록 구현하면 됨/ 해당 경우가 없는 경우는 "No" 출력2중 for문을 돌면서 Map에 있는 모든 cell을 순회했음 (시간 초과 안걸리니까 그냥 패스

초반에 생각했던 알고리즘처음에 작성한 코드 (Recursion error, 시간 초과 발생)check_cycle()을 통해 먼저 cycle이 생기는 node들을 찾고 cycle (set) 에 저장해놓음그 후 distance()를 통해 다시 dfs를 순회하면서 cycle

bfs를 통해 모든 경우를 순회하면서 curr == K인 경우에 bfs의 depth 출력걸린 시간은 bfs의 depth임\-> bfs의 depth는 visit list를 이용하여 구할 수 있음\-> visitnext_position = visitcurrent_posit

최단시간->최단경로->bfsX\*2는 X+1, X-1과 달리 0초 걸리기 때문에, 우선 순위를 더 높게 주어야함우선 순위를 높게 주기 위해 X\*2를 하여 도착한 위치는 queue의 head쪽에 값을 넣음visit list를 초기화 할 때, X\*2의 경우는 0초가

bfs의 path를 구하기 위해서, path라는 이름의 list를 생성하여, queue에 node를 append 할 때마다 path에 이전 노드를 저장해줌 (자식 노드에 부모 노드를 저장)이런 식으로 저장된 연결 관계를 이용하여 K부터 시작해 역순으로 최단 경로의 pa

최소 시간 -> 최단 거리 -> bfs처음에 작성한 코드 (메모리 초과 발생)state들을 list에 모두 담아놓는 방식에서 메모리가 낭비된듯\-> visit라는 이름의 dictionary 자료형을 사용\-> visit(stdout, clip board) = secon

visit이라는 이름의 미로와 같은 크기의 2차원 list를 통해 부수어야하는 벽의 최소 개수를 저장해놓음visit list의 값들을 -1로 초기화visitx == -1 일 때 queue에 (nx, ny)를 append(nx, ny)가 벽이라면, 즉 Mapnx == 1

처음에는 같은 depth의 원소들끼리 sort() 하여 같다면 1을 출력하도록 구현했음근데 이렇게 하면 부모 노드들의 순서에 따라 자식 노드들의 순서도 달라지기 때문에 틀린 방식임따라서 children 이라는 set으로 구성된 list를 생성하여, 부모 노드들의 자식

i + j가 짝수이면처음 시작이 W일 경우 boardi는 W여야함처음 시작이 B일 경우 boardi는 B여야함i + j가 홀수이면처음 시작이 W일 경우 boardi는 B여야함처음 시작이 B일 경우 boardi는 W여야함

dfs 순회하면서 섬의 개수 구하기

최소 며칠이 걸리는 지 -> bfsbox에서 처음에 1이었던 좌표를 start 리스트에 넣어둠start에 있던 좌표들을 기준으로 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 방향을 탐색\-> boxnhnj == 0인 경우, boxnhnj에 boxhj + 1을 할당해주고, qu

재귀로 구현전위 순회 (preorder): root -> left -> right 순서중위 순회 (inorder): left -> root -> right 순서후위 순회 (postorder): left -> right -> root 순서

인접리스트를 통해 노드간의 관계 그래프를 표현visit 리스트를 통해 노드를 방문했는 지 방문하지 않았는 지를 확인1번 컴퓨터부터 시작하여 dfs 시작\-> 'visit 리스트 원소들의 총합 - 1'이 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수가 됨

python의 heapq 묘듈을 사용하여 구현

visit 2차원 리스트로 출발지점부터의 거리를 저장해둠visit == -1이라면 아직 방문하지 않은 노드\-> Map == 1이라면 visitnx = visitx + 1 (진행 가능)\-> Map == 0이라면 visitnx = 0 (진행 불가능)히든 테케를 찾지 못

Divide & Conquer -> 재귀로 풀이conquer 함수에서 (0, 0)부터 시작하여 Paper를 순회함\-> 만약 처음 색과 다른 색을 만났다면 정사각형을 4부분으로 나누어 재귀 호출\-> return 이후에 color에 따라 색 count를 1 증가시켜줌

시간 초과 발생\-> 모든 부분을 재귀 호출하지 말고, r, c의 위치의 cnt만 효율적으로 구해야할듯1) x > r or x+N <= r or y > c or y+N <= c: 굳이 재귀 호출을 하지 않아도 되는 경우 (단위 정사각형 외의 경우) -> cn

구현 문제 너무 어렵다 디버깅할 때 시간이 너무 오래 걸림shark_position_x, shark_position_y는 상어의 현재 위치shark_size는 상어의 현재 크기shark_current_eat은 상어가 현재 크기에서 먹은 물고기의 개수answer는 상어가

dfs와 bfs 두 가지 방법 모두로 구현이 가능함visit 리스트를 이용하여 자식 노드의 위치에 부모 노드를 저장함

dfs를 두 번 순회하여 해결1번이 루트 노드이고, 이 노드가 트리의 지름을 구할 때 중앙이 되는 노드임1번에서 거리가 가장 먼 노드를 구함 (= farest)farest에서 가장 거리가 먼 노드를 구함각 노드별 weight 누적 값 (거리)는 visit 리스트를 이용

1967번과 같은 방식으로 풀이함dfs를 두 번 순회하여 1번 노드에서 가장 먼 노드를 찾고, 찾은 노드에서 가장 먼 노드를 찾음visit 리스트를 이용하여 거리 저장

그리디 알고리즘을 쓰는 경우 -> 지역의 최적성이 최종 최적성을 보장할 때

딕셔너리 자료형을 이용하여 주사위의 밑면에 해당하는 윗면을 index로 매칭해줌brute force로 모든 경우를 확인해봐야함 (1번 주사위를 돌리는 경우 -> 6가지)시간 제한 및 메모리 제한을 고려하여 tmp_dice를 선언해주고 여기에서 윗면과 밑면을 제거해줌\-

어렵,,is_dfs랑 순서를 맞춰나가면서 dfs 순회를 해야함현재 노드, curr_node는 is_dfs.popleft()를 해서 할당해줌다음 노드는 is_dfs0임is_dfs의 모든 노드들을 출력한 경우 1을 출력하고 종료해줌이 부분에서 curr_node에 연결되어

bfs_partition(): Map에서 섬 별로 색상(color)를 다르게 줌\-> Map의 모든 위치를 순회하면서 섬인 경우 bfs_partition을 호출. visit 리스트를 이용하여 색 입히기를 이미 진행한 섬은 그냥 넘어가도록 구현bfs_bridge(): 처

자릿수가 큰 곳에 위치한 알파벳에 큰 숫자를 매칭해줘야함\-> assn 딕셔너리를 통해 words의 word를 순회하며 각 알파벳들의 자릿수에 따른 level을 계산해줌 (아래 두 사진처럼)dictionary를 value에 따라 내림차순으로 정렬해줌sorted_dict

난 아직도 내가 작성한 코드가 왜 틀리는 지를 모르겠다/ 그래도 일단 기록은 해둠dfs와 백트래킹의 차이: dfs는 완전 탐색을 기본으로 하는 그래프 순회 기법으로 가능한 모든 경로는 탐색함. 백트래킹은 경로는 찾는 도중에 해가 되지 않을 것 같은 경로가 있다면 더 가

1학기때 삼성sds 코테 미궁탈출 문제에서 배열 돌리는 유형이 나왔었는데, 당시에는 for문 엄청 돌면서 삽질했음/ 16926 문제에선 학습을 위해 최적화된 코드를 참조함배열이 회전을 할 때는 껍질별로 회전을 함\-> 때문에 껍질의 개수 (min(N, M) // 2)

N, M, R이 작아서 그냥 빡구현으로 해도 통과함

첫 플래티넘 문제/ 배열 돌리기 3번과 달리 이 문제는 R이 2000000이기 때문에 새로운 아이디어가 필요함우선 기존 arr를 1, 2, 3, 4 부분으로 나누어 origin_arr에 저장함status_updown, status_leftright, status_rot

이 문제는 회전할 톱니바퀴 기준으로 다른 어느 톱니바퀴가 회전을 할건지를 판별해야하는데 그 부분이 좀 어려웠다left(), right() 함수를 구현하여 회전할 톱니바퀴를 기준으로 왼쪽, 오른쪽을 재귀적으로 탐색하여 추가적으로 톱니바퀴를 회전시켜주었다.추가사항) 각 회

그냥 구현 문제candidate list에서 sort()를 쓸 때, lambda를 이용해서 list 원소별로 내림차순, 오름차순으로 설정하여 sorting할 수 있음

stack과 queue, 조건 분기만 조금 신경쓰면 쉬운 문제people이 빌 때까지 while문 순회. 마지막에 남아있는 wait 리스트를 역순으로 정렬한 결과가 order 리스트와 다르다면 BAD를 출력하고 프로세스 종료people: 줄에 기다리고 있는 사람 (qu

2차원 세계지만 1차원 리스트로 풀이블록이 쌓인 높이 리스트 (world)를 순회하면서, "해당 위치의 왼쪽의 최대값", "해당 위치의 오른쪽의 최대값" 중 작은 값에서 해당 위치의 높이를 뺀 값이 해당 위치에 담길 수 있는 빗물의 양임

수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 출력해야함dfs 순회를 하기 전에 먼저 result 리스트를 이용해 나올 수 있는 부분 수열의 합의 모든 공간을 할당해서 -1로 채워넣음dfs 순회를 하면서 모든 부분 수열의 합을 갱신해주고, result

이 문제는 14888: 연산자 끼워넣기와 정답 코드가 같다연산자의 개수가 N-1 보다 크거나 같아도, dfs를 통해 모든 경우를 탐색하기 때문에 같은 return 조건 (if depth == N)과 재귀 방식으로 최솟값을 찾을 수 있다

두 개의 동전 모두의 위치를 독립적인 tuple에 저장해주고 bfs 순회 과정에서 매 단계마다 두 개의 동전 모두를 고려해줘야함nx, ny가 범위 내인 경우, coin1, coin2의 좌표들과 cnt + 1을 queue에 append 해줘야함. 단, 만약 벽인 경우 그

N\*N 체스판에 N개의 Queen을 놓아야하는데, 이때 각 Queen당 좌우상하 대각선에 다른 Queen이 없어야함rows 리스트에 row 별로 어느 col에 Queen이 있는 지를 저장해둠0번 row부터 시작하여 queen 함수 호출\-> 만약 row 번호가 N이라

조건 문 분기하는 부분이랑 for문 빠져나오는 부분에서 조금 삽질을 했다전반적으로 길을 하나씩 탐색해가면서,1) 2칸 이상 높아지거나 낮아지는 경우 거르고2) 1칸 낮아진 경우는 해당 위치의 오른쪽 부분에 경사로를 놓아야 하기 때문에 오른쪽을 L만큼 탐색하고3) 1칸

0-1 knapsack 문제이다. fractional kanpsack 문제는 greedy로 풀 수 있지만, 0-1 knapsack 문제는 dynamic programming으로 풀어야함이 문제의 점화식은 아래와 같다dp 테이블의 값 (dpi, weight)은 i개의 물

dx, dy, cctv_modes 이 세개의 list를 통해 모든 cctv와 각 cctv 별 방향으로 탐색을 진행함dfs 순회를 진행하면서 backtracking을 해줘야하는데, 이때 1) dfs의 input parameter로 Room을 넣어주고, 2) deepco

치킨 거리를 구하는 공식이 그냥 abs(home0 - chicken0) + abs(home1 - chicken1) 이어서 생각보다 간단했던 백트래킹 문제종료조건: depth (선택한 치킨 집의 개수)가 M이 될 때, 최소거리를 구하고 global_distance를 갱신

그리디 알고리즘으로 풀이discussion 리스트를 1) 끝나는 시간의 오름차순, 2) 시작하는 시간의 오름차순으로 정렬해준 후, discussion 리스트의 처음 인덱스부터 회의실을 배정해줌

평이한 brute force (dfs) 및 backtracking 문제dfs 함수에서 input parameter로 가독성을 위해 W를 넣어주기는 했다만, 실제로 list를 parameter로 넘겨줄 땐 값이 아니라 주소가 복사되니까 큰 의미는 없음재귀적으로 함수가

간만에 풀어보는 bfs 구현 문제구슬을 기울여서 움직이는 부분이 신선했다 (네이버 코테 2차에서 이와 비슷한 식으로 구현하는 문제가 있었음)"\_\_boardx+dxy+dy} != '- 굴러간 거리는 1초당 1칸이라고 보고, 굴러간 거리가 작은 색깔의 구슬이 해당 자리

dfs + backtracking 문제일단 zero 리스트의 0번 index부터 시작하여 dfs 진행dfs함수에선 해당 depth의 zero의 위치에 1~9까지 모두 넣어봄\-> checkRow(), checkCol(), checkSquare() 함수를 통해 스도쿠 규

쉬운 backtracking 문제dfs 함수의 인자로 말의 x, y 좌표와 지금까지 지나온 알파벳들을 set 자료형으로 넘겨줌 (in 연산을 할 때, set에선 O(1)임)maxLen을 전역변수로 선언하여 최대값을 구함

combination을 이용하여 candidate에서 M개의 바이러스를 선택하는 모든 경우를 순회하여 result를 최소시간으로 갱신해줌bfs를 통해 모든 경우에 대해 최소시간을 구해줌"17141: 연구소 2"문제와 유사함한 가지 주의해야할 점은 boardi == 2인

간단한 bfs 문제한 가지 주의해야할 점은 npos를 갱신할 때, 뱀인지 사다리인지 확인하고 난 후에 board의 최소시간 갱신 및 queue에 npos를 append를 해줘야함\-> "npos = pos + i" + "npos = laddernpos" 또는 "npos

간단한 bfs 문제인데 시간 복잡도를 조금 신경써줘야하는 문제였다1) visit 리스트를 통해 이미 방문한 노드를 중복 방문하지 않도록 처리해줌2) L연산과 R연산을 처음에는 string으로 변환하고 padding 해주는 방식으로 접근했는데, 그렇게 하면 연산 시간이

A + B + C의 값이 3의 배수가 아니라면 돌을 같은 개수로 만들 수 없으므로 print(0)을 해준다A + B + C의 값이 3의 배수라면 bfs 탐색을 시작한다여기서 포인트가 queue에 노드를 넣어줄 때, A, B, C 세 개 모두를 넣어주는 것이 아니라 두

visit 리스트를 3차원으로 선언하여 벽을 부쉈는 지, 부수지 않았는 지의 두 가지 경우를 확인해줘야하는 게 이 문제의 포인트였다queue에 노드를 넣어줄 때, X, Y, wall을 넣어주어 벽을 부쉈는 지, 부수지 않았는 지를 기록해줌"boardnextX == 1

dfs를 이용한 풀이dfs()는 정상인 경우에 하나의 구역(빨간색 or 초록색 or 파란색)에 대해 0으로 값을 변경해주는 함수dfs_B()는 적록색약인 경우에 파란색 구역에 대해 0으로 값을 변경해주는 함수dfs_RG()는 적록색약인 경우에 빨간색 또는 초록색 구역에

최소 연산 횟수 + 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력 -> bfs로 풀이연산의 순서를 '\*' -> '+' -> '-' -> '/'로 진행함한 가지 막혔던 부분이 s를 t로 바꿀 수 없는 경우였는데, 이 경우는 t가 "1 <= t &lt

bfs 탐색을 하면서 연합의 국가 수(count)와 총 인구수(total), 그리고 해당 국가들의 좌표(coor)를 구해야함\-> visit 리스트로 중복 제거를 하면서 2중 for문을 돌며 bfs 탐색\-> count가 1보다 큰 경우 연합이 있는 경우이므로 coun

사다리가 놓여진 위치 표시를 board 2차원 리스트로 해주었다\-> boardi에서 i는 사다리 가로선의 행번호, j는 사다리 시작점의 열번호depth는 추가한 사다리의 개수임x, y 위치에서부터 사다리를 하나씩 추가로 설치하면서 backtracking을 진행함boa

처음에는 모든 드래곤들을 순회하면서, 드래곤의 처음 위치와 방향을 기준으로 세대만큼 시계 방향으로 90도 회전해서 board에 표시를 해주는 방식으로 구현하려 했으나 구현 방법이 막막해서 실패함구글링을 해본 결과 드래곤 커브의 규칙이 존재함을 확인함만약 처음 시작 방향

그냥 R연산과 C연산을 나누어 빡구현함dictionary sorting\-> value값을 오름차순, 그러한 것이 여러가지면 key값 오름차순 정렬은 아래와 같이 한다sorted_cnt = sorted(cnt.items(), key=lambda x: (x1, x0))R

일반적인 bfs 문제처럼 queue가 빌 때까지 while문을 도는데, 이 문제에선 한 번의 turn마다 이동할 수 있는 경우를 한번에 처리해주어야 한다\-> 현재 queue에 있는 노드의 개수만큼 for문을 돌면서 조건에 맞는 경우에 9가지 방향(현재 위치에 서있는

greedy로 풀이행렬을 변환하는 연산이 3\*3 크기의 부분행렬에 있는 모든 원소를 뒤집는 것이므로, 행렬 A를 순회하면서 행렬 B와 부분행렬의 (0, 0)에 있는 원소가 다르다면 toggle함 (toggle시 cnt 1 증가)순회를 마친 후 A와 B가 다르다면 pr

첫번째 스위치를 눌렀는 지, 누르지 않았는 지를 분리하여 풀이첫번째 스위치 이후부터는 이전 전구를 확인하고, 이전 전구가 다르다면 스위치를 켠다 (이전 전구, 현재 전구, 이후 전구를 켬. 단, i == N-1이라면 이후 전구를 켤 수 없음)\-> 이렇게 이전 전구를

35 mbfs를 돌 때, 현 시점을 기준으로 queue에 들어있는 node들을 한번에 처리해줘야함중복 제거를 위한 visit 리스트도 매 stage마다 초기화해주어야함"고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치

1h 8m결국 히든 테케를 못찾아서 구글링함 + 시간 초과 이슈queue의 노드에 x, y, 진행 시간, 남은 벽의 개수를 저장해줌visit 리스트를 MAX 값으로 초기화해줌boardnx == 0 and visitnxwall > turn 이라면,\-> 벽을 부수지 않고

1h 28m처음에 공기청정기가 작동하는 부분을 시계방향으로 deque에 1차원으로 저장하고 popleft(), append(0) 해주는 방식으로 구현하려 했으나 코드를 짜다보니 너무 꼬여서 이에 대해 dx, dy로 이동하는 방식의 아이디어를 참고했다미세먼지 확장미세먼지

1h 6m시간 초과에서 막혀서 3차원 list로 해결하는 아이디어를 참고함나무에 대한 정보를 3차원 list로 저장한다\-> 이렇게 하면 봄과 여름을 한 번의 2중 for문을 통해 해결할 수 있음\-> for문에서 list의 원소를 삭제하는 부분이 조금 쉽지 않을 수

1h 4m30분 동안 고민하다가 감이 잘 안잡혀서 구글링.. brute force를 할 때 모든 경우를 고려해줘야하는 부분을 어떻게 시작해줘야할 지 가끔씩 감이 잘 안잡힌다. brute force 연습 더 많이 해야할듯N이 10보다 작기 때문에 brute force로

2h 20mlist 인덱싱 때문에 대가리 깨질뻔..N이 작기 때문에 brute force로 모든 경우의 x, y, d1, d2를 찾고, 인구수 차이의 최솟값을 구해야함4중 for문을 돌며 문제의 조건에 맞는 x, y, d1, d2를 찾음그 후 해당 x, y, d1, d

12m모든 'L'대해 bfs로 최단거리 중 가장 긴 거리 (local_result)를 각각 구해주고, 최종적으로 result (보물이 묻혀 있는 두 곳 사이를 최단 거리로 이동하는 시간)을 구해줌

41m코테 준비를 하다보면서 느끼는 게, 문제의 표현이 조금 명확하지 않은 경우도 있다는 점이다. 최대한 꼼꼼히 읽어보고 센스있게 해석하는 자세가 필요할듯.문제에서 시키는 대로 구현하면 되는 문제이다나는 그냥 내구도와 로봇이 있고 없고를 2차원 리스트를 이용하여 저장해

1h 15m"격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다."라는 말이 잘 이해가 안갔는데, 약간 차원 이동처럼 1번 행에서 위로 올라가면 N번 행이고 1번 열에서 왼쪽으로 이동하면 N번

55m거울 개수를 최소로하는 루트를 찾기 위해 한 방향으로 갈 수 있을 때까지 가는 아이디어를 참고함노드에 cnt (탐색하면서 사용한 거울 개수)를 추가해줌bfs를 탐색할 때, 최단거리 루트 + 거울 개수를 최소로하는 루트를 찾아야함\-> nx, ny를 구하고 다음 노

1h 35mpython 내장함수로 2차원 리스트 transpose (-> list(map(list, zip(\*A))) 하는거랑 역순으로 루프 돌리는 거 (-> reversed()) 개꿀인듯일단 direction 리스트를 미리 만들어줌\-> 토네이도의 방향대로 dx,

28m문제의 설명대로 구현하면 됨set에서 in 연산 -> O(1)list -> set으로 바꿔줄 때, list의 원소가 list면 안됨 -> list의 원소를 tuple로 바꿔준 후에 set으로 변환 가능

39mdijkstra 알고리즘을 그대로 구현하는 문제였다처음에 각 노드마다 bfs를 순회하는 방식으로 구현하려했으나 시간초과가 발생했고, 알고리즘 분류를 보고 dijkstra 알고리즘을 사용해야한다는 사실을 알게되었다dijkstra: 하나의 시작 정점으로부터 모든 다른

11mdijkstra 알고리즘으로 X부터 시작하는 최단 거리를 구함 (각 학생 별 X에서 집으로 돌아오는 데 걸리는 최소 시간) -> result_pre1번 학생부터 N번 학생까지 for문을 돌며 각 학생부터 시작하는 최단 거리를 구함 (집에서 X로 가는 데 걸리는 최

1h 2m에라스토테네스의 체 알고리즘을 이용하여 10000 미만 소수를 판정할 수 있는 array를 미리 만듦bfs를 통해 4개의 자릿수 (일의 자리, 십의 자리, 백의 자리, 천의 자리) 마다 0 ~ 9까지 모든 경우를 확인하여 문제의 조건에 맞는 경우 해당 node

1h 9m설명대로 구현하면 되는 시뮬레이션 문제메모리 제한이 시간 제한보다 널널해서 총 3개의 메인 변수를 선언하여 풀이했다\-> board: 2차원 리스트/ 각 체스판의 색깔 정보 저장\-> horses: 2차원 리스트/ 각 말의 번호당 x, y, direction

1h 41m코드 다 짜놓고 "턴이 진행되던 중에 말이 4개 이상 쌓이는 순간 바로 종료"를 해줬어야했는데 바로 종료하지 않고 하나의 턴을 완료하고 말이 4개 이상 쌓인 곳이 있는 지를 확인하는 방식으로 했어서 뭐가 문제인지 한참 찾다가 한 시간을 까먹음.. 억까 아닌

11m이번 삼성 SW 알고리즘 역량 강화 사전문제에 풀로이드 워셜 문제가 나왔는데, 플로이드 워셜 알고리즘에 대해 공부 좀 할겸 품플로이드 워셜 알고리즘: 그래프 내의 모든 정점 쌍 간의 최단 경로를 구할 때 사용 (Dynamic Programming 기법) -> 그래

42mbellman-ford 알고리즘에 대해 공부한 후 풂bellman-ford 알고리즘\-> 음수 가중치가 있는 그래프의 시작 정점에서 다른 정점들까지의 최단 거리를 구할 수 있음\-> 음의 사이클의 존재 여부를 알 수 있음"한 지점에서 출발을 하여서 시간여행을 하기

2749: 피보나치 수 3 "피사노 주기"를 이용함 피사노 주기는 N번째 피보나치 수를 M으로 나눈 나머지는 N % P번째 피보나치 수를 M으로 나눈 나머지와 같다는 원리 M = 10^k 일 때, k > 2라면, 주기는 항상 15*10^(k-1)임 11444: 피보

1h 3m부분 격자로 나누기\-> 회전을 2^L \* 2^L크기의 부분 격자 단위로 해주어야하기 때문에 range(0, 2N, 2Lq)만큼의 2중 for문을 돌면서 시작 i점과 시작 j점을 구함\-> 시작 i점과 시작 j점을 기준으로 step만큼 (row의 길이만큼)

2h구현 자체가 크게 어려운 문제는 아니었는데 1번 조건: "크기가 가장 큰 블록 그룹을 찾는다. 그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블룩 그룹, 그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을, 그것도 여러개이면 열이 가장

22m무난한 bfs 탐색 문제였다처음에는 치즈를 시작노드로 하여 bfs 탐색을 하면서 'c'를 표시해야겠다고 생각했으나, 구현 방법을 떠올리기가 쉽지 않았다. 이 문제에선 "판의 가장자리에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구명이 있을 수 있다."라는 조

23m무난한 bfs 문제였다bfs 함수의 return value를 얼음덩어리의 좌표들로 설정함board를 순회하면서 bfs를 돌며 ices 리스트에 얼음덩어리의 좌표들을 append 해줌만약 len(ices)가 2 이상이라면 얼음이 두 덩어리로 나뉜 경우이므로 flag

1h 35m이 문제에서도 마찬가지로 "궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다." 와 같은 조건이 있었다. 이러한 조건은, 가능한 경우를 모두 구해주고 정렬을 통해서 처리해주는 방

22m무난한 bfs 및 구현 문제였다기억해두면 좋을 게, gravity 함수에서 row+1이 범위 내이고 아랫줄에 빈공간이 있을 때 현재줄과 아랫줄을 바꿔주고 그 외의 경우엔 바로 break를 해주는 방식이 구현 문제에서 많이 쓰이는 것 같다

풀이 시간 30m 100% 쯤에서 계속 indexError가 떠서 질문게시판을 확인한 결과 stdin을 받을 때, input[:-1]가 아닌 input[:9]로 해야 통과한다는 글을 보고 해결함. 문제의 입력에 오류가 있는듯 구현 방식 dfs + backtracki

20m알고리즘 분류를 보고 stack을 활용해서 풀이함입력받은 문자열을 순회하면서 문자 하나씩 stack에 append해줌stack에 넣어줄 때마다 stack의 tail - bomb_length부터 tail까지가 bomb와 같은지를 확인하고 같다면 바로 bomb_len

53m그냥 문제에서 구현하라는 대로 구현하면 된다search(x, y, number)\-> bfs를 통해 인접한 숫자를 찾고, 찾은 숫자의 좌표들을 반환해주는 함수이다\-> 문제의 조건,"(i, 1)은 (i, 2), (i, M)과 인접하다.(i, M)은 (i, M-1)

57m백트래킹 문제 감을 잃어서 전체적인 아이디어 틀만 (살짝) 참고했다이 문제에서는 윷놀이판의 graph를 직접 작성해야한다\-> graph: 인접 리스트 형태로, curr node당 next node를 매핑해줌. 파란색칸에 해당하는 node일 경우 1번 인덱스에 파

1h 20m특별한 알고리즘은 없는 빡구현 문제. 모든 연산을 구현해주면 된다2차원 배열의 시계방향 90도 회전2차원 배열의 반시게방향 90도 회전처음엔 deepcopy를 이용해서 나머지 부분을 구현해주려 했으나 deepcopy의 연산 시간이 짧지가 않아서, 하드코딩을

1h 39m그냥 구현하라는 대로 구현하면 되는 문젠데 약간 뻘짓해서 풀이 시간이 길었다일단 초록색 보드 (green)과 파란색 보드 (blue)를 따로 2차원 리스트로 생성했다아래를 차례대로 구현해주면 된다1) 초록색 판 이동2) 초록색 판 점수 획득 + 행 제거3)

2h근 200줄이다 윽IndexError: gravity 함수에서 "green + 타일이 2번인 경우"와 "blue + 타일이 3번인 경우"에 idx_flag 변수를 통해 다음 열 또는 행을 건너뛸 수 있도록 구현하여 해결함

16m무난한 bfs 문제모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정하기 때문에 매 turn 마다 bfs(0, 0)을 호출하여 'C'를 구한다C의 좌표를 구하는 과정에서, "모눈종이 모양의 치즈에서 각 치즈 격자(작은 정사각형 모양)의 4번 중에서 적어도

1h 50m처음에 backtracking으로 풀이하려 했으나, 반례가 안잡혀서 permutations를 이용해 모든 연산의 순서를 탐색하여 풀었다"배열 A와 사용 가능한 회전 연산이 주어졌을 때, 배열 A의 값의 최솟값을 구해보자. 회전 연산은 모두 한 번씩 사용해야

1h 30mdfs로 풀어야한다는 사실을 구글링하고 나서야 알았다 ☹️dfs max_result 갱신 및 종료 조건\-> depth가 N-1일 때가 끝에 도달한 경우이기 때문에 최댓값을 갱신하고 종료해줘야함재귀 호출 부분은 두 가지 경우로 나뉨1) 뒤에 괄호가 없어서 앞

1h 54m반례가 안잡혀서 고생하다가 겨우 찾음\-> "모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다"라는 조건에서 한 승객의 도착지가 다른 승객의 출발지인 경우가 발생 가능했다\-> 처음에는 board에 승객의 출발지는 2로, 승객의 도착지는 3으로

44m처음에 dfs로 풀었는데 Recursion Error랑 시간 초과가 나서 갈아엎고 bfs로 풀었다그냥 트리의 지름을 구하기 위해선 루트노드에서 가장 먼 노드(farest_node_1)을 찾고, farest_node_1에서 다시 가장 먼 노드(farest_node_

55m무난한 구현 문제. 왜 골드1인지는 모르겠다2차원 리스트(board)에 상어가 있는 좌표에 상어의 크기를 할당해줌딕셔너리(shark)에 "크기: (속력, 방향)" 형식으로 상어에 대한 정보를 저장해줌 전반적인 구현 방식은, C만큼 for문을 돌면서1) 현재 열에서

2h 30mdfs + 백트래킹 관련 문제를 더 많이 풀어봐야겠다"상어는 방향에 있는 칸으로 이동할 수 있는데, 한 번에 여러 개의 칸을 이동할 수 있다. 상어가 물고기가 있는 칸으로 이동했다면, 그 칸에 있는 물고기를 먹고, 그 물고기의 방향을 가지게 된다. 이동하는

43m처음에 brute force로 코드를 짰는데 메모리 초과가 나서 알고리즘 분류를 보고 비트마스킹 + 백트래킹 알고리즘을 사용하여 다시 풀었다비트마스킹 개념은 구글링을 통해 아이디어를 참고했다alphabet을 길이가 26인 리스트로 선언하여 index 별로 (알파벳

22m카드 묶음의 크기가 작은 묶음들끼리 먼저 비교를 해주어야 총 비교 횟수가 최소가 된다\-> 우선순위 큐를 이용heap에서 카드 묶음의 크기가 작은 묶음 두 개를 꺼내서 둘을 더한 값을 다시 heap에 넣는 과정을 len(heap)이 2이상일때까지 반복하면서 res

50m조합으로 푸는 아이디어를 참고해서 구현했다 (골드 5치고 너무 발상이 필요한 문제같다 ㅇㅅㅇ)outer for문: 자릿수만큼 for문을 돎 (1은 한자리수, 2는 두자리수, 3은 세지리수..)inner for문: combination을 이용하여 i자리수를 만드는

28m처음에 dfs만을 이용해서 풀었는데, M과 N이 각각 최대 500이기 때문에 대충 한 칸씩 상하좌우를 탐색한다고 치면 시간 초과가 발생한다알고리즘 분류를 보고 dp를 추가 이용해서 다시 풀었다dfs + dp 를 이용해서 풀었다그냥 재귀를 돌면 시간초과가 나기 때문

1h 34m계속 RecursionError(47%에서)랑 메모리 초과(2%에서)가 떠서 삽질하다가 python3으로 제출하니까 한번에 맞음. 내 코드가 문제는 아니었던걸로..(https://www.acmicpc.net/board/view/35748)dfs +

24m자료구조문제도 간간이 풀어줘야지N만큼 for문을 돌면서 building을 앞에서부터 순서대로 처리해준다매 회마다 stack의 tail에 building에 대한 값을 넣어주는데, 발사한 레이저 신호를 수신한 탑의 번호를 출력해야하므로 '탑의 index'와 '탑의

19m재귀를 이용해서 left, right 함수를 구현해주면 된다\-> 왼쪽 끝(left 함수)을 넘거나 오른쪽 끝(right 함수)을 넘는 경우 return\-> 두 톱니바퀴가 맞닿은 부분이 같다면 return\-> 두 톱니바퀴가 맞닿은 부분이 다르다면 재귀호출 후

1h 17m알고리즘 분류를 보고 Minimum Spanning Tree와 Kruskal 알고리즘을 공부한 후에 풀었다BFS와 MST를 찾는 Kruskal 알고리즘을 이용하여 풀었다1) 일단 섬들을 구분지어주고, 2) 각 섬들마다 다른 섬들로 이동할 수 있는 최소 길이의

7m사실 사전에 "17472: 다리만들기 2" 문제를 먼저 풀었다edges에 대해 cost 기준으로 오름차순 정렬edge를 하나씩 확인하며 현재의 edge가 node들 간에 사이클을 발생시키는 지 확인사이클이 발생하지 않으면 MST에 포함 / 사이클이 발생하면 MST에

12mdijkstra 알고리즘 이용출발점을 기준으로 초기화: 출발점에서 시작하여 모든 정점들까지의 거리를 무한대로 초기화. 출발점 자체의 거리는 0으로 설정인접한 정점들의 거리 갱신: 현재 방문하지 않은 정점들 중에서 출발점으로부터 거리가 가장 가까운 정점을 선택하고,

29m이 문제는 dijkstra 알고리즘을 이용하여 최단 거리를 구하는 것뿐만 아니라, 최단 '경로'를 구해야하는 문제였다"1916: 최소비용 구하기" 문제에선 costs에 거리만 저장해주었지만, 원소를 하나 더 추가해서 부모 노드도 저장해주어야한다\-> E부터 시작하

34m질문게시판을 보고 반례를 찾았다가운데수 보다 작은 값들이 최대힙에 들어가고, 가운데수 보다 큰 값들이 최소힙에 들어가도록 해줘야한다\-> N만틈 for문을 돌면서 두 힙의 길이를 맞춰가면서 값을 넣어주었다그러나 이렇게만 처리해줄 경우, 오른쪽 힙에 왼쪽 힙보다 작

30m1번 정점에서 N번 정점으로 최단 거리로 이동할 때, v1과 v2를 반드시 통과해야하기 때문에, 두 가지 경우를 생각해볼 수 있다1) 1 -> v1 -> v2 -> N2) 1 -> v2 -> v1 -> N따라서 1번에서 N까지 가는 dijkstra, v1에서 N까

1hdp문제 오랜만에 풀었는데 점화식 세우기 + 세운 점화식 구현하기는 여전히 너무 어렵다dpi에서, i는 가치의 합이고, dpi는 가치의 합이 i가 되는 경우의 수이다문제에서 주어진 조건으로 예를 들자면처음에 1원짜리 동전만을 이용하여 1원부터 K원까지 만드는 경

7m분리 집합 == 서로소 집합find: 부모를 찾는 함수union: 부모를 합쳐주는 함수

1h 10mprint("No")가 아니라 print("NO")로 출력을 해야했다..여행 계획에 포함된 도시들이 모두 같은 집합에 속해있다면 가능한 여행계획이고, 그렇지 않다면 불가능한 여행계획이다분리 집합 -> find-union을 이용해서 풀었다도시의 graph의 모

1h트리는 사이클이 발생하지 않는 그래프이다find-union을 통해 그래프를 찾아주는데, 해당 그래프에 사이클이 존재하는 지를 확인해주어야 한다모든 간선을 순회하면서,1) find(a) != find(b)이면 union(a, b)를 호출해서 부모 합쳐주기2) find

25m매 초마다 1~K까지 순서대로 전염되도록 구현한다면 최악의 경우 N \* N \* S = 200 \* 200 \* 10000으로 시간초과가 발생한다따라서 queue에 현재 몇 초인지를 넣어주어 (s == S 경우 break) while문 한 번에 끝나도록 구현해주

33m이 문제의 포인트는, count 딕셔너리 변수를 이용해서 {"사용자의 아이디": 그래프의 노드 개수} 형식으로 값을 저장하고 이를 이용해 문제에서 원하는 정답을 빠르게 찾아줘야한다는 점이었다union 함수에서 parent와 count의 값을 모두 a에 합쳐준다ed

40mfind-union을 이용하여 풀었다"공항에는 P개의 비행기가 순서대로 도착할 에정이며, 당신은 i번째 비행기를 1번부터 gi번째 게이트 중 하나에 영구적으로 도킹하려 한다."\-> parent를 gate들 간의 관계를 나타낼 수 있도록 설정해줘야한다예제 2에서

2h반례 찾는 게 힘들었다이 문제의 포인트는 클러스터 별로 중력을 작용해주는 부분이었던 것 같다.\-> 이렇게 해주기 위해선 클러스터에 대한 정보를 dictionary에 담아서 처리해주는 게 편하다 (key는 cluster number, value는 (x1, y1

16m우선순위 큐로 중앙값을 구하는 알고리즘은 이전에 "1655: 가운데를 말해요"에서 풀어본 적이 있었다max_heap에는 중앙값보다 작은 값이, min_heap에는 중앙값보다 큰 값이 들어간다두 heap의 길이를 맞춰가면서 값을 넣어주되, 길이가 같은 경우에는 ma

50m1\. 먼저 각 party마다 입력을 받고 분류를 해준다union 함수에서, 1) a와 b가 모두 진실을 아는 사람이라면 return2) a는 진실을 알고, b는 진실을 모른다면 b의 parent를 a로 설정3) b는 진실을 알고, a는 진실을 모른다면 a의 pa

1h 30m좌표를 하나씩 이동하면서 backtracking을 수행하는 아이디어를 참고했다좌표를 하나씩 이동하면서 backtracking을 수행하는 점이 신선했다backtrackingbacktracking 함수의 인자는 x, y, count이다return 조건\-> y좌

1h 20m열쇠를 발견했을 경우 queue와 visit리스트를 초기화하는 아이디어를 참고했다"상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다."라는 설명을 통해 board의 가장자리를 모두 '.'로 채워주고 H+

1h 10m이 문제는 "9328: 열쇠" 문제와 유사하나, 차이점은 이동 횟수의 최솟값을 구하는 문제라는 점이다\-> 또한 이 문제에선 열쇠 문제와 다르게 keys set을 이용하지 않고 비트마스킹을 이용했다visit 리스트를 3차원으로 선언하여 중복 방문 제거 및 d

23291: 어항 정리1h 45m문제에서 구현하라는대로 구현해주면 된다물고기 수 가장 적은 어항에 물고기 한마리 넣기왼쪽에 있는 어항부터 공중부양하여 시계방향 90도 회전 후 오른쪽 어항 위에 쌓기인접한 어항들에 대해 차이 줄이기바닥에 일렬로 놓기다시 공중부양 작업 (

2565: 전깃줄DP로 어떻게든 풀어보려고 애를 썼다일단 line을 A 기준 오름차순으로 정렬해줘야한다그 후, 2중 for문을 돌면서 dp table을 갱신해줘야한다outer for loop을 아래에 있는 전깃줄, inner for loop을 위에 있는 전깃줄로 잡았을

17070: 파이프 옮기기 13차원 dp table을 이용해 풀어주었다dpi0는 가로 파이프 놓는 경우의 수, dpi1은 세로 파이프 놓는 경우의 수, dpi2는 대각선 파이프 놓는 경우의 수기저: 0행먼저 순회하면서 board0의 값이 0이라면 dp00 = dp00으

1068: 트리주어진 트리에서 삭제하고자 하는 노드를 삭제한 후에 리프 노드의 개수를 출력하는 문제tree는 parent라는 이름의 list를 이용했다index: 자신의 노드, parentindex: 부모 노드dfs를 통해 parent의 값을 'False'로 변경해주어

1240: 노드사이의 거리dfs 탐색하면서 구하고자하는 cost를 구해주면 된다재귀 종료조건: node == dest일 때 global_cost를 update 해주고 return중복 노드를 제거해주지 않으면 무한 재귀 호출을 할 수 있기 때문에 visit 1차원 lis

19237: 어른 상어간만에 풀어보는 삼성 구현문제/ 문제에서 안내한 대로 구현해주면 된다. 딱히 코너 케이스도 없다구현 순서는 아래와 같이 해야한다인접한 칸으로 이동하는 과정 (아무 냄새가 없는 칸으로, 여러 개면 우선순위에 따라서 이동/ 아무 냄새가 없는 칸이 없으

12851: 숨바꼭질 2 가장 빠른 시간이 몇 초 후인지와, 가장 빠른 시간으로 찾는 방법이 몇 가지인지를 구해야하기 때문에 queue에 노드를 추가할 때 조건문을 조금 신경써줘야 한다

4179: 불!고려해야할 코너 케이스가 몇 가지 있었다1) 지훈이가 1초만에 통과할 수 있는 경우2) 처음에 지훈이와 불은 여러 군데 존재할 수 있다도착점은 따로 ex에 넣어서 처리해주었다bfs를 두번 탐색해서 해결해주었다먼저, 불이 번지는 경우를 bfs로 처리해주고

9466: 텀 프로젝트시간초과를 극복하기가 어려웠다 (pypy3은 메모리초과, python3으로 setrecursionlimit(10\*\*6) 설정해서 통과함)team list를 이용해서 해결했다일단, visit list는 반복문 밖에 한 번만 선언해줘도 된다team

23289: 온풍기 안녕!문제에서 안내한대로 구현해주면 된다이 문제에선 벽을 어떻게 효과적으로 판별해줄지가 포인트였다wall = \[set() for c in range(C) for r in range(R)] 형식의 set을 원소로 갖는 2차원 list를 이용했다. s

23288: 주사위 굴리기 2전반적인 구현 흐름은 아래와 같다K만큼 for문을 돌면서,현재 위치에서 현재 방향으로 이동했을 때, 칸이 있는지 없는지 판별하여 없다면 방향을 반대로 바꿔준다다음 위치로 주사위를 이동시킨다해당 경우에 획득할 수 있는 점수를 bfs 탐색으로

14938: 서강그라운드N이 100 이하여서 그냥 dijkstra로 풀어주었다N번 dijkstra 돌면서 예은이가 얻을 수 있는 아이템의 최대 개수를 갱신해줌

4485: 녹색 옷 입은 애가 젤다지?이 문제의 경우 bfs로 풀면 안된다bfs는 한번 방문한 노드를 재방문하지 않으므로, 가중치가 있는 그래프에서 최소 cost 경로를 찾지 못할 수가 있음반면, dijkstra는 더 빠른(최소 cost) 경로가 있다면 방문했던 노드를

18428: 감시 피하기3개의 장애물을 설치하는 경우를 모두 고려하여 brute force로 풀어주었다3개의 장애물을 설치하는 부분을 backtracking을 이용해서 구현해주었다if o_cnt == 3이면, check() 호출하여 감시 피할 수 있는 지의 여부 검사e

2661: 좋은수열backtracking 유형의 문제이다뒤에 숫자를 "하나씩" 붙여가면서 좋은수열을 만족하는 지 check_curr함수를 통해 확인해주면서 backtracking을 진행해주면 된다check_curr 함수는 "하나의 숫자"를 붙였을 때 좋은 수열을 만족하

1941: 소문난 칠공주brute force로 25C7의 경우를 모두 고려해주었다3번 조건 '이다솜파'가 반드시 우위를 점해야 한다. 따라서 7명의 학생 중 '이다솜파'의 학생이 적어도 4명 이상은 반드시 포함되어 있어야 한다.에 따라 ratioCheck() 함수로 p

2174: Crashing Robots2차원 list로 board를 선언해주고, 로봇이 없는 칸은 0, 로봇이 있는 칸은 로봇의 번호를 값으로 갖도록 해주었다robot이라는 hashMap을 이용해서 key는 로봇의 번호, value는 x좌표, y좌표, 로봇의 현재 방향

7490: 0 만들기전형적인 백트래킹 문제python으로는 string 형식으로 path를 저장해주고, eval()을 이용해서 한번에 수식의 값을 구해주었다cpp로는 vector로 path를 저장해주었고, 매 회마다 result 값도 구해서 저장해주었다공백 연산의 경우

28703: Double Itmin heap을 이용해서 최솟값이 초기의 최댓값(mx)보다 작을때까지 "배열에서 원하는 수 하나를 골라서 2를 곱합니다"의 연산을 수행해주었다cpp에서 priority_queue 사용하는 방법은 아래와 같다최소힙최대힙

9205: 맥주 마시면서 걸어가기bfs로 풀어주었다초기 맥주 20개, 50미터를 가려면 맥주 한 개를 마셔야하므로, src 또는 mid에서 출발하여 다른 mid 또는 dest로 가기 위해선 그 사이의 거리가 1000미터 이하여야 한다node는 pair<int, i

2961: 도영이가 만든 맛있는 음식 백트래킹으로 구현해주었다 매 노드마다 visit 리스트를 인자로 넘겨주어, 하나의 재료를 중복하여 사용하는 경우가 생기지 않도록 해주었다 dfs 함수 인자에 idx도 같이 넘겨주어 더 효율적인 탐색이 가능하도록 해줌 코드

2251: 물통bfs를 이용한 brute force로 풀어주었다a -> b, a -> c, b -> a, b -> c, c -> a, c -> b의 모든 경우를 고려해주었다queue에는 현재 노드의 a, b, c의 물의 양을 넣어주었고, visit를 3차원 리스트로 선

16987: 계란으로 계란치기계란을 치는 과정을 보면, 백트래킹 문제임을 알 수 있다가장 왼쪽의 계란을 든다.손에 들고 있는 계란으로 깨지지 않은 다른 계란 중에서 하나를 친다. 단, 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다. 이후

2558: 숫자고르기주어진 표를 단방향 그래프로 나타내주고, 해당 그래프를 순회하면서 사이클이 존재한다면 사이클의 원소들을 result set에 추가해주는 방식으로 구현해주었다1차 for문을 돌면서 N번 dfs를 호출해줌i가 result에 없는 경우에만 dfs를 호출해

11048: 이동하기2차원 미로여서 bfs로 풀려다가 시간초과, 메모리초과가 나서 삽질했다 (무작정 bfs로 푸는 건 안좋은 습관..)이 문제는 dp로 풀면 쉽게 풀린다N+1의 크기만큼 dp table을 생성해주고 2중 for문을 돌며 갱신해주면 된다점화식은 아래와 같

16985: Maaaaaaaaazepermutations를 이용해서 5층의 순서를 정해준다순서를 정한 후, dfs 탐색으로 하나의 판을 0도, 90도, 180도, 270도 회전해주고, 이 과정을 depth == 5가 될 때까지 반복하여 모든 층을 회전해준다 (4^5의

1175: 배달거하게 삽질한 문제..이 문제는 visit 리스트를 5차원으로 선언하여 bfs 탐색으로 풀었다visit 리스트는 directionyC2 순서이다.start위치는 direction을 4로 설정해주면 간편하다!bfs 탐색 시, len(queue)만큼씩 한번에

16946: 벽 부수고 이동하기 4우선 벽이 있는 위치(board 값이 1)를 board 값을 -1로 변경해주었다그 후, board를 순회하면서, 이동할 수 있는 위치(board값이 0)마다 bfs 탐색으로 인접한 부분을 grouping 해주었다. 이 과정에서 grou

18352: 특정 거리의 도시 찾기dijkstra로도 풀 수 있고, bfs로도 풀 수 있다dijkstra 풀이bfs 풀이

5719: 거의 최단 경로전반적인 구현 흐름은 아래와 같다간선을 입력받을 때, 정방향 간선(edges), 역방향 간선(edges_r), 인접행렬(edges_check)을 완성해준다(경로의 일부를 공유하는 경우를 처리하기 위해 인접행렬을 사용해줌)먼저 dijkstra를

3980: 선발 명단전형적인 backtracking 문제최댓값 갱신 조건: depth == 11check = False\*11를 통해 해당 포지션에 배치가 됐는 지 안됐는 지를 판별해주었다not checki and Sdepth != 0인 경우에 backtracking

1922: 네트워크 연결kruskal 알고리즘으로 MST를 구해주었다MST: cycle이 발생하지 않고, 간선들의 가중치 합이 가장 작은 treekruskal 알고리즘을 이용하기 위해선 edges를 weight 기준으로 오름차순 정렬해줘야함

1647: 도시 분할 계획입력으로 주어지는 edges는 모든 노드들이 연결되어있는 간선들이다우선 MST를 구해준 후에, MST의 간선 중 가중치가 가장 큰 간선을 제거해주는 방식으로 유지비 합의 최솟값을 구해주었다MST를 구하는 과정에서, path(MST의 간선들을 저

6497: 전력난매 TC마다 MST를 구해주고, 모든 간선들의 가중치 합에서 MST내 간선들의 가중치 합을 빼준 값이 절약할 수 있는 최대 비용이 된다

2470: 두 용액투 포인터를 이용해서 풀었다A를 오름차순으로 정렬left를 가장 왼쪽 idx, right를 가장 오른쪽 idx로 설정check은 현재 가장 0에 가까운 용액의 수치 (abs(l_value + right_value))left < right을 만족하

2805: 나무 자르기이분탐색으로 풀어주었다1654: 랜선 자르기이분탐색으로 풀어주었다

23290: 마법사 상어와 복제삼성 기출 간만에 푸니까 더 안풀린다 😇board를 3차원 list로 선언해주어, 물고기의 방향을 저장할 수 있게끔 해주었다smell은 (x, y):smell_cnt 형식의 dictionary로 선언해주었다상어는 sx, sy의 정보만 필

5427: 불두 개의 queue를 이용해서 bfs를 수행해주었다fire -> 불에 해당하는 queuestart -> 상근이에 해당하는 queuewhile문을 돌면서, 1) bfs_fire를 한 타임 실행해주고, 이어서 2) bfs_sang을 한 타임 실행해준다1) bf

1405: 미친 로봇dfs로 풀어주었다이동 경로가 단순하다 == 한번 방문한 칸은 다시 방문하지 않는다

3197: 백조의 호수시간 초과를 해결하기 위해 임시 큐를 사용하는 아이디어를 참고했다전반적인 흐름은 While문을 돌면서,1) 얼음을 한 타임 녹임 (물에 해당하는 좌표들에서 bfs 한 타임 실행)2) 백조 한 타임 이동 (백조에 해당하는 좌표들에서 bfs 한 타임

12015: 가장 긴 증가하는 부분 수열 2이분 탐색을 이용해서 O(nlogn)으로 LIS의 길이를 구해줄 수 있다 (LIS의 구성 요소는 다를 수 있음)

4386: 별자리 만들기Kruskal 알고리즘을 통해 MST를 구해주는 문제이다별들이 2차원 좌표로 나타나기 때문에 edges 정의만 신경써서 해주면 된다\-> 두 개의 별에 대해 nodes의 인덱스를 a, b라고 한다면, edges에 (math.sqrt((nodesa

1600: 말이 되고픈 원숭이벽 부수고 이동하기 문제와 풀이 방법이 같음3차원 visit리스트를 이용한 bfs로 풀어주었다

1525: 퍼즐bfs를 통한 완전탐색으로 풀어주었다주어진 시간 내에 완전탐색을 수행해주기 위해, board를 1차원 string으로 정의해 주었고, 중복 제거 및 이동 횟수 저장을 dictionary로 처리해주었다

1202: 보석 도둑가방에는 최대 한 개의 보석만 넣을 수 있음jewels를 (무게, 가격) 형식으로 오름차순 정렬 (최소힙 이용)bags를 담을 수 있는 최대 무게 기준으로 오름차순 정렬bags를 기준으로 순회candi를 최대힙으로 설정하여 각 가방마다 while문을

2252: 줄 세우기위상 정렬 기본 구현 문제이다위상 정렬: 사이클이 없는 방향 그래프(DAG)의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열진입차수(indegree): 특정한 노드로 들어오는 간선의 개수진출차수(outdegree): 특정한 노드에서 나가는 간선

16724: 피리 부는 사나이성우가 정해놓은 방향대로 움직이면서, 몇개의 cycle이 발생하는 지를 찾는 find-union 문제이다find-union 수행 시 parent는 1차원으로 정의되므로 x = idx//M; y = idx%M 이런 식으로 차원을 낮춰주는 처리

2623: 음악 프로그램순서가 정해진 단방향 그래프에서 노드들의 순서를 정하는 문제이므로 위상 정렬로 풀어주었다모든 노드를 방문하지 못했을 경우(len(result) != N인 경우), cycle이 발생한 경우이므로 0을 출력해줘야 한다

2467: 용액이분 탐색으로 풀어주었다l < r을 만족할 때까지, value = Al + Ar이 음수라면 l+=1, 양수라면 r-=1abs(value)가 near_value(지금까지 가장 0과 가까운 value) 보다 작다면 x, y, near_value 갱신

업로드중..2437: 저울수직전을 사용하는 아이디어를 참고했다구간 1, 10에서 무게 5인 추가 추가된다면 -> 1+5, 10+5을 추가로 측정할 수 있음 -> 총 구간은 1, 15가 됨구간 1, 5에서 무게 7인 추가 추가된다면 -> 1+7, 10+7을 추가로 측정할

2812: 크게 만들기stack + greedy로 풀었다왼쪽부터 오른쪽으로 for문을 돌면서, K만큼 while문을 돌면서 stack에 가장 큰 숫자가 앞쪽에 위치하도록 해주었다