본문 바로가기

BOJ

 (223)
[BOJ] 1280. 나무심기 *세그먼트 트리를 사용한다. *현재 나무의 좌표가 [pos]라고 가정한다. pos가 나온 시점보다 앞에 심어진 나무 중 pos보다 좌표의 크기가 큰 좌표의 합 = sumUpper 개수 = a pos가 나온 시점보다 앞에 심어진 나무 중 pos보다 좌표의 크기가 작은 좌표의 합 = sumLower 개수 = b 3 2 0 4 1 이렇게 다섯 개의 나무가 심어질 것이다. 3의 관점에서 sumUpper = 0/ sumLower = 0 / a = 0 / b = 0 => cost = 0 2의 관점에서 sumUpper = 3 / sumLower = 0 / a = 1 / b = 0 => 좌표 사이의 거리를 구하는 것이기 때문에 sumUpper - pos*a를 해줘야 한다. (각 좌표에서 기준 좌표를 빼주는 것과 같다)..
[BOJ] 2636. 치즈 * 치즈가 없는 좌표(0)에서 탐색할 수 있는 곳에 (상하좌우) 치즈가 있는 좌표(1)가 있다면 -> 이번 타임에 녹는 치즈이다. * 큐를 돌고 있는 상황에서 치즈를 바로 없애버리면 (1-> 0) 한 타임에 모든 치즈가 녹아버린다. * 위 상황을 방지하기 위해 이번 타임에 녹은 치즈는 map에 -1로 표시한다. * 치즈의 개수를 셀 때 -1인 좌표를 0으로 바꾼다. (벡터에 넣어주고 그 좌표들만 0으로 바꿔줘도 되지만, 어차피 치즈 개수 셀 때 모든 맵의 좌표를 탐색하기 때문에 이 때 바꿔주는 것으로 했다.) * 치즈가 모두 녹아 없을 때까지 (check() == True) 반복한다. * 치즈가 모두 녹기 한 시간 전에 있는 치즈의 개수를 세야 하기 때문에 howmanyCheese()를 만들었다. 더 효..
[Python] 리스트 안에 중복된 원소의 개수 구하기 import collections a = [1,1,1,1,2,2,2,2,3,3,4,5,5] counter=collections.Counter(a) print(counter) # Counter({1: 4, 2: 4, 3: 2, 5: 2, 4: 1}) print(counter.values()) # [4, 4, 2, 1, 2] print(counter.keys()) # [1, 2, 3, 4, 5] print(counter.most_common(3)) # [(1, 4), (2, 4), (3, 2)] dict = [] for key, value in counter.items(): dict[key] = value
[BOJ] 18808. 스티커 붙이기 *단순 시뮬레이션 *스티커가 회전한 결과를 미리 저장한다. sticker[100][4][10][10] 0: 0도 1: 90도 2: 180도 3:270도 *스티커가 순서대로가 아니라 조합을 구하는 건 줄 알고 시간초과를 걱정했는데 다행히 순서대로 붙이는 것이다. 스티커를 순서대로 불러오면서 4방향을 모두 본다. check() 에서는 지금 범위에 스티커를 붙일 수 있는지 없는지를 확인하고, 붙일 수 있으면 넣는다. 여러 곳을 붙일 수 있으면 가장 위쪽을 선택하는 것이기 때문에 그리디하게 해결할 수 있다. *스티커의 높이와 너비는 차지하는 칸과 동일하지 않기 때문에 sizes라는 백터배열에 저장한 후 가져왔다. *코드가 많이 더럽다. 시뮬레이션 문제이니, 풀이 방법만 참고하시길.. 더보기 #include #i..
[BOJ] 18809. Gaaaaaaaaaarden * 배양액들의 조합을 구해서 배치한다. * 큐를 [초록색 배양액, 빨간색 배양액] 으로 두 개를 사용하는데 depth와 좌표 정보를 넣었다. depth는 처음에 문제를 잘 못 이해해서 예시를 보고 추가했다. G 1 or 2 R 이렇게 되어있을 때만 가운데 좌표에 꽃이 필 수 있다. 동시에 도달했을 때의 정보를 넣어줘야 하는데 그 정보를 depth로 기록했다. *depth를 기록했다면 이 정보를 빠르게 찾아내야 하는데, 이 정보는 dp[][] 배열에 기록해서 빨간색 배양액이 다음에 갈 곳에 이미 초록색 배양액이 있다. -> dp[nx][ny] 가 depth + 1 이면 초록색 배양액이 방금 전에 도달한 곳이다라는 정보를 찾아낼 수 있다. -> 꽃을 틔운다. *50*50 인데 조합까지 해서 그런지 시간이 꽤..
[BOJ] 10799. 쇠막대기 (C) *스택 자료구조 구현 연습을 위해 C로 풀이 *() 는 레이저이므로 레이저가 나올 때마다 스택에 있는 [(] 의 개수만큼 더해준다. (쇠막대기가 잘라지니까) *[(]는 스택에 푸시 (레이저는 푸시 안함) *[)]는 스택에서 팝하는데 이때, sum++ 을 해줘야 한다. ((()())) 이렇게 있다면 보기 편하게 레이저를 *로 치환한다. ( (* *) ) 이렇게 될 것이다. 그럼 막대는 ( (* *) ) --- -> - - - ------ -> -- -- -- 이렇게 되는 데 레이저를 만날 때마다 스택에 있는 개수만큼 막대의 개수가 증가하게 된다. 막대의 끝을 의미하는 [)]가 나올 때는 나누어진 막대의 가장 오른쪽 개수를 세야 하기 때문에 sum++을 해준다. #include #include #includ..
[BOJ] 1158. 요세푸스 문제 (C) *큐 구현 연습을 위해 C로 품. #include #include #include //큐 구현하기 #define MAXX 5001 struct Queue { int num[MAXX]; int front, back; }; int isEmpty(struct Queue *q) { if (q->back == q->front) return 1; return 0; } int isFull(struct Queue *q) { int tmp = (q->back+1)%MAXX; if (tmp == q->front) { //back+1 을 MAXX로 나눈 값이 front와 같으면 //가득 차 있다. return 1; } return 0; } void push(struct Queue *q, int data) { if (isFu..
[BOJ] 18258. 큐2 *pypy3으로 제출해야 통과한다. (진짜 아슬아슬하게 시간 안에 들은 것 같다..) *파이썬 유저가 아니라서 더 이상 시간을 줄일 방법이 안 떠오른다. *input() 이 아니라 sys.stdin.readline 을 써야 한다. *c++에 scanf / java 에 bufferedReader 같이 입출력을 빠르게 해 주는 라이브러리 인 것 같다. *리스트를 큐로 구현했는데, pop(), index() 로 요소를 찾는 것보다는 size, idx 를 이용해서 투 포인터 같이 사용하는 게 더 빠르다. import sys read = sys.stdin.readline queue = [] idx = 0 size = 0 for _ in range(int(read())): order = read().rstrip("..

티스토리툴바