# 백트래킹

16개의 포스트
post-thumbnail

스타트와 링크_14889

문제 출처 : 스타트와 링크_14889 파라미터 정리 N 총 사람 수(4 ~ 20, 짝수) Row 팀(스타트) or Col 팀(링크)로 생각하기 Sij i번 사람과 j번 사람 사이에 존재하는 시너지 (1~100) Sij는 Sji와 다를 수 있음 Sii는 항상 0 (자기 자신과의 시너지를 의미하므로 0) 각 팀의 능력치는 모든 팀원의 시너지를 더한 것 원하...

어제
·
0개의 댓글

[BOJ 6987] 월드컵 (Java)

BOJ 6987 월드컵재미있는 문제였다. 처음 생각한 것은 전체 경기의 모든 경우를 입력으로 주어지는 것 처럼 스트링으로 만들어서 Set에 저장하고 입력이 들어올때 해당 경우가 Set에 존재하는지 확인하는 방식이였다. 하지만 메모리 초과!이 문제는 시간 제한 1초에 메

3일 전
·
0개의 댓글

[프로그래머스] N-Queen (Java)

프로그래머스 N-Queen백트래킹의 기본 예제로 사용되는 N-Queen 문제다.col 배열은 i행에는 coli열에 퀸이 배치되어있음을 나타낸다.isPossible 함수행을 중심으로 퀸을 배치해나가기 때문에 현재 행의 이전 행들 중에서 같은 열에 퀸이 배치된적이 있는지

2020년 5월 21일
·
0개의 댓글
post-thumbnail

연구소_14502

문제 출처 : 연구소_14502 파라미터 정리 NxM 직사각형, N:row, M:col (3~8) 0 : 빈칸 (3~) 1 : 벽 2 : 바이러스 (벽을 만날때까지 상하좌우로 퍼짐) (2~10) 추가로 3개의 벽을 세움 원하는 것 = 벽 3개를 세워 바이러스 확산을

2020년 5월 16일
·
0개의 댓글
post-thumbnail

치킨배달_15686

문제 출처 : 치킨배달_15686 파라미터 정리 NxN 맵 크기 (2~50) 1칸은 1x1 크기, 빈 칸(0), 치킨집(2), 집(1) 中 1 (r,c) r : row, c : col 각 값은 1부터 시작함 치킨 거리 = |r1-r2| + |c1-c2| (집과 가장

2020년 5월 16일
·
0개의 댓글
post-thumbnail

사다리조작_15684

문제 출처 : 사다리조작 파라미터 정리 N 세로선(col), M 가로선(연결선), H 점선(row) 사다리 게임이 진행되는 방법 : 아래(r+1), 좌측(c-1),우측(c+1) 中 택1 가로선은 연속하거나 서로 접하면 안됨 원하는 것 = 가로선을 추가하여 모든 i번

2020년 5월 16일
·
0개의 댓글

[BOJ 16937] 두 스티커 (Java)

BOJ 16837 두 스티커스티커가 나오면 바로 DP가 떠오르지만 이 문제는 아니다! 시간이 넉넉하고 메모리도 넉넉하다 완전탐색이 제격인 문제로 보인다.스티커가 90도 회전 가능하지만 스티커의 사이즈가 주어진 형식으로 보아 모든 스티커가 직사각형의 자리를 차지하는 것을

2020년 5월 13일
·
0개의 댓글
post-thumbnail

백준 14500 테트로미노

# 문제 ### DFS를 사용해서 합의 최댓값을 구하는 문제. (ㅜ 모양은 예외처리 합니다) 1. n 종이의 크기 (4 ≤ N, M ≤ 500) 2. 종이 한칸의 수는 (1<= aij <= 1,000) 3. 5개의 모양을 종이에 놓아서 합의 최대값을 구합니다.

2020년 5월 1일
·
0개의 댓글
post-thumbnail

BOJ 14889. 스타트와 링크

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.BOJ를 운영

2020년 4월 13일
·
0개의 댓글

[프로그래머스] 단체사진 찍기 (Java)

프로그래머스 단체사진 찍기캐릭터들이 옆으로 나란히 서서 단체 사진을 찍을 때 각 캐릭터들이 요구하는 모든 조건을 만족하는 경우의 수를 구하는 문제다. 역시나 가장 먼저 완전탐색을 생각해봤다. 캐릭터들이 나란히 서는 모든 경우를 구하고 각 경우가 캐릭터들의 요구조건을 만

2020년 3월 8일
·
0개의 댓글

[BOJ 16638] 괄호 추가하기 2 (Java)

BOJ 16638 괄호 추가하기 2괄호 추가하기 1은 쉽게 풀었던 것 같은데 비슷한 아이디어가 다시 떠오르지 않아서 힘들었다. 이 문제의 핵심 아이디어는 다음과 같다.괄호는 연산자 기준으로 씌워진다.괄호를 어떻게 씌워줄까 굉장히 고민되는데 괄호는 연산자를 중심으로 씌워

2020년 2월 23일
·
0개의 댓글

[BOJ 4574] 스도미노쿠 (Java)

BOJ 4574 스도미노쿠알고리즘이 어려운 문제는 아니였으나 구현이 까다로워 상당히 힘들었다. 스도쿠 판을 모두 채운 후에 유효성 체크를 하는 것이 아니라 백트래킹을 실시하는 중에 방문체크를 통해서 항상 옳은 경우만 나오도록 하는 것이 중요했다.row, col, squ

2020년 2월 19일
·
0개의 댓글

[BOJ 9944] NxM 보드 완주하기 (Java)

BOJ 9944 NxM 보드 완주하기재밌는(쉽게 풀리는...) 백트래킹 문제였다.

2020년 2월 11일
·
0개의 댓글

[BOJ 1248] 맞춰봐 (Java)

BOJ 1248 맞춰봐 문제풀이 Sidx의 부호가 A[idx]의 부호를 나타낸다는 것을 바탕으로 각 자리의 부호를 만족하는 모든 경우의 수를 구하고 그 안에서 S의 모든 조건을 체크하는 함수를 통해 확인하는 방식을 생각하였으나 당연히 시간초과였다. 수열을 만든 후에 조건을 체크할 것이 아니라 조건에 맞는 수를 자리에 위치시켜야하고 그를 위해서는 합계를 ...

2020년 1월 28일
·
0개의 댓글
post-thumbnail

백준 14889 스타트와 링크

팀 나눌때 항상 이 짤 생각나서 문제 두 팀 총 힘의 차이의 최소값을 구하는 문제 1. n 총 인원수 (4 ≤ n ≤ 20, n은 짝수) 2. 한 팀의 힘은 다음과 같이 계산 한 팀에 1, 3, 5가 속했을때 2명씩 추출한다. 팀 총합 = s1 + s3 + s

2019년 7월 23일
·
0개의 댓글
post-thumbnail

백준 17142 연구소3

문제 연구소의 지도가 주어집니다. (0 빈칸, 1 벽, 2 바이러스) 전체 바이러스 중에서 m개의 바이러스만 활성화 시킵니다. 바이러스는 인접한 4방향(위쪽, 오른쪽, 아래쪽, 왼쪽)으로만 이동 가능하며 빈칸만 지날 수 있습니다. 비활성화 바이러스는 활성화 바이러스를

2019년 4월 20일
·
0개의 댓글